记忆一隅

散列笔记

2021-04-13 · 4 min read
数据结构与算法 编程

notes of hash table

概述

散列表(Hash table,也叫哈希表),是根据键(Key)而直接访问在内存储存位置的数据结构。通俗的说就是将要存储的内容按照一定规则计算出一个值,并将这个值作为该内容存储在表中的位置索引。这个规则我们一般称为散列函数或者哈希函数f(x)f(x)。散列表可以通过散列函数直接找到内容的存储位置并进行查找,其时间复杂度为常数时间O(1)O(1)

常见的散列函数[1]^{[1]}

直接定址法:取关键字或关键字的某个线性函数值为散列地址。即hash(k)=k{\displaystyle hash(k)=k}hash(k)=ak+b{\displaystyle hash(k)=a\cdot k+b},其中ab{\displaystyle a\,b}为常数(这种散列函数叫做自身函数)
平方取中法:取关键字平方后的中间几位为哈希地址。通常在选定哈希函数时不一定能知道关键字的全部情况,取其中的哪几位也不一定合适,而一个数平方后的中间几位数和数的每一位都相关,由此使随机分布的关键字得到的哈希地址也是随机的。取的位数由表长决定。
折叠法:将关键字分割成位数相同的几部分(最后一部分的位数可以不同),然后取这几部分的叠加和(舍去进位)作为哈希地址。
随机数法
除留余数法:取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即hash(k)=kmodp,pmpm{\displaystyle hash(k)=k\,{\bmod {\,}}p}, {\displaystyle p\leq m}p\leq m。不仅可以对关键字直接取模,也可在折叠法、平方取中法等运算之后取模。对p的选择很重要,一般取素数或m,若p选择不好,容易产生冲突。

哈希冲突

前面说了几种常用的散列函数,但是如果这个散列表需要存储的内容较多,使用散列函数求出的哈希值就有可能出现冲突,导致不同内容存到了相同的位置,这是需要避免的。处理冲突常见方法有:
开放定址法,它的基本思想是当一个位置被占用的时候,采用一种方式来寻找下一个可用的位置[2]^{[2]}
线性探查(linear probing): 当一个位置被占用,找下一个可用的位置。 h(k,i)=(h(k)+i)h(k,i)=(h′(k)+i)%m,i=0,1,...,m−1
二次探查(quadratic probing): 当一个位置被占用,以二次方作为偏移量。 h(k,i)=(h(k)+c1+c2i2)h(k,i)=(h′(k)+c_1+c_2i^2)%m,i=0,1,...,m−1
双重散列(double hashing): 重新计算 hash 结果。 h(k,i)=(h1(k)+ih2(k))h(k,i)=(h_1(k)+ih_2(k))%m

链表法 ,将散列到同一个存储位置的所有元素保存在一个链表中,但这样在查找时,就需要对链表进行搜索,其时间复杂度也就不再是O(1)O(1)

[1] https://zh.wikipedia.org/wiki/%E5%93%88%E5%B8%8C%E8%A1%A8
[2] https://python-data-structures-and-algorithms.readthedocs.io/zh/latest/07_%E5%93%88%E5%B8%8C%E8%A1%A8/hashtable/