Java之解决散列表的冲突用开放定址法和链表法

1 问题

理想状态下，散列表就是一个包含关键字的固定大小的数组，通过使用散列函数，将关键字映射到数组的不同位置，哈希函数可以将关键字均匀的分散到数组的不同位置，不会出现两个关键字散列值相同（假设关键字数量小于数组的大小）的情况。但是在实际使用中，经常会出现多个关键字散列值相同的情况（被映射到数组的同一个位置），我们将这种情况称为散列冲突。为了解决散列冲突，主要采用下如下两种方式：

2 链表法

分散链表法使用链表解决冲突，将散列值相同的元素都保存到一个链表中。当查询的时候，首先找到元素所在的链表，然后遍历链表查找对应的元素。下面是一个示意图：

3 开放定址法

在散列算法得到一个存储地址之后，如果发生冲突，不是在原处创建一个链表而是按照一定规则寻找周围可用的地址进行插入。

这个规则我么可以是线性探测法、平方探测法、

1）线性探测法

线性探测法中，函数ff是ii的函数，记为：f(i)=i （i为寻址次数）这相当于相继探测每个单元。例子：我们在M=10点散列表中，按顺序插入下列数字{89，18，49，58，69}

按照散列方式(这里直接对数组大小取余)，在插入89和18时，直接插入到散列位置9和位置8。但是插入第三个数49时，散列位置为9，跟已有89冲突，于是开始线性探测，即按照顺序寻找下一个位置。i=1时，探测位置为散列位置M+i，即探测位置0，位置0无冲突，49存入位置0。插入第四个树58时，散列位置M=8，但是位置8已经存在18，发生冲突开始线性探测，i=1时，探测位置为散列位置M+i，位置9已有89存在发生冲突，i=2时，探测位置为0，位置0已有49存在，发生冲突，i=3时，探测位置1，位置1无冲突，58存入位置1。同理，69在探测到第3次后，存入位置2。

2）平方探测法

在线性探测法中，函数f是i的函数，记为：f(i)=i 。而在平方探测法中，我们通常使用的是f(i)=i^2 。还是上面的例子，我们利用平方探测法插入{89，18，49，58，69}

按照散列方式，在插入89和18时，直接插入到散列位置9和位置8。但是插入第三个数49时，散列位置为9，跟已有89冲突，于是开始平方探测，第一次探测i=1,f(i)=i^2=1,所以我们探测位置为位置0（位置9+1）。发现位置0不冲突，那么在位置0插入49。插入第四个数58时，散列位置8，跟已有18冲突，开始平方探测，第一次探测i=1,f(i)=i^2=1探测位置9（位置8+1），发生冲突,第二次探测i=2,f(i)=i^2=4，探测位置2（位置8+4），位置2不冲突，在位置2插入58

4 两种办法对比总结

1) 、链表法

的缺点是使用链表。在新单元分配地址需要时间，不同的语言需要的时间不一致，这会导致算法的速度有些减慢。链表法也是固定定址的一种，它处理冲突简单，且无堆积现象，平均查找长度短；链表中的结点是动态申请的，适合构造表不能确定长度的情况；相对而言，拉链法的指针域可以忽略不计，因此较开放地址法更加节省空间。插入结点应该在链首，删除结点比较方便，只需调整指针而不需要对其他冲突元素作调整。

hashmap解决冲突用的是链表法。

2) 、开放定址法

容易产生堆积问题；不适于大规模的数据存储；散列函数的设计对冲突会有很大的影响；插入时可能会出现多次冲突的现象，删除的元素是多个冲突元素中的一个，需要对后面的元素作处理，实现较复杂；结点规模很大时会浪费很多空间