Java 多线程6 ConcurrentHashMap

发布于 2024-08-29 10:04:02 字数 8718 浏览 15 评论 0

前言

Map 与 List 是我们日常开发中经常会用到的用于存放数据的容器，与 list 不同的是 map 采用 key/value 的数据结构。而 map 的实现类中最常用的就是 HashMap 了，对应的在多线程场景下一般会推荐使用 ConcurrentHashMap

HashMap

hash

在看 HashMap 之前，我们先了解下什么是 hash:

Hash: 一般翻译做散列，也有直接音译为哈希的，就是把任意长度的输入，通过散列算法，变换成固定长度的输出，该输出就是散列值。
散列函数：若关键字为 k，则其值存放在 f(k) 的位置上。因此，不用比较就可以直接通过 key 找到 value。

碰撞: 再拓展下不管采用什么散列算法，都会出现两个不同的输入值，算出来的散列值是一样的，如果 k1≠k2 ，而 f(k1)=f(k2) ，即对于不同的 key 得到了同一个散列地址，这种现象就叫做碰撞。一般碰撞的概率越小算法越优

对应的在 java 中 Object 对象都会有 hashCode 这个方法(java 中默认所有的类都是继承于 Object)，就是为每个对象都保留生成 hash 的方法

HashMap 原理

先简单了解下 HashMap 的原理:

HashMap 内部是由数组+链表+红黑树构成的(java8 之前采用的是数组+链表)，采用红黑树是为了提高查询效率

是根据 key 而直接访问内存存储位置的数据结构。也就是说，它通过计算一个关于 key 的函数，将所需查询的数据映射到表中的一个位置来访问记录，这加快了查找速度。
这个映射函数称作散列函数，存放记录的数组称作散列表，也叫哈希表。

transient Node<k,v>[] table

transient: 在实现 Serializable 接口的对象中，将不需要序列化的属性前添加关键字 transient，序列化对象的时候，这个属性就被忽略

put

当一个值需要存储到 HashMap 中时，HashMap 会根据 key 值计算出他的 hash，再将 hash 值通过计算转换为索引（数组下标)，将 key 和 value 存放对应位置:

当数组中对应位置没有值时，则直接将当前的 key、value 封装成一个 Node，存放到数组中
当数组中对应位置存在值时（即发生了 hash 碰撞，又叫 hash 冲突了)，就会将当前的 key、value 封装成一个新 Node 写入到当前 Node 的后面（形成链表)，如果链表的值过长（默认 8) 会直接转换为红黑树（即 TreeNode)

最后判断是否需要进行扩容(扩容的判断及扩容实现较复杂, 后面重点分析下)

数组下标的计算方式为：通过对 key hash 然后与数组长度-1 进行与运算((n-1)&hash) (都是 2 的次幂所以等同于取模，但是位运算的效率更高)，找到数组中的下标

链表长度低于 6，会把红黑树转回链表

get

当需要从 HashMap 中获取 value 值时，同样根据 key 计算 hash 和转换得到索引值，取出 value:

当数组对应位置只有一个 node 时，判断是否是同样的 key, 是则直接取出
当数组对应的位置存在多个时，判断是否是红黑树，是则按照红黑树的方式获取值，如果不是，则按照链表的方式遍历获取值

解疑

通过上面的描述，我们也就好理解了：

为什么 HashMap 的 key 不可以是基本数据类型了：因为需要 hash 计算
为什么 HashMap 的遍历会比 List(ArrayList) 慢：因为判断多且结构复杂（可能会遍历数组+链表或者红黑树)

通过 HashMap 的 hash 方法:

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

也可以得出结论，HashMap 是允许 key 为空的

有序的 HashMap

由于 HashMap 是通过 hash 计算来得出存放位置的，故他是不能保证顺序的。如果需要有序的 HashMap，使用 LinkedHashMap：

LinkedHashMap 属于 HashMap 的子类，与 HashMap 的区别在于 LinkedHashMap 保存了记录插入的顺序。TreeMap 实现了 SortedMap 接口，TreeMap 有能力对插入的记录根据 key 排序，默认按照升序排序，也可以自定义比较器，在使用 TreeMap 的时候，key 应当实现 Comparable(String 默认已经实现了 Comparable)

HashMap 线程不安全?

