HashMap扩容机制深度解析

HashMap原理的深入理解 HashMap是基于哈希表的Map接口的非同步实现，提供了所有可选的映射操作，并允许使用null值和null键。HashMap储存的是键值对，HashMap很快。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。 HashMap的底层结构是一个“链表散列”的数据结构，即数组和链表的结合体。数组：存储区间连续，占用内存严重，寻址容易，插入删除困难；链表：存储区间离散，占用内存比较宽松，寻址困难，插入删除容易。HashMap综合应用了这两种数据结构，实现了寻址容易，插入删除也容易。 HashMap的基本存储原理是先声明一个下标范围比较大的数组来存储元素。另外设计一个哈希函数（也叫做散列函数）来获得每一个元素的Key（关键字）的函数值（即数组下标，hash值）。数组存储的元素是一个Entry类，这个类有三个数据域，key、value（键值对），next（指向下一个Entry）。例如，第一个键值对A进来。通过计算其key的hash得到的index=0。记做：Entry[0] = A。第二个键值对B，通过计算其index也等于0，HashMap会将B.next = A,Entry[0] = B；第三个键值对C,index也等于0，那么C.next = B,Entry[0] = C；这样我们发现index=0的地方事实上存取了A,B,C三个键值对，它们通过next这个属性链接在一起。 HashMap的工作原理是基于散列法（又称哈希法hashing）的原理。使用put(key, value)存储对象到HashMap中，使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时，我们先对键调用hashCode()方法，返回的hashCode用于找到bucket（桶）位置来储存Entry对象。 HashMap的存取过程是： put键值对的方法的过程是： 1. 判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容； 2. 根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥； 3. 判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals； 4. 判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤； 5. 遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作； 6. 插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。 get值方法的过程是： 1. 指定key 通过hash函数得到key的hash值 int hash=key.hashCode(); 2. 调用内部方法 getNode()，得到桶号（一般都为hash值对桶数求模）int index =hash%Entry[].length; 3. 比较桶的内部元素是否与key相等，若都不相等，则没有找到。相等，则取出相等记录的value。 4. 如果得到 key 所在的桶的头结点恰好是红黑树节点，就调用红黑树节点的 getTreeNode() 方法，否则就遍历链表节点。 getTreeNode 方法使通过调用树形节点的 find()方法进行查找。 HashMap的重要特点是使用散列法来解决冲突问题，使用链表和数组结合的数据结构来实现快速的插入和删除操作。HashMap的应用非常广泛，例如在数据库中建立索引，并进行搜索，同时还用在各种解密算法中。