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!