深入探讨源码-HashMap

田维常

发布于 2020-03-25 10:59:33

3250

发布于 2020-03-25 10:59:33

又聊到HashMap了，其实网上已经有很多关乎HashMap的文章了，本文将对HashMap的实现方式和一些关键点进行一一的说明，仅限个人理解，如有疑惑和问题，请联系作者更正。说明：JDK版本1.8.0_151

`HashMap`

Hash表是一个数组+链表的结构，这种结构能够保证在遍历与增删的过程中，如果不产生hash碰撞，仅需一次定位就可完成，时间复杂度能保证在O(1)。在JDK1.7中，只是单纯的数组+链表的结构，但是如果散列表中的hash碰撞过多时，会造成效率的降低，所以在JKD1.8中对这种情况进行了控制，当一个hash值上的链表长度大于8时，该节点上的数据就不再以链表进行存储，而是转成了一个红黑树。

简单使用案例

HashMap常用遍历方式

public class HashMapTest {
    public static void main(String[] args) {
        HashMap<String, String> hashMap = new HashMap<>(4);
        hashMap.put("1", "a");
        hashMap.put("2", "b");
        hashMap.put("3", "c");
        hashMap.put("4", "e");
        //第一种：普遍使用，二次取值
        System.out.println("通过Map.keySet遍历key和value：");
        for (String key : hashMap.keySet()) {
            System.out.println("key= " + key + " and value= " + hashMap.get(key));
        }

        //第二种
        System.out.println("通过Map.entrySet使用iterator遍历key和value：");
        Iterator<Map.Entry<String, String>> it = hashMap.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry<String, String> entry = it.next();
            System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
        }

        //第三种：推荐，尤其是容量大时
        System.out.println("通过Map.entrySet遍历key和value");
        for (Map.Entry<String, String> entry : hashMap.entrySet()) {
            System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
        }

        //第四种
        System.out.println("通过Map.values()遍历所有的value");
        for (String v : hashMap.values()) {
            System.out.println("value= " + v);
        }
        System.out.println("通过Map.keySet()遍历所有的key");
        for (String v : hashMap.keySet()) {
            System.out.println("value= " + v);
        }
    }
}

简单使用已经结束，下面来看看其源码。

`HashMap`类关系

可以看出，HashMap出生于JDK1.2中。

在看看HashMap类图：

下面对这些混个眼熟就行。

Map接口

定义了一堆方法了，还有个Entry接口，其中Entry中也定义了一堆方法

Map有键和值的概念。一个键映射到一个值，Map按照键存储和访问值，键不能重复，即一个键只会存储一份，给同一个键重复设值会覆盖原来的值。使用Map可以方便地处理需要根据键访问对象的场景，比如：

一个词典应用，键可以为单词，值可以为单词信息类，包括含义、发音、例句等；
统计和记录一本书中所有单词出现的次数，可以以单词为键，以出现次数为值；
管理配置文件中的配置项，配置项是典型的键值对；
根据身份证号查询人员信息，身份证号为键，人员信息为值。

数组、ArrayList、LinkedList可以视为一种特殊的Map，键为索引，值为对象。

`AbstractMap`抽象类

关于 Cloneable, Serializable这两个东东这里就不深入讨论，但是肯定回去讨论它们的，只是这里他们不是重点。

`HashMap`概览

回到HashMap中内容大致有这些：

是不是很多呀，看到这里就不想看了吗？坚持咯，这里刚刚开始。

`HashMap`构造函数

