HashMap1.7和1.8对比与源码解析

HashMap 集合
笔记
发布日期:   2021-11-05
更新日期:   2021-11-05
文章字数:   3.2k
阅读时长:   13 分
阅读次数:  

常用API

put过程：它会hash传入的key值，将hash的值&上map长度减一（这里用的是&而不是取模运算，应该是考虑到性能问题，这里是length-1是应为这样可以取到0到map.length-1的值）插入到对应的数组下标上面去。这时产生了一个问题就是2个key值hash到一个位置怎么办？这就是Hash碰撞，产生了Hash碰撞在当前数组位置产生一个链表，如果链表过长查询效率可能会减低，在jdk1.8上面达到了一定的程度会链表转红黑树增强查询效率。

get过程：hash传入的key值，将hash的值&上map长度减一在数组里面去找找到对应的数组位置如果不是传入的key值就顺着链表或红黑树继续往里面找，所以他的时间复杂度是O(1)。

扩容：当数据达到map总长度的加载因子倍数就会开始扩容

基本参数介绍

// 数组默认大小，默认为16，必须设值为2的n次幂，如果设值不是2的n次幂它会往大于你的值的最近的2次幂
// 比如你设map长度为9它会修改map长度为2的4次，也就是16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final int MAXIMUM_CAPACITY = 1 << 30;
// 加载因子，数组长度大于容量的0.75就会扩容，为什么是9.75？基于空间与时间的考虑，如果太满了可能会有很多的hash碰撞，hash碰撞越多，链表就会越长，查询效率就会太低，加载因子如果太小了就会导致扩容频繁，通过牛顿二项式推导得出，0.693是最为合适的值，java选择了0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;

jdk1.7和jdk1.8对比

jdk1.7

数据结构：数组+链表

扩容：1.7的扩容会先把当前数组长度乘2生成一个新数组，然后对原来的Map里面的值进行reHash.重新落入到新数组中。

链表插入方式：尾插法

jdk1.8

数据结构：数组+链表+红黑树

扩容：1.8的扩容有个高低位的概念，它将原来的key Hash过后&map长度,这时候会生成2种值要么是0，要么是数组长度，这时候是0的我们算作低位，数组长度的算作高位，这时候我们有2个链表一个低位链表一个高位链表，低位链表还是在原来的位置，高位链表移到原来位置加上数组长度的位置。

链表插入方式：尾插法

链表转红黑树判定：链表长度大于8,也就是第9个元素，还有一个条件是容量大于64

​ 为什么要把阈值设为8呢？

​ 下面是HashMap源码里面的注释。大致意思就是数组中链表长度达到相应的数字概率是多少（这里是通过泊松分布计算得出），前提是随机hash码和加载因子是0.75.可以看出来到8的时候概率是很低了。从这一方面可以看出HashMap正常情况下转红黑树的几率是极其小的。也可以侧面的反映出HashMap在1.7到1.8性能上的提升其实并不大，数据量极大的情况下是有提升的。

* Because TreeNodes are about twice the size of regular nodes, we
* use them only when bins contain enough nodes to warrant use
* (see TREEIFY_THRESHOLD). And when they become too small (due to
* removal or resizing) they are converted back to plain bins.  In
* usages with well-distributed user hashCodes, tree bins are
* rarely used.  Ideally, under random hashCodes, the frequency of
* nodes in bins follows a Poisson distribution
* (http://en.wikipedia.org/wiki/Poisson_distribution) with a
* parameter of about 0.5 on average for the default resizing
* threshold of 0.75, although with a large variance because of
* resizing granularity. Ignoring variance, the expected
* occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
* factorial(k)). The first values are:
*
* 0:    0.60653066
* 1:    0.30326533
* 2:    0.07581633
* 3:    0.01263606
* 4:    0.00157952
* 5:    0.00015795
* 6:    0.00001316
* 7:    0.00000094
* 8:    0.00000006

