什么是散列表

散列表又被称为哈希表，包含一个键key、一个值value它们之间的对应关系是一对一，散列表就提供了键key和值value的对应关系，基本结构如下。

键值不会重复所以通过键就可以找到与之对应的值，一般散列表查询的时间复杂度为O(1)，那么为什么散列表会这么快呢？

哈希函数

在分析原因之前我们需要知道散列表其存储底层是数组，正是利用了数组下标获取元素效率高的特点，但我们需要注意的是数组下标是整型，而散列表的键值可不一定是整型，为什么散列表还能通过键高效获取值呢？这就需要聊到哈希函数，所谓的哈希函数就是将散列表的键转换为存储数组的下标，再通过下标获取散列表的值，获取过程如下。

哈希函数如何实现

那么哈希函数如何实现呢？每个语言会有自己的计算逻辑，这里以JAVA为例。如果想要自己设计一个哈希函数第一步是需要取到每个键唯一且为整数的标识，在JAVA中有这种功能的函数被称为hashCode方法，是每个对象唯一的标识，所以键对应的哈希函数就可以采用如下逻辑（JAVA中必然不可能如此简单还会通过一系列的位运算提升效率，这里只是简单讨论）。

// key.hashCode()调用键的hashCode方法得到唯一的int值
// arr.length表示散列表底层数组的长度
int index = key.hashCode()%arr.length;

哈希碰撞

无论多好的哈希函数都避免不了的一个问题就是，两个不相同的哈希值可能计算出来的数组下标为同一个。

假设数组长度为6，需要放入两个键key1和key2，key1的hashCode值为3，key2的hashCode值为9，那么通过与数组长度模运算得到两个数组下标都是3，如果按照数组的存储方式，后面存储的必然会把前面存储的值覆盖，这种场景被称为哈希碰撞。

为解决哈希碰撞提出了两种方法，分别为链表法和开放寻址法。

开放寻址法

开放寻址法其原理就是，当存储元素的键下标被占用时，自动查找下一个空挡位置存放值，如下

存在一个元素Entry2，计算其数组下标为2，也就是Entry3的位置，计算出来的数组下标被占用，那么就往下查找下一个元素但是被Entry4占用，再去查找为空的位置，直到查找到数组下标为4的位置，插入元素保存即可。

这种方法在JAVA中的经典应用就是ThreadLocal~

链表法

链表法就是将散列表由单纯的数组存储改为数组+链表组合的形式存储，每个数组中的元素都可以理解为链表的头节点，当需要存储元素时，先判断该下标元素是否为空如果为空之间作为头节点插入，如果不为空则将该数组下标元素头节点指向需要插入的元素。

JAVA中的HashMap就是采用的链表法来解决哈希冲突，当然链表法不是万无一失，当链表过长那么检索的效率必然降低因为链表检索需要遍历链表，时间复杂度为O(n)，所以HashMap中还会涉及到扩容，扩容后将所有的元素重新哈希，以此来达到缩短链表长度的目的。