Fork me on GitHub

线程安全的使用HashMap

发表于 | | 阅读次数:

    HashMap是线程不安全的，HashMap是一个接口，是Map的一个子接口，是将键映射到值的对象，不允许键重复，允许空键和空值。由于非线程安全，HashMap的效率要较HashTable的效率高一些。

    在Java8之前，HashMap和其他基于map的类都是通过链地址法解决冲突，它们使用单向链表来存储相同索引值的元素。在最坏的情况下，这种方式会将HashMap的get方法的性能从O(1)降低到O(n)。为了解决在频繁冲突时hashmap性能降低的问题，Java8中使用平衡术来替代链表存储冲突的元素。这意味着我们可以将最坏情况下的性能从O(n)提高到O(logn)。
    在Java8中使用常量TREEIFY_THRESHOLD来控制是否切换到平衡树来存储。目前，这个常量值是8，这意味着当有超过8个元素的索引一样时，HashMap会使用树来存储它们。
    这一改变是为了继续优化常用类。在Java7中为了优化常用类对ArrayList和HashMap采用了延迟加载的机制，在有元素加入之前不会分配内存，这会减少空的链表和HashMap占用的内存。
    这一动态的特性使得HashMap一开始使用链表，并在冲突的元素数量超过制定值时用平衡二叉树替换链表。不过这一特性在所有基于hashtable的类中并没有，例如Hashtable和WeakHashMap。
    目前，只有ConcurrentHashMap，LinkedHashMap和HashMap会在频繁冲突的情况下使用平衡树。

什么时候会产生冲突

    HashMap中调用hashcode()方法来计算hashcode。
    由于在Java中两个不同的对象可能有一样的hashcode，也就是说不同的键可能有一样的hashcode，此时会产生冲突。

  • 相同对象的hashCode一定是相同的，但相同的hashCode不一定是相同的对象。
  • 在HashTable和HashMap中，冲突的产生是由于不同对象的hashCode()方法返回了一样的值。
  • 从Java1中就存在的hashtable类为了保证迭代顺序不变，即便在频繁冲突的情况下也不会使用平衡树。这一决定是为了不破坏某些较老的需要依赖于Hashtable迭代顺序的Java应用。

为什么HashMap是线程不安全的

HashMap的内部存储结构为：

1
2
3
4
5
6
7
8
transient Node<K, V>[] table;
static class Node<K, V> implements Map.Entry<K, V> {
    final int hash;
    final K key;
    V value;
    Node<K, V> next;
}

    可以看到HashMap内部存储使用了一个Node数组(默认大小是16)，而Node类包含一个类型为Node的next的变量，也就是相当于一个链表，所有hash值相同(即产生了冲突)的key会存储到同一个链表里。
    需要注意的是，在Java8中如果hash值相同的key数量大于指定值(默认是8)时使用平衡树来代替链表，这会将get()方法的性能从O(n)提高到O(logn)。

HashMap的自动扩容机制

    HashMap内部的Node数组默认的大小是16，假设有100万个元素，那么最好的情况下每个hash桶里都有62500个元素，这时get(), put(), remove()等方法效率都会降低。为了解决这个问题，HashMap提供了自动扩容机制，当元素个数达到数组大小loadFactor后会扩大数组的大小，在默认情况下，数组大小为16，loadFactor为0.75，也就是说当HashMap中的元素超过16/ 0.75= 12时，会把数组大小扩展为2* 16= 32，并且重新计算每个元素在新数组中的位置。

HashMap的工作原理

    HashMap是基于hashing的原理，我们使用put(key, value)存储对象到HashMap中，使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时，我们先对键调用hashCode()方法，返回的hashCode用于找到bucket位置来存储Entry对象。

两个对象的hashcode相同会发生什么

    因为hashcode相同，所以它们的bucket位置相同，”碰撞”会发生。因为HashMap使用LinkedList存储对象，这个Entry(包含有键值对的Map.Entry对象)会存储在LinkedList中。
    既然两个键的hashcode相同，如何获取值对象呢？当我们调用get()方法时，HashMap会使用键对象的hashcode找到bucket位置，然后获取值对象。如果两个值对象存储在同一个bucket，会调用keys.equals()方法去找到LinkedList中正确的节点，最终找到要找的值对象。

为什么线程不安全

    个人觉得HashMap在并发时可能出现的问题主要是两方面，首先如果多个线程同时使用put方法添加元素，而且假设正好存在两个put的key发生了碰撞(hash值一样)，那么根据HashMap的实现，这两个key会添加到数组的同一个位置，这样最终就会发生其中一个线程的put数据被覆盖。第二就是如果多个线程同时检测到元素个数超过数组大小*loadFactor，这样就会发生多个线程同时对Node数组进行扩容，都在重新计算元素位置以及复制数据，但是最终只有一个线程扩容后的数组会赋给table，也就是说其他线程的都会丢失，并且各自线程put的数据也丢失。

HashMap在并发执行put操作时会引起死循环，导致CPU利用率接近100%。因为多线程会导致HashMap的Node链表形成环形数据结构，一旦形成环形数据结构，Node的next节点永远不为空，就会在获取Node时产生死循环。

如何线程安全的使用HashMap

  • Hashtable
  • ConcurrentHashMap
  • Synchronized Map

    主要说一下ConcurrentHashMap。

锁分段技术

    HashTable容器在竞争激烈的并发环境下表现出效率低下的原因，是因为所有访问HashTable的线程都必须竞争同一把锁，那假如容器里有多把锁，每一把锁用于锁容器其中一部分数据，那么当多线程访问容器里不同数据段的数据时，线程间就不会存在锁竞争，从而可以有效的提高并发访问效率，这就是ConcurrentHashMap所使用的锁分段技术，首先将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。有些方法需要跨段，比如size()和containsValue()，它们可能需要锁定整个表而不仅仅是某个段，这需要按顺序锁定所有段，操作完毕后，又按顺序释放所有段的锁。这里”按顺序”是很重要的，否则极有可能出现死锁，在ConcurrentHashMap内部，段数组是final的，并且其成员变量实际上也是final的。但是，仅仅是将数组声明为final的并不保证数组成员也是final的，这需要实现上的保证。这可以确保不会出现死锁，因为获得锁的顺序是固定的。
    ConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成。Segment是一种可重入锁ReentrantLock，在ConcurrentHashMap里扮演锁的角色，HashEntry则用于存储键值对数据。一个ConcurrentHashMap里包含一个Segment数组，Segment的结构和HashMap类似，是一种数组和链表结构，一个Segment里包含一个HashEntry数组，每个HashEntry是一个链表结构的元素，每个Segment守护着一个HashEntry数组里的元素，当对HashEntry数组的数据进行修改时，首先获得它对应的Segment锁。

Your support will encourage me to continue to create!