特殊的线性表存储结构--散列表(HashTable)

散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组烟花而来。可以说，如果没有数组，就没有散列表。

结构：

key：数据的键或者叫关键字；
value：存入数组中的数据；
散列函数：把键(key)转化为数组下标的映射方法；
散列值：通过散列函数计算得到的值；

散列函数

顾名思义，他就是一个函数，可以定义为hash(key)，其中key表示元素的键值，hash(key)的值表示经过散列函数计算得到的散列值
设计一个散列函数的基本要求
-散列函数计算得到的散列值是一个非负整数；
-如果key1 = key2，那hash(key1) == hash(key2)；
-如果key1 ≠ key2，那hash(key1) ≠ hash(key2)；

散列冲突

再好的散列函数也无法避免散列冲突。常用的散列冲突解决方法有两类，开放寻址法和链表法

1、开放寻址法(如：ThreadLocalMap)

插入：当我们往散列表中插入数据时，如果某个数据经过散列函数散列后，存储位置已经被占用了，我们就从当前位置开始，依次往后查找，看是否有控线位置，直到找到为止。
查找：通过散列函数求出要查找元素的键值对应的散列值，然后比较数组中下标为散列值得元素和要查找的元素。如果相等，则说明就是我们要找的元素；否则就顺序往后一次查找。如果遍历到数组中的空闲位置，还没有找到，就说明要查找的元素并没有在散列表中。
删除：将删除的元素，特殊标记为deleted。当线性探测查找的时候，遇到标记为deleted的空间，并不是停下来而是继续往下探寻
优点：散列表中的数据都存储在数组中，可以有效的利用CPU缓存加快查询速度。而且，这种方法实现的散列表，序列化起来比较简单。
存在问题：当散列表中插入的数据越来越多时，散列冲突发生的可能性就会越来越大，空闲位置会越来越少，线性探测的时间就会越来越久。极端情况下，我们可能需要探测整个散列表，所以最坏情况下的时间复杂度为O(n)。同理在删除和查找时，也有可能会线性胎侧整张散列表，才能找到要查找或者删除的数据。
所以说当数据量比较小，装载因子小的时候，适合采用开放寻址法。这也是ThreadLocalMap使用开放寻址法解决散列冲突的原因。

2、链表法(如：LinkedHashMap)

链表法是一种更加常用的散列冲突解决办法。当插入的时候，只需要通过散列函数计算出对应的散列槽位，将其插入到对应链表中即可，所以插入的时间复杂度是O(1)。当查找、删除一个元素时，我们同样通过三连函数计算出对应的槽，然后遍历链表查找或者删除。
优点：链表法对内存的利用率比开放寻址法要高。因为链表结点可以在需要的时候再创建，并不需要像开放寻址法那样事先申请好。链表法比起开放寻址法，对大装载因子的容忍度更高。只要散列函数的值随机均匀，即便装载因子编程10，也就是链表的长度变长而已，虽然查找效率有所下降，但是比起顺序查找还是快很多。
存在问题：链表因为要存储指正，所以对于较小的对象的存储，是比较消耗内存的，还有可能会让内存的消耗翻倍。而且，因为链表中的结点是零散分布在内存中的，不是连续的，所以对CPU缓存是不友好的，这方面对于执行效率也有一定的影响。但如果我们存储的是大对象，指针的内存消耗就可以忽略了。
所以说基于链表的散列冲突处理方法比较适合存储大对象，大数据量的散列表，而且，比起开放寻址法，他更加灵活，支持更多的优化策略，比如用红黑树替代链表。

装载因子

当散列表中空闲位置不多的时候，散列冲突的概率就会大大提高。为了尽可能保证散列表的操作效率，一般情况下，我们会尽可能保证散列表中有一定比例的空闲槽位。我们用装载因子来表示空位的多少。
装载因子的计算公式是：
散列表的装载因子 = 填入表中的元素个数 / 散列表的长度

散列函数

是把键(key)转化为数组下标的映射方法，所以散列函数设计的好坏，决定了散列表冲突的概率大小，也直接决定了散列表的性能。

所以设计一个散列函数最好满足这两点：

-散列函数的设计不能太复杂：过于复杂的散列函数，势必会消耗很多计算时间，也就间接的影响到散列表的性能；
-散列函数生成的值要尽可能随机并且均匀分布：这样才能避免或者最小化散列冲突，而且即便出现冲突，散列到每个槽里的数据也会比较平均，不会出现某个槽内数据特别多的情况。