首先 HashMap 先明确下，如果是在只读环境下，那 HashMap 是不存在线程不安全的，所以如果业务中的使用时先初始化好 map，然后在不同线程内获取值的话，HashMap 也是可以直接使用的。

那 HashMap 什么情况下会造成线程不安全呢？答案就是在每次 put 值之后会判断是否扩容，而如果并发情况下，扩容时可能会导致节点丢失(java8 之前还可能造成环形链表导致死循环) 等问题，所以才说 HashMap 是线程不安全的

在 jdk1.7 中，由于扩容时使用头插法，在并发时可能会形成环状列表，导致死循环，在 jdk1.8 中改为尾插法，可以避免这种问题，但是依然避免不了节点丢失的问题

ConcurrentHashMap

与 HashMap 类似，ConcurrentHashMap 也采用了数组+链表+红黑树的方式，并使用 volatile 关键字来保证获取时可见性，采用了 CAS + synchronized 来保证并发安全性(java8 之前采用的是 Segment 分段锁)

transient volatile Node<K,V>[] table;

ConcurrentHashMap 并不是直接继承自 HashMap，而是继承了和 HashMap 一样的父类 AbstractMap。并且ConcurrentHashMap 中的 key 和 value 都不可以为空!

put

put 方法与 HashMap 有一些区别:

根据 key 计算出 hashcode(这里 ConcurrentHashMap 的 hash 是使用了 spread,与 HashMap 稍有不同)，定位出 Node：

如果为空表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功
如果当前位置的 hashcode == MOVED == -1,则需要进行扩容
如果都不满足，则利用 synchronized 锁写入数据。
如果链表数量大于 8 则要转换为红黑树

ConcurrentHashMap VS HashTable

既然 HashMap 是线程不安全的，那在多线程场景下我们就可以选择 HashTable 或者 ConcurrentHashMap 了，在一般情况下推荐使用 ConcurrentHashMap：HashTable 在线程竞争比较激烈的情况下效率相对较低，因为他采用的是 synchronized 全局锁的方式，在一个线程操作时，其他线程都需要等待，不仅不能 put 也不能 get。而 ConcurrentHashMap 使用了分段锁的技术来提高并发度，不在同一段的数据互相不影响，多个线程对多个不同段的操作是不会相互影响的。

值得一提的是 java8 对 synchronized 做了很多优化，java8 中 ConcurrentHashMap 采用的分段锁从 ReentrantLock 改为了 synchronized

当然 HashTable 也不是完全没有用了，相反由于采用了全局锁，使得每个线程获得的数据总是最实时的：比如说线程 A 调用 putAll 写入大量数据，期间线程 B 调用 get，线程 B 就会被阻塞，直到线程 A 完成 putAll，因此线程 B 肯定能获取到线程 A 写入的完整数据。相对应的 ConcurrentHashMap 是设计为非阻塞的。在更新时会局部锁住某部分数据，但不会把整个表都锁住。同步读取操作则是完全非阻塞的。好处是在保证合理的同步前提下，效率很高。坏处是严格来说读取操作不能保证反映最近的更新。例如线程 A 调用 putAll 写入大量数据，期间线程 B 调用 get，则只能 get 到目前为止已经顺利插入的部分数据。

应该根据自己的业务场景选择合适的 HashMap

使用 HashMap 需注意的事项

默认情况下 HashMap 的初始容量为 16，默认情况下，当其 size 大于 12(16*0.75) 时就会触发扩容当达到扩容条件时会进行扩容，从 16 扩容到 32、64、128…

如果用户通过构造函数指定了一个数字作为容量，那么 Hash 会选择大于该数字的第一个 2 的幂作为容量。(3->4、7->8、9->16)

建议初始化 HashMap 的容量大小

如果我们没有设置初始容量大小，随着元素的不断增加，HashMap 会发生多次扩容，而 HashMap 中的扩容机制决定了每次扩容都需要重建 hash 表，是非常影响性能的

项目使用时，如果引用了 guava 库直接使用 Maps.newHashMapWithExpectedSize(x) 即可，否则可以采用下面的算法来初始化:

static int capacity(int expectedSize) {
        if (expectedSize < 3) {
            return expectedSize + 1;
        } else {
            return expectedSize < 1073741824 ? (int)((float)expectedSize / 0.75F + 1.0F) : 2147483647;
        }
    }

