HashMap解决冲突的四种方法

#HashMap解决冲突的四种方法| 来源: 网络整理| 查看: 265

1. 开放地址法

线性探测再散列图片转自：https://blog.csdn.net/yeiweilan/article/details/73412438

放入元素，如果发生冲突，就往后找没有元素的位置；在这里插入图片描述平方探测再散列

如果发生冲突，放到(冲突+1平方)的位置，如果还发生冲突，就放到(冲突-1平方)的位置；如果还有人就放到(冲突+2平方)的位置，以此类推，要是负数就倒序数。在这里插入图片描述优点

记录更容易进行序列化操作如果记录总数可以预知，可以创建完美的哈希函数，尽量避免hash冲突，提高效率；缺点扩容成本太高；使用探测序列，造成额外计算时间；删除的时候需要设置删除标记，造成额外的空间和操作； 2. 拉链法

在这里插入图片描述如果发生冲突，就继续往前一个元素上链接，形成一个链表，Java的hashmap就是这种方法。

优点

对于记录总数频繁可变的情况处理的较好；结点是动态分配，不会造成内存的浪费；删除记录比较方便，可是直接通过指针操作；缺点存储的记录是随机分布在内存中的，跳转访问时会带来额外的开销；由于使用指针，记录不容易进行序列化操作； 3. 再哈希

如果发生冲突，就用另一个方法计算hashcode，两次结果值不一样就不会发生hash冲突；

4. 建立公共溢出区

将哈希表分为基本表和溢出表两部分，范式和基本表发生冲突的元素，一律填入溢出表。

【本文地址】

公司简介

联系我们