Java HashMap底层实现原理源码分析Jdk8

2019-11-03 00:00:00 原理 源码 底层

在JDK1.6,JDK1.7中,HashMap采用位桶+链表实现,即使用链表处理冲突,同一hash值的链表都存储在一个链表里。但是当位于一个桶中的元素较多,即hash值相等的元素较多时,通过key值依次查找的效率较低。而JDK1.8中,HashMap采用位桶+链表+红黑树实现,当链表长度超过阈值(8)时,可能会将链表转换为红黑树,这样大大减少了查找时间。

简单说下HashMap的实现原理:

首先存在一个table数组,里面每个元素都是一个node链表,当添加一个元素(key-value)时,就首先计算元素key的hash值,通过table的长度和key的hash值进行与运算得到一个index,以此确定插入数组中的位置,但是可能存在同一hash值的元素已经被放在数组同一位置了,这时就把这个元素添加到同一hash值的node链表的链尾,他们在数组的同一位置,但是形成了链表,同一各链表上的Hash值是相同的,所以说数组存放的是链表。而当链表长度大于等于8时,链表就可能转换为红黑树,这样大大提高了查找的效率。

存储结构

《Java HashMap底层实现原理源码分析Jdk8》

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        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;
        }
        *
        *
        *
    }
transient Node<K,V>[] table;
  • HashMap内部包含一个Node类型的数组table,Node由Map.Entry继承而来。
  • Node存储着键值对。它包含四个字段,从next字段我们可以看出node是一个链表。
  • table数组中的每个位置都可以当做一个桶,一个桶存放一个链表。
  • HashMap使用拉链法来解决冲突,同一个存放散列值相同的Node。

数据域

// 序列化ID
private static final long serialVersionUID = 362498820763181265L;  
// 初始化容量,初始化有16个桶
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16  
// 最大容量  1 073 741 824, 10亿多
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认的负载因子。因此初始情况下,当键值对的数量大于 16 * 0.75 = 12 时,就会触发扩容。
static final float DEFAULT_LOAD_FACTOR = 0.75f; 
// 当put()一个元素到某个桶,其链表长度达到8时有可能将链表转换为红黑树  
static final int TREEIFY_THRESHOLD = 8;  
// 在hashMap扩容时,如果发现链表长度小于等于6,则会由红黑树重新退化为链表。
static final int UNTREEIFY_THRESHOLD = 6;  
// 在转变成红黑树树之前,还会有一次判断,只有键值对数量大于 64 才会发生转换,否者直接扩容。这是为了避免在HashMap建立初期,多个键值对恰好被放入了同一个链表中而导致不必要的转化。
static final int MIN_TREEIFY_CAPACITY = 64;  
// 存储元素的数组  
transient Node<k,v>[] table;
// 存放元素的个数
transient int size;
// 被修改的次数fast-fail机制   
transient int modCount; 
// 临界值 当实际大小(容量*填充比)超过临界值时,会进行扩容   
int threshold;
// 填充比
final float loadFactor;

构造函数

public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
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;
        // tableSizeFor(initialCapacity)方法计算出接近initialCapacity
        // 参数的2^n来作为初始化容量。
        this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
}
  • HashMap构造函数允许用户传入容量不是2的n次方,因为它可以自动地将传入的容量转换为2的n次方。

    put()操作源码解析


