hash冲突的4种解决方案

原文网址：hash冲突的4种解决方案_IT利刃出鞘的博客-CSDN博客

简介

解决hash冲突（哈希冲突）有以下四种方法：

1. 链地址法
2. 再哈希法
3. 建立公共溢出区
4. 开放定址法

法1：链地址法

对于相同的哈希值，使用链表进行连接。（HashMap使用此法）

优点

1. 处理冲突简单，无堆积现象。即非同义词决不会发生冲突，因此平均查找长度较短；
2. 适合总数经常变化的情况。（因为拉链法中各链表上的结点空间是动态申请的）
3. 占空间小。装填因子可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计
4. 删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。

缺点

1. 查询时效率较低。（存储是动态的，查询时跳转需要更多的时间）
2. 在key-value可以预知，以及没有后续增改操作时候，开放定址法性能优于链地址法。
3. 不容易序列化

法2：再哈希法

上边是文章的部分内容，为便于维护，全文已迁移到此网址：hash冲突的4种解决方案 - 自学精灵

hash冲突的4种解决方案

原文网址：hash冲突的4种解决方案_IT利刃出鞘的博客-CSDN博客

简介

解决hash冲突（哈希冲突）有以下四种方法：

1. 链地址法
2. 再哈希法
3. 建立公共溢出区
4. 开放定址法

法1：链地址法

对于相同的哈希值，使用链表进行连接。（HashMap使用此法）

优点

1. 处理冲突简单，无堆积现象。即非同义词决不会发生冲突，因此平均查找长度较短；
2. 适合总数经常变化的情况。（因为拉链法中各链表上的结点空间是动态申请的）
3. 占空间小。装填因子可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计
4. 删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。

缺点

1. 查询时效率较低。（存储是动态的，查询时跳转需要更多的时间）
2. 在key-value可以预知，以及没有后续增改操作时候，开放定址法性能优于链地址法。
3. 不容易序列化

法2：再哈希法

上边是文章的部分内容，为便于维护，全文已迁移到此网址：hash冲突的4种解决方案 - 自学精灵