在了解golang的map之前,我们需要了解哈希这个概念。
哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将所需查询的数据映射到表中的一个位置让人访问,这加快了查找速度。这个映射函数称为散列函数,存放记录的数组称作散列表。
一个优秀的哈希函数应该包含以下特性:
由于哈希算法被计算的数据是无限的,而计算后的结果范围有限,因此总会存在不同的数据经过计算后得到的值相同,这就是哈希冲突。
解决哈希冲突的方法一般有:开放定址法、链地址法(拉链法)、再哈希法、建立公共溢出区等方法。
而我们这里主要介绍开放地址法和拉链法。
链接地址法的思路是将哈希值相同的元素构成一个同义词的单链表,并将单链表的头指针存放在哈希表的第i个单元中,查找、插入和删除主要在同义词链表中进行。链表法适用于经常进行插入和删除的情况。
从发生冲突的那个单元起,按照一定的次序,从哈希表中找到一个空闲的单元。然后把发生冲突的元素存入到该单元的一种方法。开放定址法需要的表长度要大于等于所需要存放的元素。
在开放寻址法中解决冲突的方法有:线性探测法、平方探测法、双散列函数探测法。
开放定址法的缺点在于删除元素的时候不能真的删除,否则会引起查找错误,只能做一个特殊标记。只到有下个元素插入才能真正删除该元素。
线性探查法是开放定址法中最简单的冲突处理方法,它从发生冲突的单元起,依次判断下一个单元是否为空,当达到最后一个单元时,再从表首依次判断。直到碰到空闲的单元或者探查完全部单元为止。
设Hash(key)表示关键字key的哈希值,表示哈希表的槽位数(哈希表的大小)。
线性探测法可以表示为:
同样以哈希函数H(key)=key MOD 7(除数取余法)对一组元素[50,700,76,85,92,73,101]进行映射。
其中,empty代表槽位为空,occupied代表槽位已被占(后续映射到该槽,则需要线性向下继续探测),而lazy delete则代表将槽位里面的数据清除,并不释放存储空间。
平方探查法即是发生冲突时,用发生冲突的单元d[i], 加上 1²、 2²等。即d[i] + 1²,d[i] + 2², d[i] + 3²…直到找到空闲单元。 在实际操作中,平方探查法不能探查到全部剩余的单元。不过在实际应用中,能探查到一半单元也就可以了。若探查到一半单元仍找不到一个空闲单元,表明此散列表太满,应该重新建立。
这种方法使用两个散列函数hl和h2。
其中hl和前面的h一样,以关键字为自变量,产生一个0至m-l之间的数作为散列地址;
h2也以关键字为自变量,产生一个l至m-1之间的、并和m互素的数(即m不能被该数整除)作为探查序列的地址增量(即步长),探查序列的步长值是固定值l.
对于平方探查法,探查序列的步长值是探查次数i的两倍减l;
对于双散列函数探查法,其探查序列的步长值是同一关键字的另一散列函数的值。
哈希桶:所有哈希值组成哈希空间
装载因子:表示哈希表中元素的填满程度。
计算方式:装载因子=填入哈希表中的元素个数/哈希表的长度。
装载因子越大,填入的元素越多,空间利用率越高,发生哈希冲突的几率变大。
装载因子越小,填入的元素越少,空间利用率越低,但空间浪费多,而且会提高扩容操作的次数。
开放地址法
只用数组一种数据结构就可完成存储,继承了数组的优点,对CPU缓存友好,易于序列化操作。
但是它对内存的利用率不如链地址法,且发生冲突时代价更高。当数据量明确、装载因子小,适合采用开放寻址法。
链地址法
1、处理冲突简单,且无堆积现象
2、由于拉链法中各链表上的节点空间在需要时创建,不必像开放地址法事先申请好足够的内存,因此对内存使用率较高,适合造表前无法确定表长的情况
3、对装载因子的容忍度较高,适合存储大对象、大数据量的哈希表
4、删除结点的操作易于实现,只要简单地删去链表上相应的结点即可。