暗中观察

hashMap 和 concurrentHashMap (转)
原作者: 点我直达一、hashMap 原理及实现1.1 简介 众所周知 HashMap 底层是基于 数组 + 链表...
扫描右侧二维码阅读全文
10
2018/09

hashMap 和 concurrentHashMap (转)

  1.  Home
  2. Text  
    3. Share to：

原作者: 点我直达

一、hashMap 原理及实现

1.1 简介
众所周知 HashMap 底层是基于 数组 + 链表 组成的，不过在 jdk1.7 和 1.8 中具体实现稍有不同。

1.2 jdk1.7中
hashmap-struc-0.jpg
hashmap-struc-1.jpg

1.初始化桶大小，因为底层是数组，所以这是数组默认的大小。
2.桶最大值。
3.默认的负载因子（0.75）
4.table 真正存放数据的数组。
5.Map 存放数量的大小。
6.桶大小，可在初始化时显式指定。
7.负载因子，可在初始化时显式指定。

重点解释下负载因子：

由于给定的 HashMap 的容量大小是固定的，比如默认初始化：

public HashMap() {
    this(DEFAULT_INITIAL_CAPACITY, 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;
    threshold = initialCapacity;
    init();
}

给定的默认容量为 16，负载因子为 0.75。Map 在使用过程中不断的往里面存放数据，当数量达到了 16 * 0.75 = 12 就需要将当前 16 的容量进行扩容，而扩容这个过程涉及到 rehash、复制数据等操作，所以非常消耗性能。

因此通常建议能提前预估 HashMap 的大小最好，尽量的减少扩容带来的性能损耗。

根据代码可以看到其实真正存放数据的是

transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

这个数组，那么它又是如何定义的呢？
hashmap-struc-entry.jpg

Entry 是 HashMap 中的一个内部类，从他的成员变量很容易看出：

  1. key 就是写入时的键。
  2. value 自然就是值。
  3. 开始的时候就提到 HashMap 是由数组和链表组成，所以这个 next
    就是用于实现链表结构。
  4. hash 存放的是当前 key 的 hashcode。

知晓了基本结构，那来看看其中重要的写入、获取函数：
put 方法

hashmap-put.png
hashmap-put1.png

get 方法
再来看看 get 函数：
hashmap-get.png

1.3 jdk1.8中
当 Hash 冲突严重时，在桶上形成的链表会变的越来越长，这样在查询时的效率就会越来越低；时间复杂度为 O(N)
因此 1.8 中重点优化了这个查询效率
hashmap-1.8-struc.jpg
先来看看几个核心的成员变量：
hashmap-1.8-struc1.jpg

再来看看核心方法。
hashmap-1.8-put.jpg
hashmap-1.8-get.jpg

但是 HashMap 原有的问题也都存在，比如在并发场景下使用时容易出现死循环。

final HashMap<String, String> map = new HashMap<String, String>();
for (int i = 0; i < 1000; i++) {
    new Thread(new Runnable() {
        @Override
        public void run() {
            map.put(UUID.randomUUID().toString(), "");
        }
    }).start();
}

看过上文的还记得在 HashMap 扩容的时候会调用 resize() 方法，就是这里的并发操作容易在一个桶上形成环形链表；这样当获取一个不存在的 key 时，计算出的 index 正好是环形链表的下标就会出现死循环。
如下图:
hashmap-1.8-resize-for0.jpg
hashmap-1.8-resize-for1.jpg

遍历方式
还有一个值得注意的是 HashMap 的遍历方式，通常有以下几种：
hashmap-1.8-for.jpg

二、concurrentHashMap 原理及实现

2.1 Base 1.7
是由 Segment 数组、HashEntry 组成，和 HashMap 一样，仍然是数组加链表。
ConcurrentHashMap-struc.jpg

它的核心成员变量：

/**
 * Segment 数组，存放数据时首先需要定位到具体的 Segment 中。
 */
final Segment<K,V>[] segments;
transient Set<K> keySet;
transient Set<Map.Entry<K,V>> entrySet;

Segment 是 ConcurrentHashMap 的一个内部类，主要的组成如下：

static final class Segment<K,V> extends ReentrantLock implements Serializable {
    private static final long serialVersionUID = 2249069246763182397L;
    
    // 和 HashMap 中的 HashEntry 作用一样，真正存放数据的桶
    transient volatile HashEntry<K,V>[] table;
    transient int count;
    transient int modCount;
    transient int threshold;
    final float loadFactor;
    
}

看看其中 HashEntry 的组成：
ConcurrentHashMap-struc-hashentry.jpg

和 HashMap 非常类似，唯一的区别就是其中的核心数据如 value ，以及链表都是 volatile 修饰的，保证了获取时的可见性。

原理上来说：ConcurrentHashMap 采用了分段锁技术，其中 Segment 继承于 ReentrantLock。不会像 HashTable 那样不管是 put 还是 get 操作都需要做同步处理，理论上 ConcurrentHashMap 支持 CurrencyLevel (Segment 数组数量)的线程并发。每当一个线程占用锁访问一个 Segment 时，不会影响到其他的 Segment。

下面也来看看核心的 put get 方法。

public V put(K key, V value) {
    Segment<K,V> s;
    if (value == null)
        throw new NullPointerException();
    int hash = hash(key);
    int j = (hash >>> segmentShift) & segmentMask;
    if ((s = (Segment<K,V>)UNSAFE.getObject          // nonvolatile; recheck
         (segments, (j << SSHIFT) + SBASE)) == null) //  in ensureSegment
        s = ensureSegment(j);
    return s.put(key, hash, value, false);
}

首先是通过 key 定位到 Segment，之后在对应的 Segment 中进行具体的 put。

final V put(K key, int hash, V value, boolean onlyIfAbsent) {
    HashEntry<K,V> node = tryLock() ? null :
        scanAndLockForPut(key, hash, value);
    V oldValue;
    try {
        HashEntry<K,V>[] tab = table;
        int index = (tab.length - 1) & hash;
        HashEntry<K,V> first = entryAt(tab, index);
        for (HashEntry<K,V> e = first;;) {
            if (e != null) {
                K k;
                if ((k = e.key) == key ||
                    (e.hash == hash && key.equals(k))) {
                    oldValue = e.value;
                    if (!onlyIfAbsent) {
                        e.value = value;
                        ++modCount;
                    }
                    break;
                }
                e = e.next;
            }
            else {
                if (node != null)
                    node.setNext(first);
                else
                    node = new HashEntry<K,V>(hash, key, value, first);
                int c = count + 1;
                if (c > threshold && tab.length < MAXIMUM_CAPACITY)
                    rehash(node);
                else
                    setEntryAt(tab, index, node);
                ++modCount;
                count = c;
                oldValue = null;
                break;
            }
        }
    } finally {
        unlock();
    }
    return oldValue;
}

虽然 HashEntry 中的 value 是用 volatile 关键词修饰的，但是并不能保证并发的原子性，所以 put 操作时仍然需要加锁处理。

首先第一步的时候会尝试获取锁，如果获取失败肯定就有其他线程存在竞争，则利用 scanAndLockForPut() 自旋获取锁。
ConcurrentHashMap-put-0.jpg

  1. 尝试自旋获取锁。
  2. 如果重试的次数达到了 MAX_SCAN_RETRIES 则改为阻塞锁获取，保证能获取成功。
    ConcurrentHashMap-put-1.jpg

再结合图看看 put 的流程。

  1. 将当前 Segment 中的 table 通过 key 的 hashcode 定位到 HashEntry。
  2. 遍历该HashEntry，如果不为空则判断传入的 key 和当前遍历的 key 是否相等，相等则覆盖旧的 value。
  3. 不为空则需要新建一个HashEntry 并加入到 Segment 中，同时会先判断是否需要扩容。
  4. 最后会解除在 1 中所获取当前 Segment 的锁。

get 方法:

public V get(Object key) {
    Segment<K,V> s; // manually integrate access methods to reduce overhead
    HashEntry<K,V>[] tab;
    int h = hash(key);
    long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
    if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
        (tab = s.table) != null) {
        for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
                 (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
             e != null; e = e.next) {
            K k;
            if ((k = e.key) == key || (e.hash == h && key.equals(k)))
                return e.value;
        }
    }
    return null;
}

