We all make choices in life. The hard thing is to live with them. 人一生要做很多选择，最困难的是要带着自己的选择生活下去。
本文主要分享的散列表的定义以及它的两种实现。一种是线性探测；一种是拉链法。所有源码均已上传至github:
定义
我们先假设一下，如果所有的值都是小整数，那么，我们可以用一个数组来实现这样一个无序的符号表，并且将键作为数组的索引，那数组中键key处所存储的就是它所对应的值value，这就是散列表。
散列表也叫哈希表。
三个条件
总体来讲，一个优秀的散列方法需要满足三个条件：
- 一致性---等价的键比如产生相等的散列值
- 高效性---计算起来要简便，不能设计的太复杂
- 均匀性---散列函数生成的值要尽可能的随机并且均匀分布
举例
散列表的应用非常广泛，业界的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
您的点赞和关注是对我最大的支持，谢谢！