前言

          内容为 HashMap 底层探究

一、概念

1. 哈希表也叫做散列表，存放键值对（key-value）也叫做entry，一个值对应另一个值，是一个数据结构，可以根据key来直接访问数据，查找速度快。例如，a对应b，a就映射到b，其中a就是key（关键值），b是value（哈希值）
2. 哈希表本质上是一个数组，底层实现是一个数组，在数组基础上进行加工得到哈希表。
3. 哈希表是根据key值经过哈希函数得到另一个值（数组下标）进而确定entry放在数组中的位置。

二、哈希表的实现

1. 两种方式，一种是数组+链表，另一种是数组+二叉树，链表和二叉树都是用来解决哈希冲突的，用链表和二叉树存储冲突的数据。
2. 散列函数：给一个值通过散列函数加工得到另一个值。例如，101 -> 散列函数 -> 1，其中101是key。哈希表通过将关键值（key）通过散列函数加工处理得到一个新的值，这个新的值就是数据要存放的位置（数组下标），可以根据这个值快速找到存放的数据。

三、解决哈希冲突

1. 开放寻址法

   • 扩容：开放寻址法位置被占用一直往后面找，不存在一直找不到一个空的位置的情况，因为存在自动扩容产生新的位置。当哈希表被占用的位置较多时，出现哈希冲突的概率就会变大，有必要扩容。
   • 增长因子：已经被占用的位置达到总位置的一个百分比，0.7就会自动扩容，比如一共有10个位置，现在已经占了7个位置就会触发扩容机制（新创建一个数组是原数组的2倍，将原数组的所有entry重新通过哈希函数hash一遍放到新的数组上，原数组上的entry对应的下标在新数组中可能会发生改变，因为哈希函数跟数组的size有关，扩容之后数组的size发生改变进而hash之后得到的数组下标可能也会发生改变）。HashMap中当它当前的容量占总容量的75%时就需要扩容。

2. 拉链法

   • 当冲突较多时会出现链表过长的情况，Java中HashMap解决的方法为当冲突的数据数量>=8时链表的结构就会转成二叉树结构（从纵向发展转换为横向发展）进而解决链表过长的问题，当冲突的数据数量<=6时，树结构会还原成链表的结构，7作为一个过渡值是为了避免频繁进行树结构和链表结构的转换，频繁转换会影响性能。

四、哈希表读取数据

1. 拉链法：通过key经过哈希函数找到对应的下标，如果存在，然后依次比较链表上的每个entry中的value是否与查找的value相等。
2. 开放寻址法：通过key经过哈希函数找到对应的下标，然后依次往后找数组中每个entry中的value是否与查找的value相等。