get 逻辑比较简单：

只需要将 Key 通过 Hash 之后定位到具体的 Segment ，再通过一次 Hash 定位到具体的元素上。

由于 HashEntry 中的 value 属性是用 volatile 关键词修饰的，保证了内存可见性，所以每次获取时都是最新值。

ConcurrentHashMap 的 get 方法是非常高效的，因为整个过程都不需要加锁。

2.2 Base 1.8
1.7 已经解决了并发问题，并且能支持 N 个 Segment 这么多次数的并发，但依然存在 HashMap 在 1.7 版本中的问题。
那就是查询遍历链表效率太低。
首先来看下底层的组成结构
ConcurrentHashMap-1.8-struc.jpg
其中抛弃了原有的 Segment 分段锁，而采用了 CAS + synchronized 来保证并发安全性。
也将 1.7 中存放数据的 HashEntry 改为 Node，但作用都是相同的。
其中的 val next 都用了 volatile 修饰，保证了可见性。
ConcurrentHashMap-1.8-struc-entry.jpg

put 方法:
ConcurrentHashMap-1.8-put.jpg

  1. 根据 key 计算出 hashcode 。
  2. 判断是否需要进行初始化。
  3. f 即为当前 key 定位出的 Node，如果为空表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功。
  4. 如果当前位置的 hashcode == MOVED == -1,则需要进行扩容。
  5. 如果都不满足，则利用 synchronized 锁写入数据。
  6. 如果数量大于 TREEIFY_THRESHOLD 则要转换为红黑树