//大部分你最喜欢用的构造方法
public HashMap() {
    // all other fields defaulted
   this.loadFactor = DEFAULT_LOAD_FACTOR;
}
//少部分人会使用这个，在初始化的时候就指定HashMap容量
//这里说的容量initialCapacity时数组大小
//在明确map将要存放数据个数时，推荐使用这个
public HashMap(int initialCapacity) {
   this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//用的人就更少了，除了指定容量外，还需要指定加载因子
public HashMap(int initialCapacity, float loadFactor) {
   if (initialCapacity < 0)
      throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
   if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
   if (loadFactor <= 0 || Float.isNaN(loadFactor))
          throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
   this.loadFactor = loadFactor;
   this.threshold = tableSizeFor(initialCapacity);
}
//目前没见过谁在业务代码中使用过
public HashMap(Map<? extends K, ? extends V> m) {
   this.loadFactor = DEFAULT_LOAD_FACTOR;
   putMapEntries(m, false);
}

`HashMap`关键变量

//Node类型的数组，记我们常说的bucket数组，其中每个元素为链表或者树形结构
//被transient修饰的变量是不会被序列化的
transient Node<K,V>[] table;
//HashMap中保存的数据个数
transient int size;
//HashMap需要resize操作的阈值
int threshold;
//负载因子，用于计算threshold。计算公式为：
////临界值=主干数组容量*负载因子
//threshold = loadFactor * capacity
final float loadFactor;

`HashMap`关键常量

 //数组的默认初始长度，java规定hashMap的数组长度必须是2的次方
 //扩展长度时也是当前长度 << 1。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 数组的最大长度
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认负载因子，当元素个数超过这个比例则会执行数组扩充操作。
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 树形化阈值，当链表节点个大于等于TREEIFY_THRESHOLD - 1时，
// 会将该链表换成红黑树。
static final int TREEIFY_THRESHOLD = 8;
// 解除树形化阈值，当链表节点小于等于这个值时，会将红黑树转换成普通的链表。
static final int UNTREEIFY_THRESHOLD = 6;
// 最小树形化的容量，即：当内部数组长度小于64时，不会将链表转化成红黑树，而是优先扩充数组。
static final int MIN_TREEIFY_CAPACITY = 64;

`HashMap`关键内部类

//Node为静态内部类
static class Node<K,V> implements Map.Entry<K,V> {
    //key的hash值,可以避免重复计算    
    final int hash;
    //key
    final K key;
    //value
    V value;
    //指向下一个节点，没有指向上一个节点
    //所以是单向链表
    Node<K,V> next;
    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
}  
//红黑树节点定义
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
   //父节点
   TreeNode<K,V> parent;  
   //左子节点
   TreeNode<K,V> left;
   //右子节点
   TreeNode<K,V> right;
    //前方节点（删除后需要取消链接）
   TreeNode<K,V> prev;  
   //是否红色
   boolean red;
   TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
}

上面的Node静态内部类中的属性next证明了HashMap中的链表是单向链表。另外上面有个Node[] table，这里大致能猜出来，HashMap结构是数组+链表，但是后面又有红黑树。由此推测，当链表过于长的时候，查询效率变低，于是有了红黑树。

数组+链表数组+红黑树

数组

数组具有遍历快，增删慢的特点。数组在堆中是一块连续的存储空间，遍历时数组的首地址是知道的（首地址=首地址+元素字节数 * 下标），所以遍历快（数组遍历的时间复杂度为O(1) ）；增删慢是因为，当在中间插入或删除元素时，会造成该元素后面所有元素地址的改变，所以增删慢（增删的时间复杂度为O(n) ）。

链表

链表具有增删快，遍历慢的特点。链表中各元素的内存空间是不连续的，一个节点至少包含节点数据与后继节点的引用，所以在插入删除时，只需修改该位置的前驱节点与后继节点即可，链表在插入删除时的时间复杂度为O(1)。但是在遍历时，get(n)元素时，需要从第一个开始，依次拿到后面元素的地址，进行遍历，直到遍历到第n个元素（时间复杂度为O(n) ），所以效率极低。

`HashMap`常用方法

put方法

大致分为七步：

根据key计算hash值；
判断是否是第一次加入元素（table是否为空），如果是，则调用resize函数初始化（扩容）：（见下面resize）如果threshold=0，则初始化为16,；如果threshold不为0，初始化为threshold（构造函数中传入加载因子，会给threshold赋值，但是没有初始化table）
根据hash值找到（(n-1)&hash）对应桶的第一个元素；如果第一个元素为空，那么直接插入新节点。
如果第一个元素不为空，则判断结构是不是红黑树，如果是红黑树则调用红黑树插入的方法；
如果不是红黑树，则依次遍历链表，如果链表有和传入的key相同的key,则用新的value替换原来的value，并返回旧value；
如果没有相同的key，则插入到链表的最后。并判断新链表的大小是否超过门限，超过则转换成红黑树。
判断新size是不是大于threshold，是就扩容。

