散列表（哈希表）

散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。（散列表）

值得注意的是： 

1. 我们所用的散列表一般都是经过一系列的封装的，散列函数也是散列表重要的一部分
2. 哈希表是一种数据结构 ，原理是数组加工而来的

散列函数：指将哈希表中元素的关键键值映射为元素存储位置的函数

哈希冲突函数：由于新产生的映射仍有可能发生冲突（即非同义词冲突），所以哈希冲突函数通常有多个。哈希冲突即关键字不同的元素被映射到了同一个内存位置，包括由同义词冲突和非同义词冲突。

键值对：（key-value）

• 哈希表存储的就是键值对
• key是键值，value是hash值

散列表如何存储数据： 

当两个键值通过哈希函数计算出来的值相同时那么就要处理哈希冲突

 处理哈希冲突：

1. 开放寻址法：当计算的值已经存在时那么就继续在后面找空的空间

1. 拉链法：在哈希列表中的每一个元素中加一个指针，这个指针就用来存储相同的值的地址

哈希表的扩容：

 当哈希表的存储率达到一定值时，就会开启扩容机制，哈希表的数组将会扩大两倍，值得注意的是：扩容之后要利用新的hash函数将扩容之前的哈希表转移到扩容之后的hash表中

哈希表的遍历：（拉链法）

当我们现在要通过key: 111来查找Entry 的 value 时，怎么操作呢？我们首先通过键值 key 利用哈希函数得出位置1（数组下标），然后我们就去位置1拿数据，拿到这个Entry之后我们得看看这个Entry的key是不是我们要找的111，如果是110，这不是我们要的key，然后根据这个Entry的next知道下一个的位置，再比较key，如果是111，那么就找到了。