详细介绍 HashMap底层原理 _链表

数组：其实所谓的数组指的就是一组相关类型的变量集合，并且这些变量彼此之间没有任何的关联。存储区间连续，占用内存严重，数组有下标，查询数据快，但是增删比较慢；
链表：一种常见的基础数据结构，是一种线性表，但是不会按照线性的顺序存储数据，而是每一个节点里存到下一个节点的指针。存储区间离散，占用内存比较宽松，使用链表查询比较慢，但是增删比较快；
哈希表：Hash table 既满足了数据的快速查询（根据关键码值key value 而直接进行访问的数据结构），也不会占用太多的内存空间，十分方便。哈希表是数组加链表组成。
结构及原理
是基于哈希表的Map接口的非同步实现。实现对数据的操作，允许有一个null键，多个null值。
底层就是一个数组结构，数组中的每一项又是一个链表。数组+链表结构，新建一个的时候，就会初始化一个数组。Entry就是数组中的元素，每个Entry其实就是一个key-value的键值对，它持有一个指向下一个元素的引用，这就构成了链表，底层将key-value当成一个整体来处理，这个整体就是一个Entry对象。底层采用一个Entry【】数组来保存所有的key-value键值对，当需要存储一个Entry对象时，会根据hash算法来决定在其数组中的位置，在根据方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry对象时，也会根据hash算法找到其在数组中的存储位置，在根据方法从该位置上的链表中取出Entry;
的存储
put：（key-value）方法是中最重要的方法，使用最主要使用的就是put，get两个方法。
判断键值对数组table[i]是否为空或者为null，否则执行（）进行扩容；根据键值key计算hash值得到插入的数组索引 i ,如果table[i] == null，直接新建节点添加即可，转入6，如果table[i] 不为空，则转向3；判断table[i] 的首个元素是否和key一样，如果相同（和）直接覆盖value，否则转向4；判断table[i] 是否为，即table[i]是否为红黑树，如果是红黑树，则直接插入键值对，否则转向5；遍历table[i] ,判断链表长度是否大于8，大于8的话把链表转换成红黑树，进行插入操作，否则进行链表插入操作；便利时遇到相同key直接覆盖value；插入成功后，判断实际存在的键值对数量size是否超过了，如果超过，则扩容；

文章插图
看一下put源码
get方法取值过程：
int hash = key.（）；
int index = hash%Entry[].;
指定key通过hash函数得到key的hash值；调用内部方法（），得到桶号（一般为hash值对桶数求摸）；比较桶的内部元素是否和key相等，如不相等，则没有找到，相等，则取出相等记录的value；如果得到key所在桶的头结点恰好是红黑树节点，就调用红黑树节点的（）方法，否则就遍历链表节点。（）方法通过调用树形节点的find（）方法进行查找。由于之前添加时已经保证这个树是有序的，因此查找时基本就是折半查找，效率高；如果对比节点的哈希值和要查找的哈希值相等，就会判断key是否相等，相等就直接返回；不相等就从子树中递归查找；
中直接地址用hash函数生成，冲突用比较函数解决。如果每个桶内部只有一个元素，那么查找的时候只有一次比较。当许多桶内没有值得时候，许多查询就会更快
方法
添加新元素前，判断是否需要对map的数组进行扩容，如果需要扩容，则扩容多大？对于新增key-value键值对，如果可以的hash值相同，则构造单向列表；
源码分析：