散列表的两种实现

We all make choices in life. The hard thing is to live with them. 人一生要做很多选择，最困难的是要带着自己的选择生活下去。

本文主要分享的散列表的定义以及它的两种实现。一种是线性探测；一种是拉链法。所有源码均已上传至github:

github.com/chaoaiqi/st…

定义

我们先假设一下，如果所有的值都是小整数，那么，我们可以用一个数组来实现这样一个无序的符号表，并且将键作为数组的索引，那数组中键key处所存储的就是它所对应的值value，这就是 散列表 。

散列表也叫哈希表。

三个条件

总体来讲，一个优秀的散列方法需要满足三个条件：

1. 一致性---等价的键比如产生相等的散列值
2. 高效性---计算起来要简便，不能设计的太复杂
3. 均匀性---散列函数生成的值要尽可能的随机并且均匀分布

举例

散列表的应用非常广泛，业界的MD5，SHA,CRC等哈希算法；Redis的有序集合；java的LinkedHashMap，hashCode()。

散列冲突

金无足赤，人无完人。再好的散列函数也无法避免散列冲突。那究竟该如何解决散列冲突问题呢？

常用的散列冲突解决方法有两类：

• 链表法
• 开放寻址法

链表法 的核心思想是，在散列表中，每个“桶（bucket）”或者“槽（slot）”会对应一条链表，所有散列值相同的元素我们都放到相同槽位对应的链表中。

优点： 对内存利用率比较高，链表节点可以在需要的时候创建。对大装载因子的容忍度更高，只要散列函数的值随机均匀，即便装载因子变成 10，也就是链表的长度变长了而已，虽然查找效率有所下降，但是比起顺序查找还是快很多。

缺点： 因为链表要存储指针，所以对于比较小的对象的存储，是比较消耗内存的，还有可能会让内存的消耗翻倍。而且，因为链表中的结点是零散分布在内存中的，不是连续的，所以对 CPU 缓存是不友好的，这方面对于执行效率也有一定的影响。

开放寻址法 的核心思想是，如果出现了散列冲突，就重新探测一个空闲位置，将其插入。

优点： 开放寻址法不像链表法，需要拉很多链表。散列表中的数据都存储在数组中，可以有效地利用 CPU 缓存加快查询速度。而且，这种方法实现的散列表，序列化起来比较简单。链表法包含指针，序列化就不是很容易。

缺点： 用开放寻址法解决冲突的散列表，删除数据的时候比较麻烦，需要特殊标记已经删除掉的数据。而且，在开放寻址法中，所有的数据都存储在一个数组中，比起链表法来说，冲突的代价更高。所以，使用开放寻址法解决冲突的散列表，装载因子的上限不能太大。这也导致这种方法比链表法更浪费内存空间。

总结：当数据量比较小、装载因子小的时候，适合采用开放寻址法。存储大对象、大数据量的散列表，适合采用链表法。

实现

开发寻址法（以线性探测为例）

两个构造方法

小哈希算法

扩容

put方法，当存的键值对的数量大于容器的一半的时候，扩容。

第一个for循环是，先查找key是否存在，如果不存在，则存入value数组

get方法，根据key查找value

delete方法

delete方法是线性探测法里比较难的，第一个while循序用来查找key的位置，然后需要将簇中被删除的key的右侧的所有key重新插入到散列表中，这个过程比想象的要复杂的多。

keys方法

测试结果

在实现链表法之前先简单的实现了一个顺序查找的无序链表

keys方法

get方法

put方法

测试结果

链表法（以拉链法为例）

初始化有参构造方法

get，put方法

测试结果

end

您的点赞和关注是对我最大的支持，谢谢！