【软考】哈希表

1.一般存储结构由于记录在存储结构中的相对位置是随机的，查找时通过一系列与关键字的比较才能确定被查记录在表中的位置。
2.哈希表则通过计算一个以记录的关键字为自变量的函数（称为哈希函数）来得到该记录的存储地址。
3.哈希表中进行查找时，需用同一哈希函数计算得到待查记录的存储地址，然后到相应的存储单元去获得有关信息再判定查找是否成功。
4.根据设定的哈希函数H(key)和处理冲突的方法，将一组关键字映射到一个有限的连续的地址集（区间）上，并以关键字在地址集中的像作为记录在表中的存储位置，这种表称为哈希表，这一映射过程称为哈希造表或散列，所得的存储位置称为哈希地址或散列地址。
5.对于某个哈希函数H和两个关键字K₁和K₂，如果K₁≠K₂，而H(K₁)=H(K₂)，则称为冲突。
6.具有相同哈希函数值的关键字对该哈希函数来说称为同义词。
7.冲突只能尽可能减少而不能完全避免，因为哈希函数是从关键字集合到地址集合的映像。
8.通常关键字集合比较大，它的元素包含所有可能的关键字，而地址集合的元素仅为哈希表中的地址值。
9.一般情况下，哈希函数是一个压缩映像，冲突是不可避免的。

1.H_i=(H(key)+d_i)%m i=1,2,…,k (k ≤ m-1)其中，H(key)为哈希函数，m为哈希表表长
2.常见的增量序列有：线性探测再散列d_i=1,2,3,…,m-1；二次探测再散列d_i=1²,-1²,2²,-2²,…,±k²(k≤m/2)；随机探测再散列d_i=伪随机数序列

1.最简单的产生探测序列的方法是进行线性探测，也就是发生冲突时，顺序地到存储区的下个单元进行探测。
2.例如，某记录的关键字为 key，哈希函数值 H(key)。若在哈希地址j发生了冲突(即此位置已存放了其他记录)，则对哈希地址j+1进行探测，若仍然有冲突，再对地址 j+2 进行探测，依此类推，直到找到一个“空”的单元并将元素存入哈希表。
3.线性探测法可能使第i个哈希地址的同义词存入第 i+1 个哈希地址，这样本应存入第 i+1个哈希地址的元素变成了第 i+2个哈希地址元素的同义词
4.线性探测法的优点：思路清楚，算法简单
5.线性探测法的缺点：① 溢出处理需另编程序。一般可另外设立一个溢出表，专门用来存放上述哈希表中放不下的记录。实现溢出表最简单的结构是顺序表，查找方法可用顺序查找。② 线性探测法很容易产生聚集现象。所谓聚集现象，就是存入哈希表的记录在表中连成一片。当哈希函数不能把关键字很均匀地散列到哈希表中时，尤其容易产生聚集现象，这种情况下会增加探测的次数，从而降低了查找效率。
6.用户可以采取多种方法减少聚集现象的产生，二次探测再散列和随机探测再散列是两种有效的方法。