本章为 《HashMap全B站最细致源码分析课程》 + 拉钩教育HashMap 学习笔记

1. HashMap的数据结构

数据结构中有数组和链表来实现对数据的存储，但这两者基本上是两个极端。

1. 数组

• 在生成数组的时候数组的长度是固定的，在增加元素时常常会遇到长度不足的问题，此时就需要进行扩容——生成一个更长的数组，并将原数组中所有元素复制到新数组中，这个过程是很消耗资源的，故插入操作比较困难。
• 数组存储区间是连续的，占用内存严重，故空间复杂的很大。
• 数组的二分查找时间复杂度小，为O(1)；
• 数组的特点是：寻址容易，插入和删除困难；

2. 链表

• 链表存储区间离散，占用内存比较宽松，故空间复杂度很小，
• 查询时必须从头节点一个个向后查询，时间复杂度很大，达O（N）。
• 链表的特点是：寻址困难，插入和删除容易。

3. 哈希表

• 哈希表（(Hash table）既满足了数据的查找方便，同时不占用太多的内容空间，使用也十分方便，哈希表有多种不同的实现方法，我接下来解释的是最常用的一种方法—— 拉链法，我们可以理解为“链表的数组” ，如图：

• 从上图我们可以发现哈希表是由数组+链表组成的，一个长度为16的数组中，每个元素存储的是一个链表的头结点。
• HashMap里面实现一个静态内部类Entry，其重要的属性有 key , value, next，从属性 key,value 我们就能很明显的看出来Entry就是HashMap键值对实现的一个基础bean，
• HashMap其实也是一个线性的数组实现的，这个数组就是Entry[]，Map里面的内容都保存在Entry[]里面。
• 一般情况下存储规则为： hash(key)%len，也就是元素的key的哈希值对数组长度取模得到

3.1 Hash

• 理论：Hash 也称散列表, 基本原理就是把任意长度的输入，通过Hash变成固定长度的输出。这个映射规则对应的就是 Hash算法，而原始数据映射后的二进制串就是哈希值

---

• 特点：

• 从 Hash值 不能反向推导出原始数据
• 输入数据的微小变化，会得到完全不一样的hash值。相同数据的得到的hash值完全一样
• Hash 算法执行效率高
• Hash 算法冲突概率较小

---

• 由于 Hash 的原理是将输入空间的值映射到Hash空间内， 而由于Hash空间远小于输入空间，根据抽屉原理，一定会存在不同输入空间的值映射到相同的hash空间的情况