// 链表转红黑树阈值
static final int TREEIFY_THRESHOLD = 8;
// 红黑树转链表阈值
static final int UNTREEIFY_THRESHOLD = 6;
// 链表转红黑树，map最小容量
static final int MIN_TREEIFY_CAPACITY = 64;

HashMap jdk1.7源码解析

public V put(K key, V value) {
    // 第一次开始put值的时候，hash表是空的
    // threshold是传进来的长度
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    // 这里证明了HashMap的key可以为空
    if (key == null)
        // 空就往第一个数组位置里面插
        return putForNullKey(value);
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        // 这里判断传进来的key是不是已经写过了，写过了就把value修改掉
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    // 下文有介绍modeCount存在的意义。这里不影响put主体流程，所以暂时可以不关心
    modCount++;
    // put进去
    addEntry(hash, key, value, i);
    return null;
}

private void inflateTable(int toSize) {
    // Find a power of 2 >= toSize
    // 这里就是空间修正代码，找到当前传的值，大于值且是2的指数次幂
    int capacity = roundUpToPowerOf2(toSize);
    // 这里是扩容指标
    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    table = new Entry[capacity];
    initHashSeedAsNeeded(capacity);
}

void addEntry(int hash, K key, V value, int bucketIndex) {
    // 这里判断是判断是否需要扩容
    // 判断条件是map长度大于扩容阈值，而且当前数组下标必须放了值
    if ((size >= threshold) && (null != table[bucketIndex])) {
        // 扩容大小 -> map长度的2倍 
        resize(2 * table.length);
        // 这里就是keu为null的时候会往数组第一个位置放
        hash = (null != key) ? hash(key) : 0;
        // indexFor就是&数组长度-1
        bucketIndex = indexFor(hash, table.length);
    }
    // 元素放进去了
    createEntry(hash, key, value, bucketIndex);
}

