HashMap实现原理分析

• hash概念
• HashMap概念
• • • 概念
    • 数据结构
• HashMap的基本存储原理和工作原理
• • • HashMap的基本存储原理以及存储内容的组成
    • HashMap的工作原理以及存取方法过程
• HashMap具体分析
• • • HashMap具体的存取过程
    • HashMap中的碰撞探测(collision detection)以及碰撞的解决方法
    • HashMap扩容机制（如何调整HashMap的大小）
    • HashMap扩容可能存在的问题

hash概念

hashing(散列法或哈希法)的概念

散列法（Hashing）是一种将字符组成的字符串转换为固定长度（一般是更短长度）的数值或索引值的方法，称为散列法，也叫哈希法。由于通过更短的哈希值比用原始值进行数据库搜索更快，这种方法一般用来在数据库中建立索引并进行搜索，同时还用在各种解密算法中。

HashMap概念

概念

HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作，并允许使用null值和null键。HashMap储存的是键值对，HashMap很快。此类不保证映射的顺序，特别是，它不保证该顺序恒久不变。

HashMap在Map体系中的位置：

数据结构

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的工作原理以及存取方法过程

HashMap的工作原理 ：HashMap是基于散列法（又称哈希法hashing）的原理，使用put(key, value)存储对象到HashMap中，使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时，我们先对键调用hashCode()方法，返回的hashCode用于找到bucket（桶）位置来储存Entry对象。”HashMap是在bucket中储存键对象和值对象，作为Map.Entry。并不是仅仅只在bucket中存储值。

HashMap具体分析

HashMap具体的存取过程

put键值对的方法的过程是（本图转自美团）：

①.判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；

②.根据键值key计算hash值得到插入的数组索引 i ，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③；

③.判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals；

④.判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；

⑤.遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；

⑥.插入成功后，判断实际存在的键值对数量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()方法进行查找。由于之前添加时已经保证这个树是有序的，因此查找时基本就是折半查找，效率很高。

5、如果对比节点的哈希值和要查找的哈希值相等，就会判断 key 是否相等，相等就直接返回；不相等就从子树中递归查找。

HashMap中直接地址用hash函数生成；解决冲突，用比较函数解决。如果每个桶内部只有一个元素，那么查找的时候只有一次比较。当许多桶内没有值时，许多查询就会更快了(指查不到的时候)。

HashMap中的碰撞探测(collision detection)以及碰撞的解决方法

1、当两个对象的hashcode相同时，会发生什么？

当两个对象的hashcode相同时，它们的bucket位置相同，‘碰撞’会发生。因为HashMap使用LinkedList存储对象，这个Entry(包含有键值对的Map.Entry对象)会存储在LinkedList中。这两个对象就算hashcode相同，但是它们可能并不相等。

2、当两个对象的hashcode相同时，那如何获取这两个对象的值呢？

当两个对象的hashcode相同时，我们调用get()方法，HashMap会使用键对象的hashcode找到bucket位置，遍历LinkedList直到找到值对象。找到bucket位置之后，会调用keys.equals()方法去找到LinkedList中正确的节点，最终找到要找的值对象使用不可变的、声明作final的对象，并且采用合适的equals()和hashCode()方法的话，将会减少碰撞的发生，提高效率。不可变性使得能够缓存不同键的hashcode，这将提高整个获取对象的速度，使用String，Interger这样的wrapper类作为键是非常好的选择。

HashMap扩容机制（如何调整HashMap的大小）

扩容(resize)就是重新计算容量，向HashMap对象里不停地添加元素，而HashMap对象内部的数组无法装载更多的元素时，对象就需要扩大数组的长度，以便能装入更多的元素。

HashMap的一个实例有两个影响其性能的参数： 初始容量和负载因子。 容量是哈希表中的桶数，初始容量只是创建哈希表时的容量。 负载因子是在容量自动增加之前允许哈希表得到满足的度量。 当在散列表中的条目的数量超过了负载因数和电流容量的乘积，哈希表被重新散列（即，内部数据结构被重建），使得哈希表具有桶的大约两倍。

作为一般规则，默认负载因子（0.75）提供了时间和空间成本之间的良好折中。 更高的值会降低空间开销，但会增加查找成本（反映在HashMap类的大部分操作中，包括 get 和 put ）。在设置其初始容量时，应考虑 Map 中预期的条目数及其负载因子，以便最小化重新组播操作的数量。 如果初始容量大于最大条目数除以负载因子，则不会发生重新排列操作。

HashMap扩容可能存在的问题

当重新调整HashMap大小的时候，在多线程的情况下，可能存在条件竞争(race condition)，因为如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的bucket位置的时候，HashMap并不会将元素放在链表的尾部，而是放在头部，这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了，那么就死循环了。

参照：

http://www.importnew.com/7099.html

https://blog.csdn.net/excellentyuxiao/article/details/52344819