数组还有晋级版？

我们都知道数组，数组之所以查询速度快，可以通过数组的下标获取数组中的数据，这是因为它支持下标随机访问，那么我们是不是也可以也可以做出来一个类似数组的存储空间，这也就是今天要谈到的散列表。

散列思想

散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展。查询效率接近O(1)，跟散列函数、装载因子、散列冲突等有关系。

散列函数

我们可以把这个定义为hash(key)，key 表示元素的键值，hash(key)表示经过散列函数计算得到的散列值。

散列函数设计的基本要求：

1. 散列函数计算得到的散列值是一个非负整数
   
2. 如果 key1 = key2, 那么 hash(key1) == hash(key2)；
   
3. 如果 key1 != key2, 那么 hash(key1) != hash(key2)；
   

散列冲突

装载因子

用来表示散列表中空位的多少。散列表的装载因子 = 填入表中的元素个数 / 散列表的长度，装载因子越大说明空闲位置越少，冲突越多，散列表的性能会下降。

1、开放寻址法

如果出现了散列冲突，我们就重新探测一个空闲位置，将其插入 。

优点

1. 散列表的数据存在数组中，可以利用CPU缓存加快查询速度。
   
2. 开放寻址法没有指针，序列化起来也比较简单。
   

缺点

1. 删除数据比较麻烦，需要添加删除标记
   
2. 所有的数据在存储在一个数组中，冲突出现的几率比较大。
   

使用场景

当数据量比较小、装载因子小的时候，可以使用采用开放寻址法，这也是Java中的ThreadLocalMap使用开放寻址法解决散列冲突的原因。

1.1 线性探测

当我们往散列表中插入数据时，如果某个数据经过散列函数散列之后，存储位置已经被占用了， 我们就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。删除时比较特别，如果这个空闲位置是我们后来删除的，就会导致原来的查找算法失效，我们可以将删除的元素，特殊标记为 deleted。当线性探测查找的时候，遇到标记为 deleted 的 空间，并不是停下来，而是继续往下探测。线性探测法其实存在很大问题。当散列表中插入的数据越来越多时，散列冲 突发生的可能性就会越来越大，空闲位置会越来越少，线性探测的时间就会越来越久。极端情况 下，我们可能需要探测整个散列表，所以最坏情况下的时间复杂度为 O(n)。

1.2 二次探测

线性探测每次探测的步长是 1 ，二次探测探测的步长就变成了原来的“二次方”，也就是说，它探测的下标序列就是 hash(key)+0，hash(key)+1^2，hash(key)+2^2 ……

1.3 双重散列

使用一组散列函数 hash1(key)， hash2(key)，hash3(key)……我们先用第一个散列函数，如果计算得到的存储位置已经被占用， 再用第二个散列函数，依次类推，直到找到空闲的存储位置。

2、链表法

在散列表中每个“槽”会对应一条链表，所有散列值相同的元素我们放在相同的槽位对应的链表中。插入数据的时间复杂度为O(1)，查找和删除的时间复杂度跟链表的长度 k 有关，也就是O(K)，当散列表比较均匀时，理论上 k=n/m，其中 n 表示散列表中数据的个数，m 表示散列表中“槽”的个数。当所有的元素集中到一个链表中时，散列表就会退化成链表，查询时间会退化成O(n)

优点

1. 对内存的利用率比开放寻址法更高，链表节点可以在用的时候创建，不需要事先创建。
   
2. 链表法对装载因子的容忍度更高，装载因子变大以后，链表的长度无限制，虽然查找效率有所下降，但是还是比顺序查找还要快。
   

缺点

1. 链表需要额外的空间存储指针，如果对象占用的存储空间比存储指针的空间还要小时，这就要浪费多余的空间。
   
2. 链表的结点在内存上不是连续的，所以对CPU缓存是不友好的。
   

使用场景

如果存储大对象，大数据量的散列时，比开放寻址法显得更加灵活。链表法还可以改造，这个链表可以更改成跳表或者红黑树。

如何设计散列函数

1. 散列函数的设计不能太复杂，复杂的函数影响散列表的性能
   
2. 散列函数生成的值要尽可能随机并且均匀分布，避免散列冲突
   

装载因子过大

1. 在能确定元素数量的情况下，可以申请一个容量合适的散列表，设计哈希值重复少的散列函数。
   
2. 在事先无法确定元素数量的情况下，就要构建一个能扩容的动态散列表。散列表随着元素的变多，散列冲突出现的概率会越来越大，当装载因子达到一个阈值时，这时候就要考虑扩容了。
   

这种扩容机制类似于的集合的动态扩容，但是复杂度要比集合高，更换新的散列表，需要重新计算元素的键值，大量元素的迁移需要耗费太多的时间，迁移元素的时间复杂度为O(n)，正常插入数据的时间复杂度为O(1)，那么算下的均摊时间复杂度为O(1)，这个时间复杂度在理论上是比较好的。但是这里有一个问题，在实际操作过程中，扩容会在某次插入元素时进行，假如要迁移的元素有几百万甚至上千万，那么这次插入操作的耗时将是十分漫长的，那么是不是有更优雅的方法解决问题呢？

方法还是有的，这时候我们可以是不是可以把均摊的思想运用到实际操作过程中，当散列表达到装载因子的阈值时，我们申请一个新的散列表，然后重点来了～这时候不急着把所有数据移动到新的散列表中，我们可以分批移动，比如当每次插入新数据时，我们移动一小部分，这样在任何情况下，我们插入一个数据的时间复杂度都会差不多，不会出现一次特别慢的情况。

散列表实例

Java中的 HashMap 实现

初始大小

HashMap 默认的初始化大小是16，如果事先我们知道数据量的大小，可以设定默认初始化时的大小，减少动态扩容的次数，提高效率。

装载因子和动态扩容

最大装载因子默认是 0.75，当装载因子超过这个值时，就会启动扩容，每次扩容都会扩容为原来的两倍大小。

散列冲突解决方法

HashMap 底层使用链表法解决冲突，在JDK1.8 版本后，引入了红黑树，当链表的长度超过 8 时，链表转换为红黑树。当红黑树结点个树少于8个的时候，红黑树转化为链表。