// ========================================扩容方法===============================
void resize(int newCapacity) {
    // 容错不管它
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    // new 一个新的hash表
    Entry[] newTable = new Entry[newCapacity];
    // 核心方法
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    // 把新的table,扩容阈值重新写入
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

void transfer(Entry[] newTable, boolean rehash) {
    // 新的数组容量
    int newCapacity = newTable.length;
    // 遍历原来的table表
    // 这里使用双重循环是因为我们的hashmap数据结构是数组加链表，第一重遍历数组第二重遍历链表找到元素开始reHash
    for (Entry<K,V> e : table) {
        while(null != e) {
            // next为当前链表的下一个元素，为了后面的循环
            // 1
            Entry<K,V> next = e.next;
            if (rehash) {
                // rehash当前节点
                e.hash = null == e.key ? 0 : hash(e.key);
            }
               // 用扩容后的hashmap长度计算出当前节点应该落到哪个节点上面去。
            int i = indexFor(e.hash, newCapacity);
            // 当前节点与别的节点指针断开指向新的节点位置
            // 2
            e.next = newTable[i];
            // 把值赋给新的节点位置，从这可以看出它是使用的是头插法
            // 3
            newTable[i] = e;
            // 为了新一轮的遍历
            e = next;
        }
    }
}

HashMap并发场景下的死锁问题

（吐槽：在并发场景使用HashMap，想什么呢，HashMap本身是线程不安全的还敢在并发下用？）。

我们想一下现在有2个线程thread1,thread2,这2个线程都在进行扩容，都走到了transfer方法的2重循环内，这完全是可能的吧，因为它全程没有锁，因为它是线程不安全的。现在thread1走到了transfer代码段1（上面源码解析标注）的位置，已经把next节点定下来了时间片轮转到thread2了。thread2执行到代码段3，这时候thread1在继续往下走，最后会发现2个节点会出现循环链表。说不清，画个图来说吧。

​ 原hashMap

HashMap多线程丢数据情况分析

代码定位到addEntry()->createEntry()方法中

void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

如果有多个线程同时拿的e,e应该是当前table[i]链表的第一个元素，然后你这时候拿到多个元素就会出现元素覆盖的请况，thread1头插法排到了第一个元素，而thread2拿到的e是第二个元素，用头插法，一插好家伙，吧我thread1插入的数据给顶掉了，最后thread1写的数据就丢失了，在jdk1.8这种情况也在发生，因为他是线程不安全的。注意，多线程不要用HashMap，请用ConcurrentHashMap

HashMap jdk1.8源码解析

hashMap jdk1.8跟1.7大体逻辑是差不多的，我们就看下改动比较大的几个点

树化

上面说了jdk1.8的HashMap有了红黑树的数据结构，那么他怎么才会变为红黑树呢？TREEIFY_THRESHOLD = 8

下面这段是put中的关键代码从这段代码可以看出，binCount>=7,所以循环肯定是8次也就是这个时候链表长度是8了。但在这个时候它先执行的是p.next = newNode(hash, key, value, null);然后在判断链表长度，所以链表长度是9的时候它才会满足树化的第一个条件走treeifyBin；不信可以测试一下

for (int binCount = 0; ; ++binCount) {
    if ((e = p.next) == null) {
        p.next = newNode(hash, key, value, null);
        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
            treeifyBin(tab, hash);
        break;
    }
    if (e.hash == hash &&
        ((k = e.key) == key || (key != null && key.equals(k))))
        break;
    p = e;
}

​ 树化还有一个条件就是hashmap容量大于64，这个条件就在上面的treeifyBin方法内，第一个判断就是如果容量没有达到MIN_TREEIFY_CAPACITY=64就先走扩容策略，不走树化，反之直接树化（在else逻辑内）

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

扩容策略

上面说到了它的扩容策略和jdk1.7是有了极大的区别，现在我们来看一下源码是怎么实现的。源码太长就不细看了，主要逻辑就是它里面分了2组链表

Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;

这2组就是高位链表和低位链表，怎么往这2个链表里面放呢？if ((e.hash & oldCap) == 0) 满足这个条件就是低位链表，简单来说就是&上老的容量算出来只有可能为0或hashmap的长度，为0算低位，不为0算高位。newTab[j] = loHead; newTab[j + oldCap] = hiHead;这2段代码就表明了它们应该落得位置。

（1.8的HashMap源码太复杂了，全是位运算和判断逻辑看的心累，对于1.8的源码就不详细写了。）

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        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
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    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;
}

modCount字段是干嘛的

在很多集合类都有modCount的身影，那么它到底是干嘛的呢？我们发现它存在的地方都是对集合进行了修改操作比如增加元素，删除元素。而且看过ConcurrentHashMap源码发现没有这个参数了，那么很明显它可能跟线程安全有关。还记得我们在hashMap遍历的时候如果对其进行元素的操作会发生ConcurrentModificationException异常。其实他就跟modCount有关，在迭代过程中，它会判断 modCount 跟 expectedModCount 是否相等，不等说明有其他线程在修改元素，就抛出了异常。这是Fail-Fast 机制

文章作者: dm
文章链接: https://dmsupine.com/2021/11/05/hashmap/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 dm !
HashMap 集合
赏
评论
 上一篇
ConcurrentHashMap1.7和1.8对比与线程安全源码解析 ConcurrentHashMap1.7和1.8对比与线程安全源码解析
ConcurrentHashMap与HashMap在Api,参数,数据结构上面基本都是类似的，实现原理也基本都是一致的在这里就不做过多的说明了，若不清楚可以看下另一篇HashMap的对比博文HashMap1.7和1.8对比与源码解析:Con
2021-11-16 笔记
并发 集合 ConcurrentHashMap
下一篇 
Unsafe魔法类解析及应用 Unsafe魔法类解析及应用
Unsafe类提供了一些极度不安全的方法，这些方法会直接访问系统内存和对系统内存进行操作。，由于它是直接对内存进行的操作，所以从他的命名也可以看出它是不安全的。Unsafe类的使用必须慎重；juc包中大量运用了Unsafe类，对Unsafe
2021-10-05 笔记
并发 Atomic Unsafe
  目录