public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
        int h;
        // “扰动函数”。参考 https://www.cnblogs.com/zhengwang/p/8136164.html
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}    
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, i;
        // 未初始化则初始化table
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 通过table的长度和hash与运算得到一个index,
        // 然后判断table数组下标为index处是否已经存在node。
        if ((p = tab[i = (n - 1) & hash]) == null)
            // 如果table数组下标为index处为空则新创建一个node放在该处
            tab[i] = newNode(hash, key, value, null);
        else {
            // 运行到这代表table数组下标为index处已经存在node,即发生了碰撞
            HashMap.Node<K,V> e; K k;
            // 检查这个node的key是否跟插入的key是否相同。
            if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            // 检查这个node是否已经是一个红黑树
            else if (p instanceof TreeNode)
                // 如果这个node已经是一个红黑树则继续往树种添加节点
                e = ((HashMap.TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    // 在这里循环遍历node链表

                    // 判断是否到达链表尾
                    if ((e = p.next) == null) {
                        // 到达链表尾,直接把新node插入链表,插入链表尾部,在jdk8之前是头插法
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            // 如果node链表的长度大于等于8则可能把这个node转换为红黑树
                            treeifyBin(tab, hash);
                        break;
                    }
                    // 检查这个node的key是否跟插入的key是否相同。
                    if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            // 当插入key存在,则更新value值并返回旧value
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        // 修改次数++
        ++modCount;
        // 如果当前大小大于门限,门限原本是初始容量*0.75
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
  • 下面简单说下put()流程:
    1. 判断键值对数组table[]是否为空或为null,否则以默认大小resize();
    2. 根据键key计算hash值与table的长度进行与运算得到插入的数组索引 index,如果tab[index] == null,直接根据key-value新建node添加,否则转入3
    3. 判断当前数组中处理hash冲突的方式为链表还是红黑树(check第一个节点类型即可),分别处理
  • 为啥头插法为什么要换成尾插:jdk1.7时候用头插法可能是考虑到了一个所谓的热点数据的点(新插入的数据可能会更早用到);找到链表尾部的时间复杂度是 O(n),或者需要使用额外的内存地址来保存链表尾部的位置,头插法可以节省插入耗时。但是在扩容时会改变链表中元素原本的顺序,以至于在并发场景下导致链表成环的问题。
  • 从putVal()源码可以看出,HashMap并没有对null的键值对做限制(hash值设为0),即HashMap允许插入键尾null的键值对。但在JDK1.8之前HashMap使用第0个node存放键为null的键值对。
  • 确定node下标:通过table的长度和key的hash进行与运算得到一个index。
  • 在转变成红黑树树之前,还会有一次判断,只有键值对数量大于 64 才会发生转换,否者直接扩容。这是为了避免在HashMap建立初期,多个键值对恰好被放入了同一个链表中而导致不必要的转化。

get()操作源码解析

public V get(Object key) {
        HashMap.Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
    
    final HashMap.Node<K,V> getNode(int hash, Object key) {
        HashMap.Node<K,V>[] tab; HashMap.Node<K,V> first, e; int n; K k;
        // table不为空
        if ((tab = table) != null && (n = tab.length) > 0 &&
                // 通过table的长度和hash与运算得到一个index,table
                // 下标位index处的元素不为空,即元素为node链表
                (first = tab[(n - 1) & hash]) != null) {
            // 首先判断node链表中中第一个节点
            if (first.hash == hash && // always check first node
                    // 分别判断key为null和key不为null的情况
                    ((k = first.key) == key || (key != null && key.equals(k))))
                // key相等则返回第一个
                return first;
            // 第一个节点key不同且node链表不止包含一个节点
            if ((e = first.next) != null) {
                // 判断node链表是否转为红黑树。
                if (first instanceof HashMap.TreeNode)
                    // 则在红黑树中进行查找。
                    return ((HashMap.TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    // 循环遍历node链表中的节点,判断key是否相等
                    if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        // key在table中不存在则返回null。
        return null;
    }
  • get(key)方法首先获取key的hash值,
    1. 计算hash & (table.len – 1)得到在链表数组中的位置,
    2. 先判断node链表(桶)中的第一个节点的key是否与参数key相等,
    3. 不等则判断是否已经转为红黑树,若转为红黑树则在红黑树中查找,
    4. 如没有转为红黑树就遍历后面的链表找到相同的key值返回对应的Value值即可。

resize()操作源码解析

// 初始化或者扩容之后的元素调整
    final HashMap.Node<K,V>[] resize() {
        // 获取旧table
        HashMap.Node<K,V>[] oldTab = table;
        // 旧table容量
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        // 旧table扩容临界值
        int oldThr = threshold;
        // 定义新table容量和临界值
        int newCap, newThr = 0;
        // 如果原table不为空
        if (oldCap > 0) {
            // 如果table容量达到最大值,则修改临界值为Integer.MAX_VALUE
            // MAXIMUM_CAPACITY = 1 << 30;
            // Integer.MAX_VALUE = 1 << 31 - 1;
            if (oldCap >= MAXIMUM_CAPACITY) {
                // Map达到最大容量,这时还要向map中放数据,则直接设置临界值为整数的最大值
                // 在容量没有达到最大值之前不会再resize。
                threshold = Integer.MAX_VALUE;
                // 结束操作
                return oldTab;
            }
            // 下面就是扩容操作(2倍)
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                    oldCap >= DEFAULT_INITIAL_CAPACITY)
                // 临界值也变为两倍
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            /*
             * 进入此if证明创建HashMap时用的带参构造:public HashMap(int initialCapacity)
             * 或 public HashMap(int initialCapacity, float loadFactor)
             * 注:带参的构造中initialCapacity(初始容量值)不管是输入几都会通过
             * tableSizeFor(initialCapacity)方法计算出接近initialCapacity
             * 参数的2^n来作为初始化容量。
             * 所以实际创建的容量并不等于设置的初始容量。
             */
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            // 进入此if证明创建map时用的无参构造:
            // 然后将参数newCap(新的容量)、newThr(新的扩容阀界值)进行初始化
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            // 进入这代表有两种可能。
            // 1. 说明old table容量大于0但是小于16.
            // 2. 创建HashMap时用的带参构造,根据loadFactor计算临界值。
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                    (int)ft : Integer.MAX_VALUE);
        }
        // 修改临界值
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
        // 根据新的容量生成新的 table
        HashMap.Node<K,V>[] newTab = (HashMap.Node<K,V>[])new HashMap.Node[newCap];
        // 替换成新的table
        table = newTab;
        // 如果oldTab不为null说明是扩容,否则直接返回newTab
        if (oldTab != null) {
            /* 遍历原来的table */
            for (int j = 0; j < oldCap; ++j) {
                HashMap.Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    // 判断这个桶(链表)中就只有一个节点
                    if (e.next == null)
                        // 根据新的容量重新计算在table中的位置index,并把当前元素赋值给他。
                        newTab[e.hash & (newCap - 1)] = e;
                    // 判断这个链表是否已经转为红黑树
                    else if (e instanceof HashMap.TreeNode)
                        // 在split函数中可能由于红黑树的长度小于等于UNTREEIFY_THRESHOLD(6)
                        // 则把红黑树重新转为链表
                        ((HashMap.TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        // 运行到这里证明桶中有多个节点。
                        HashMap.Node<K,V> loHead = null, loTail = null;
                        HashMap.Node<K,V> hiHead = null, hiTail = null;
                        HashMap.Node<K,V> next;
                        do {
                            // 对桶进行遍历
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }
  • 在达到最大值MAXIMUM_CAPACITY之后仍可以put数据。
  • 带构造参数初始化过程中,实际创建的容量并不等于设置的初始容量。tableSizeFor()方法可以自动的将传入的容量转换2的n次方。
  • 红黑树可以退化成链表。
  • 需要注意的是,扩容操作需要把oldTable的所有键值对重新插入newTable中,因此,这一步是很耗时的。
    原文作者:NeverTh
    原文地址: https://www.cnblogs.com/neverth/p/11781491.html
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。

相关文章