public V put(K key, V value) {
   return putVal(hash(key), key, value, false, true);
}
//HashMap自定义的hash值的计算
//第一点：当key==null时候，返回hash值为0.所以也就只能有一个key可以为0.
//h = key.hashCode()是对Key进行hashCode()
//然后就是用h的高16位与低16位进行异或运算,这么做有何用？后面给出答案
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//参数hash=key的hash值，key/value就不用说，onlyIfAbsent=false,evict=true
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
        //tab 哈希数组，p 该哈希桶的首节点，n hashMap的长度，i 计算出的数组下标
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //第一次put的时候，table使用的是懒加载
        if ((tab = table) == null || (n = tab.length) == 0){
            //关键点：resize（） 扩容
            n = (tab = resize()).length;
        }
        /**
        *如果计算出的该哈希桶的位置没有值，则把新插入的key-value放到此处，
        *此处就算没有插入成功，也就是发生哈希冲突时也会把哈希桶的首节点赋予p
        * i = (n - 1) & hash相当于（n-1）%hash取模
        **/
        if ((p = tab[i = (n - 1) & hash]) == null){
            tab[i] = newNode(hash, key, value, null);
        }
        //发生哈希冲突的几种情况
        else {
            // e 临时节点的作用， k 存放该当前节点的key
            Node<K,V> e; K k;
            //第一种，插入的key-value的hash值，key都与当前节点的相等，e = p，则表示为首节点
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k)))){
                e = p;
            }
            //第二种，hash值不等于首节点，判断该p是否属于红黑树的节点
            else if (p instanceof TreeNode)
                /**为红黑树的节点，则在红黑树中进行添加，如果该节点已经存在，
                * 则返回该节点（不为null），该值很重要，
                * 用来判断put操作是否成功，如果添加成功返回null
                **/
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            //第三种，hash值不等于首节点，不为红黑树的节点，则为链表的节点
            else {
                //遍历该链表
                for (int binCount = 0; ; ++binCount) {
                    //如果找到尾部，则表明添加的key-value没有重复，在尾部进行添加
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, valbinCountue, null);
                        //判断是否要转换为红黑树结构,binCount >=8-1
                        if (binCount >= TREEIFY_THRESHOLD - 1)
                            treeifyBin(tab, hash);
                        break;
                    }
                    //如果链表中有重复的key，e则为当前重复的节点，结束循环
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //有重复的key，则用待插入值进行覆盖，返回旧值。
            if (e != null) {
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        //到了此步骤，则表明待插入的key-value是没有key的重复，因为插入成功e节点的值为null
        //修改次数+1
        ++modCount;
        //实际长度+1，判断是否大于临界值，大于则扩容
        if (++size > threshold){
            //扩容
            resize();
        }
        //用于LinkedHashMap回调，HashMap不处理
        afterNodeInsertion(evict);
        //添加成功
        return null;
}

上面put方法中，第一次put的时候，会涉及到resize，其实后面当存放数据量达到阈值后也会触发resize方法。

hash方法

此处如果传入的int类型的值：

向一个Object类型key赋值一个int的值时，会将int值自动封箱为Integer。
integer类型的hashCode都是他自身的值，即h=key；

h >>> 16为无符号右移16位，低位挤走，高位补0；^ 为按位异或，即转成二进制后，相异为1，相同为0，由此可发现，当传入的值小于 2的16次方-1 时，调用这个方法返回的值，都是自身的值。

当key==null时候，返回hash值为0.所以也就只能有一个key可以为0。

 static final int hash(Object key) {
        int h;
//也就将key的hashCode无符号右移16位然后与hashCode异或从而得到hash值在putVal方法中（n - 1）& hash计算得到桶的索引位置
//注意，这里h是int值，也就是32位，然后无符号又移16位，那么就是折半，折半之后和原来的数据做异或操作，正好整合了高位和低位的数据
//混合原始哈希码的高位和低位，以此来加大低位的随机性,而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
 }

resize方法

可以看出来resize是很重要的。下面把resize方法拿出来看看：

