哈希表中处理冲突的方法

哈希表

哈希表在建立的时候有两个地方比较重要，一个是哈希函数，另外一个就是如何解决地址冲突。

为什么会有冲突？

当关键字集合很大时，关键字值不同的元素可能会映像到哈希表的同一地址上，即K1!=K2，但f(K1)=f(K2),这种现象称为hash冲突，实际中冲突是不可避免的，只能通过改进哈希函数的性能来减少冲突。

解决哈希冲突的几种办法

处理冲突是指对于一个待插入哈希表的数据元素，若按给定的哈希函数求得的哈希地址已被占用，则按一定规则求下一哈希地址，如此重复，直至找到一个可用的地址以保存该元素。

1、开放地址法。基于该重复地址，对地址进行增量，+1，2，3，4…或者±$1^2,2^2,3^2,...k^2$，线性探测再散列，二次探测再散列，伪随机探测再散列。
2、链地址法。将所有按给定的哈希函数求得的哈希地址相同的关键字存储在同一线性链表中，且使链表按关键字有序。