get 方法:
ConcurrentHashMap-1.8-get.jpg

  1. 根据计算出来的 hashcode 寻址，如果就在桶上那么直接返回值。
  2. 如果是红黑树那就按照树的方式获取值。
  3. 就不满足那就按照链表的方式遍历获取值。

1.8 在 1.7 的数据结构上做了大的改动，采用红黑树之后可以保证查询效率（O(logn)），甚至取消了 ReentrantLock 改为了 synchronized，这样可以看出在新版的 JDK 中对 synchronized 优化是很到位的

看完了整个 HashMap 和 ConcurrentHashMap 在 1.7 和 1.8 中不同的实现方式相信大家对他们的理解应该会更加到位。
其实这块也是面试的重点内容，通常的套路是：

  1. 谈谈你理解的 HashMap，讲讲其中的 get put 过程。
  2. 1.8 做了什么优化？
  3. 是线程安全的嘛？
  4. 不安全会导致哪些问题？
  5. 如何解决？有没有线程安全的并发容器？
  6. ConcurrentHashMap 是如何实现的？ 1.7、1.8 实现有何不同？为什么这么做？

三、常见问题

3.1 解决hash碰撞还有哪些方法
我们知道，对象Hash的前提是实现equals()和hashCode()两个方法，那么HashCode()的作用就是保证对象返回唯一hash值，但当两个对象计算值一样时，这就发生了碰撞冲突。如下将介绍如何处理冲突，当然其前提是一致性hash。

  1. 线性探测(开放地址法)
  2. 二次探测(再哈希法)
  3. 拉链法
  4. 双重散列
  5. 多重散列

3.2 HashMap的长度为什么要是2的n次方
为了存取高效，要尽量较少碰撞，就是要尽量把数据分配均匀，每个链表长度大致相同，这个实现就在把数据存到哪个链表中的算法；
这个算法实际就是取模，hash%length，计算机中直接求余效率不如位移运算，源码中做了优化hash&(length-1)，
hash%length==hash&(length-1)的前提是length是2的n次方；
hashmap-hash-pz.jpg

版权属于：sunjianhua

本文链接：https://www.sunjianhua.cn/archives/java-map.html

转载时须注明出处及本声明，如果不小心侵犯了您的权益，请联系邮箱：NTA2MTkzNjQ1QHFxLmNvbQ==

Last modification：September 11th, 2018 at 08:03 pm
© The copyright belongs to the author
If you think my article is useful to you, please feel free to appreciate

Leave a Comment