1. 9IM首页
  2. 热点

HashMap与HashTable,ConcurrentHashMap的区别

主要从底层数据结构,线程安全,执行效率,是否允许Null值,初始容量及扩容,hash值计算来进行分析。

1.底层数据结构

    transient Node<K,V>[] table; //HashMap
    
    transient volatile Node<K,V>[] table;//ConcurrentHashMap
    
    private transient Entry<?,?>[] table;//HashTable

HashMap=数组+链表+红黑树

HashMap的底层数据结构是一个数组+链表+红黑树,数组的每个元素存储是一个链表的头结点,链表中存储了一组哈希值冲突的键值对,通过链地址法来解决哈希冲突的。为了避免链表长度过长,影响查找元素的效率,当链表的长度>8时,会将链表转换为红黑树,链表的长度<6时,将红黑树转换为链表(但是红黑树转换为链表的时机不是在删除链表时,而是在扩容时,发现红黑树分解后的两个链表<6,就按链表处理,否则就建立两个小的红黑树,设置到扩容后的位置)。之所以临界点为8是因为红黑树的查找时间复杂度为logN,链表的平均时间查找复杂度为N/2,当N为8时,logN为3,是小于N/2的,正好可以通过转换为红黑树减少查找的时间复杂度。

Hashtable=数组+链表

Hashtable底层数据结构跟HashMap一致,底层数据结构是一个数组+链表,也是通过链地址法来解决冲突,只是链表过长时,不会转换为红黑树来减少查找时的时间复杂度。Hashtable属于历史遗留类,实际开发中很少使用。

ConcurrentHashMap=数组+链表+红黑树

ConcurrentHashMap底层数据结构跟HashMap一致,底层数据结构是一个数组+链表+红黑树。只不过使用了volatile来进行修饰它的属性,来保证内存可见性(一个线程修改了这些属性后,会使得其他线程中对于该属性的缓存失效,以便下次读取时取最新的值)。

2.线程安全

HashMap 非线程安全

HashMap是非线程安全的。(例如多个线程插入多个键值对,如果两个键值对的key哈希冲突,可能会使得两个线程在操作同一个链表中的节点,导致一个键值对的value被覆盖)

HashTable 线程安全

HashTable是线程安全的,主要通过使用synchronized关键字修饰大部分方法,使得每次只能一个线程对HashTable进行同步修改,性能开销较大。

ConcurrentHashMap 线程安全

ConcurrentHashMap是线程安全的,主要是通过CAS操作+synchronized来保证线程安全的。

CAS操作

往ConcurrentHashMap中插入新的键值对时,如果对应的数组下标元素为null,那么通过CAS操作原子性地将节点设置到数组中。

//这是添加新的键值对的方法
final V putVal(K key, V value, boolean onlyIfAbsent) {
...其他代码
  if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
    if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null))) 				break; // 因为对应的数组下标元素为null,所以null作为预期值,new Node<K,V>(hash, key, value, null)作为即将更新的值,只有当内存中的值与即将预期值一致时,才会进行更新,保证原子性。
  }
...其他代码
}
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
                                        Node<K,V> c, Node<K,V> v) {
        return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}

synchronized锁

往ConcurrentHashMap中插入新的键值对时,如果对应的数组下标元素不为null,那么会对数组下标存储的元素(也就是链表的头节点)加synchronized锁, 然后进行插入操作,

Node<K,V> f = tabAt(tab, i = (n - 1) & hash));
synchronized (f) {//f就是数组下标存储的元素
    if (tabAt(tab, i) == f) {
        if (fh >= 0) {
            binCount = 1;
            for (Node<K,V> e = f;; ++binCount) {
                K ek;
                if (e.hash == hash &&
                    ((ek = e.key) == key ||
                     (ek != null && key.equals(ek)))) {
                    oldVal = e.val;
                    if (!onlyIfAbsent)
                        e.val = value;
                    break;
                }
                Node<K,V> pred = e;
                if ((e = e.next) == null) {
                    pred.next = new Node<K,V>(hash, key,
                                              value, null);
                    break;
                }
            }
        }
        else if (f instanceof TreeBin) {
            Node<K,V> p;
            binCount = 2;
            if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                           value)) != null) {
                oldVal = p.val;
                if (!onlyIfAbsent)
                    p.val = value;
            }
        }
    }
}

3.执行效率

因为HashMap是非线程安全的,执行效率会高一些,其次是ConcurrentHashMap,因为HashTable在进行修改和访问时是对整个HashTable加synchronized锁,所以效率最低。

4.是否允许null值出现

HashMap的key和null都可以为null,如果key为null,那么计算的hash值会是0,最终计算得到的数组下标也会是0,所以key为null的键值对会存储在数组中的首元素的链表中。value为null的键值对也能正常插入,跟普通键值对插入过程一致。

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

HashTable的键和值都不能为null,如果将HashTable的一个键值对的key设置为null,因为null值没法调用hashCode()方法获取哈希值,所以会抛出空指针异常。同样value为null时,在put方法中会进行判断,然后抛出空指针异常。

public synchronized V put(K key, V value) {
        // Make sure the value is not null
        if (value == null) {
            throw new NullPointerException();
        }
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        ...其他代码
}

ConcurrentHashMap的键和值都不能为null,在putVal方法中会进行判断,为null会抛出空指针异常。

final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());
    ...其他代码
}

5.初始容量及扩容

不指定初始容量

如果不指定初始容量,HashMap和ConcurrentHashMap默认会是16,HashTable的容量默认会是11。

不指定初始容量

如果制定了初始容量,HashMap和ConcurrentHashMap的容量会是比初始容量稍微大一些的2的幂次方大小,HashTable会使用初始容量,

扩容

扩容时,HashMap和ConcurrentHashMap扩容时会是原来长度的两倍,HashTable则是2倍加上1.

6.hash值计算

HashTable会扩容为2n+1,HashTable之所以容量取11,及扩容时是是2n+1,是为了保证 HashTable的长度是一个素数,因为数组的下标是用key的hashCode与数组的长度取模进行计算得到的,而当数组的长度是素数时,可以保证计算得到的数组下标分布得更加均匀

public synchronized V put(K key, V value) {
         ...其他代码
        // Makes sure the key is not already in the hashtable.
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash & 0x7FFFFFFF) % tab.length;
        ...其他代码
}

HashMap和ConcurrentHashMap的hash值都是通过将key的hashCode()高16位与低16位进行异或运算(这样可以保留高位的特征,避免一些key的hashCode高位不同,低位相同,造成hash冲突),得到hash值,然后将hash&(n-1)计算得到数组下标。(n为数组的长度,因为当n为2的整数次幂时,hash mod n的结果在数学上等于hash&(n-1),而且计算机进行&运算更快,所以这也是HashMap的长度总是设置为2的整数次幂的原因)

//HashMap计算hash值的方法
static int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); 
}
//ConcurrentHashMap计算hash值的方法 
static  int spread(int h) {//h是对象的hashCode
    return (h ^ (h >>> 16)) & HASH_BITS;// HASH_BITS = 0x7fffffff;
}
  

原创文章,作者:9IM,如若转载,请注明出处:https://www.9im.cn/668.html

发表评论

电子邮件地址不会被公开。 必填项已用*标注