final Node<K,V>[] resize() {
        //把没插入之前的哈希数组做我诶oldTal
        Node<K,V>[] oldTab = table;
        //old的长度
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        //old的临界值
        int oldThr = threshold;
        //初始化new的长度和临界值
        int newCap, newThr = 0;
        //oldCap > 0也就是说不是首次初始化，因为hashMap用的是懒加载
        if (oldCap > 0) {
            //大于最大值
            if (oldCap >= MAXIMUM_CAPACITY) {
                //临界值为整数的最大值
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY){
                //标记##，其它情况，扩容两倍，
                //并且扩容后的长度要小于最大值，old长度也要大于16
                //临界值也扩容为old的临界值2倍
                newThr = oldThr << 1;
            }
        }else if (oldThr > 0) {
            /**如果oldCap<0，但是已经初始化了，
             *像把元素删除完之后的情况，那么它的临界值肯定还存在，        
             * 如果是首次初始化，它的临界值则为0
             **/
            newCap = oldThr;
        }else {              
            //首次初始化，给与默认的值
            newCap = DEFAULT_INITIAL_CAPACITY;
            //临界值等于容量*加载因子
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        //此处的if为上面标记##的补充，也就是初始化时容量小于默认
        //值16的，此时newThr没有赋值
        if (newThr == 0) {
            //new的临界值
            float ft = (float)newCap * loadFactor;
            //判断是否new容量是否大于最大值，临界值是否大于最大值
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        //把上面各种情况分析出的临界值，在此处真正进行改变，
        //也就是容量和临界值都改变了。
        threshold = newThr;
        //初始化
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        //赋予当前的table
        table = newTab;
        //此处自然是把old中的元素，遍历到new中
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                //临时变量
                Node<K,V> e;
                //当前哈希桶的位置值不为null，也就是数组下标处有值，因为有值表示可能会发生冲突
                if ((e = oldTab[j]) != null) {
                    //把已经赋值之后的变量置位null，当然是为了好回收，释放内存
                    oldTab[j] = null;
                    //如果下标处的节点没有下一个元素
                    if (e.next == null)
                        //把该变量的值存入newCap中，e.hash & (newCap - 1)并不等于j
                        newTab[e.hash & (newCap - 1)] = e;
                    //该节点为红黑树结构，也就是存在哈希冲突，该哈希桶中有多个元素
                    else if (e instanceof TreeNode)
                        //把此树进行转移到newCap中
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else {
                        /**此处表示为链表结构，同样把链表转移到newCap中，
                        就是把链表遍历后，把值转过去，在置位null**/
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        //遍历链表，进行分组
                        do {
                            //next指向下一个节点
                            next = e.next;
                            //若e的hash值与旧桶数组长度位与后等于0
                            if ((e.hash & oldCap) == 0) {
                                //若loTail为null，则将loHead指向e
                                if (loTail == null){
                                    loHead = e;
                                }else{
                                    //否则将loTail.next指向e
                                    loTail.next = e;
                                }
                                //loTail指向e，做下一次循环
                                loTail = e;
                            }
                            //若e的hash值与旧桶数组长度位与后不等于0，同上
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                            //一直循环到该链表尾部
                        } while ((e = next) != null);
                        //若loTail不为null
                        if (loTail != null) {
                            loTail.next = null;
                            //将loHead赋给新的桶数组的j位置
                            newTab[j] = loHead;
                        }
                        //若hiTail不为null
                        if (hiTail != null) {
                            hiTail.next = null;
                            //将hiHead赋给新的桶数组的j+oldCap位置
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        //返回新的桶数组
        return newTab;
}

这段代码大致做了两件事情：

计算newCap、newThr，创建新的桶数组
遍历旧的桶数组并将Node节点存储到新的桶数组中

上面的resize就是HashMap的扩容过程。

get方法

get(key)方法时获取key的hash值，计算hash&(n-1)得到在链表数组中的位置first=tab[hash&(n-1)],先判断first的key是否与参数key相等，不等就遍历后面的链表找到相同的key值返回对应的Value值即可

计算key的hash值。
根据hash值找到对应桶的第一个节点。
判断第一个节点是不是（比较hash值和key）。
第一个节点不是就分红黑树和链表继续遍历

tableSizeFor方法

如果cap是2次幂则返回cap，否则将cap转化为一个比cap大且差距最小的2次幂。比如：

cap=3，返回4
cap=5，返回8
cap=16，返回16

   static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

这个方法是在构造函数中使用到。

由此可以看到，当在实例化HashMap实例时，如果给定了initialCapacity，由于HashMap的capacity都是2的幂，因此这个方法用于找到大于等于initialCapacity的最小的2的幂（initialCapacity如果就是2的幂，则返回的还是这个数）。

分析

首先，为什么要对cap做减1操作。int n = cap - 1; 这是为了防止，cap已经是2的幂。如果cap已经是2的幂，又没有执行这个减1操作，则执行完后面的几条无符号右移操作之后，返回的capacity将是这个cap的2倍。如果不懂，要看完后面的几个无符号右移之后再回来看看。下面看看这几个无符号右移操作：如果n这时为0了（经过了cap-1之后），则经过后面的几次无符号右移依然是0，最后返回的capacity是1（最后有个n+1的操作）。这里只讨论n不等于0的情况。第一次右移

n |= n >>> 1;

由于n不等于0，则n的二进制表示中总会有一bit为1，这时考虑最高位的1。通过无符号右移1位，则将最高位的1右移了1位，再做或操作，使得n的二进制表示中与最高位的1紧邻的右边一位也为1，如000011xxxxxx。第二次右移

n |= n >>> 2;

注意，这个n已经经过了n |= n >>> 1; 操作。假设此时n为000011xxxxxx ，则n无符号右移两位，会将最高位两个连续的1右移两位，然后再与原来的n做或操作，这样n的二进制表示的高位中会有4个连续的1。如00001111xxxxxx 。第三次右移

n |= n >>> 4;

这次把已经有的高位中的连续的4个1，右移4位，再做或操作，这样n的二进制表示的高位中会有8个连续的1。如00001111 1111xxxxxx 。以此类推注意，容量最大也就是32bit的正数，因此最后n |= n >>> 16; ，最多也就32个1，但是这时已经大于了MAXIMUM_CAPACITY，所以取值到MAXIMUM_CAPACITY 。

该算法的思想就是使n=cap-1的二进制中，第一个1后面全转为为1。

举一个例子说明下吧。

这个算法着实牛逼啊！

注意，得到的这个capacity却被赋值给了threshold。

this.threshold = tableSizeFor(initialCapacity);

开始以为这个是个Bug，感觉应该这么写：

this.threshold = tableSizeFor(initialCapacity) * this.loadFactor;

这样才符合threshold的意思（当HashMap的size到达threshold这个阈值时会扩容）。

但是，请注意，在构造方法中，并没有对table这个成员变量进行初始化，table的初始化被推迟到了put方法中，在resize方法中会对threshold重新计算（如下，结合上面resize代码）。

//针对的是上面oldThr>0，对threshold重新计算
if (newThr == 0) {
   float ft = (float)newCap * loadFactor;
   newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                    (int)ft : Integer.MAX_VALUE);
}

`HashMap`常见问题

什么是hash碰撞

hash是指，两个元素通过hash函数计算出的值是一样的，是同一个存储地址。当后面的元素要插入到这个地址时，发现已经被占用了，这时候就产生了hash冲突。

两节点　key 值相同（hash值一定相同），导致冲突
两节点　key 值不同，由于 hash 函数的局限性导致hash 值相同，冲突
两节点　key 值不同，hash 值不同，但 hash 值对数组长度取模后相同，冲突

注意上面第三点，存元素都是hash&(n-1)，所以一个桶内的多个key可能hash值是不同的，所以就可以解释每次遍历链表判断key是否相同时还要再判断key的hash值。

hash冲突的解决方法

开放定址法(查询产生冲突的地址的下一个地址是否被占用，直到寻找到空的地址)，再散列法，链地址法等。HashMap采用的就是链地址法，JDK1.7中，当冲突时，在冲突的地址上生成一个链表，将冲突的元素的key，通过equals进行比较，相同即覆盖，不同则添加到链表上，此时如果链表过长，效率就会大大降低，查找和添加操作的时间复杂度都为O(n)；但是在JDK1.7中如果链表长度大于8，链表就会转化为红黑树，时间复杂度也降为了O(logn)，性能得到了很大的优化。

参考：

https://www.cnblogs.com/xiaolovewei/p/7993440.html https://blog.csdn.net/qq_37113604/article/details/81353626

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2020-03-23，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

jquery

hashmap

jdk

本文分享自 Java后端技术栈微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度