//或者
return (int) ((float) expectedSize / 0.75F + 1.0F);

//expectedSize 就是可能会存储的元素的个数
new HashMap(capacity(expectedSize));

偶然间翻到 HashSet 的源码，HashSet 内部通过维护一个 HashMap 来实现读取插入等功能，他对 hashMap 的初始化容量是这么写的：

public HashSet(Collection<? extends E> c) {
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
}

而面试题经常问到的 HashSet 的值为什么不能重复, 看看 add 方法实现就知道了:

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

遍历方式选择

HashMap 中可以看到:

transient Set<Map.Entry<K,V>> entrySet;

public Set<Map.Entry<K,V>> entrySet() {
    Set<Map.Entry<K,V>> es;
    return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}

故如果有人再问哪张方式遍历效率更高，直接回答 entrySet 的方式：

Map<String, String> map = new HashMap<>(3);
map.put("a", "123");
map.put("b", "456");
map.put("c", "789");
for(Map.Entry<Integer, Integer> entry : map.entrySet()){
	System.out.println("key = " + entry.getKey() + ", value = " + entry);
}

当然如果项目是 java8 的直接采用 Map.forEach

Map<String, String> map1 = new HashMap<>(3);
map1.put("a", "123");
map1.put("b", "456");
map1.put("c", "789");

//java8
map1.forEach((key, value) -> System.out.println("key=" + key + " value=" + value));

只有当只需要获取 map 的 keys 或 values 时，采用 KeySet 或者 values 代替 entrySet

JUC 中的 concurrentMap

ConcurrentMap

它是一个接口，是一个能够支持并发访问的 java.util.map 集合。在原有 java.util.map 接口基础上又新提供了 4 种方法，进一步扩展了原有 Map 的功能：

public interface ConcurrentMap<K, V> extends Map<K, V> {
 
    //插入元素
    //如果插入的 key 相同，则不替换原有的 value 值
    V putIfAbsent(K key, V value);
 
    //移除元素
    //增加了对 value 的判断，如果要删除的 key--value 不能与 Map 中原有的 key--value 对应上，则不会删除该元素
    boolean remove(Object key, Object value);
 
    //替换元素
    //增加了对 value 值的判断，如果 key--oldValue 能与 Map 中原有的 key--value 对应上，才进行替换操作
    boolean replace(K key, V oldValue, V newValue);
 
    //替换元素
    //如果 key 存在则直接替换,不对 value 值的判断
    V replace(K key, V value);
}

ConcurrentNavigableMap

它继承了 NavigableMap 和 ConcurrentMap 这两个接口子 Map，就是两者功能的结合，既保证线程安全性，又提供导航搜索子 Map 视图的功能（视图就是集合中的一段数据序列)

ConcurrentSkipListMap

ConcurrentSkipListMap 是 ConcurrentNavigableMap 的一个实现类。

ConcurrentSkipListMap 的 key 是有序的, 所以在多线程程序中，如果需要对 Map 的键值进行排序时，请尽量使用 ConcurrentSkipListMap，可能得到更好的并发度

其他

WeakHashMap

在 Java 集合中有一种特殊的 Map 类型—WeakHashMap，在这种 Map 中存放了键对象的弱引用，当一个键对象被垃圾回收器回收时，那么相应的值对象的引用会从 Map 中删除。WeakHashMap 能够节约存储空间，可用来缓存那些非必须存在的数据

@Test
    public void test(){
        Map map;
        map = new WeakHashMap<String,Object>();
        for (int i =0;i<10000;i++){
            map.put("key"+i,new byte[i]);
        }
//        map = new HashMap<String,Object>();
//        for (int i =0;i<10000;i++){
//            map.put("key"+i,new byte[i]);
//        }
    }

使用-Xmx2M 限定堆内存，使用 WeakHashMap 的代码正常运行结束，而使用 HashMap 的代码段抛出异常：java.lang.OutOfMemoryError: Java heap space。由此可见，WeakHashMap 会在系统内存紧张时使用弱引用，自动释放掉持有弱引用的内存数据。但如果 WeakHashMap 的 key 都在系统内持有强引用，那么 WeakHashMap 就退化为普通的 HashMap，因为所有的数据项都无法被自动清理。

分享到QQ

分享到微博