HashTable,HashMap与ConcurrentHashMap源码分析

HashMap与HashTable是两个颇为相似的类。抽象的说,都是键值对集合,那么它们之前到达有什么区别呢?似乎面试也常考啊,我们从原理的角度来分析一下。

我们先来看看HashTable的代码:

HashTable

首先,HashTable的核心是一个键值对数组。如下:

HashtableEntry<K, V>[] table;

而键值对HashtableEntry的代码我们可以看到:

    private static class HashtableEntry<K, V> implements Entry<K, V> {
        final K key;
        V value;
        final int hash;
        HashtableEntry<K, V> next;

        HashtableEntry(K key, V value, int hash, HashtableEntry<K, V> next) {
            this.key = key;
            this.value = value;
            this.hash = hash;
            this.next = next;
        }

        public final K getKey() {
            return key;
        }

        public final V getValue() {
            return value;
        }

        public final V setValue(V value) {
            if (value == null) {
                throw new NullPointerException("value == null");
            }
            V oldValue = this.value;
            this.value = value;
            return oldValue;
        }

        @Override public final boolean equals(Object o) {
            if (!(o instanceof Entry)) {
                return false;
            }
            Entry<?, ?> e = (Entry<?, ?>) o;
            return key.equals(e.getKey()) && value.equals(e.getValue());
        }

        @Override public final int hashCode() {
            return key.hashCode() ^ value.hashCode();
        }

        @Override public final String toString() {
            return key + "=" + value;
        }
    }

HashtablEntry是一个链表。它持有了一个键值对、一个hash值和链表中下一个元素。那么为什么HashTable的键值对需要一个链表呢,键值对只有一个key和value不是就可以了吗?为了回答上面的问题,我们需要再来看看HashTable中put(K , V)方法的实现:

   public synchronized V put(K key, V value) {
       if (key == null) {
           throw new NullPointerException("key == null");
       } else if (value == null) {
           throw new NullPointerException("value == null");
       }
       int hash = Collections.secondaryHash(key);
       HashtableEntry<K, V>[] tab = table;
       int index = hash & (tab.length - 1);
       HashtableEntry<K, V> first = tab[index];
       for (HashtableEntry<K, V> e = first; e != null; e = e.next) {
           if (e.hash == hash && key.equals(e.key)) {
               V oldValue = e.value;
               e.value = value;
               return oldValue;
           }
       }

       // No entry for key is present; create one
       modCount++;
       if (size++ > threshold) {
           rehash();  // Does nothing!!
           tab = doubleCapacity();
           index = hash & (tab.length - 1);
           first = tab[index];
       }
       tab[index] = new HashtableEntry<K, V>(key, value, hash, first);
       return null;
   }

上面的代码我们首先要注意到synchronized,这个说明HashTable很大可能是线程安全的,进入方法后我们可以看到,需要put一对键值对进来时,我们首先会从table中取出相应hash位置的键值对,然后进行一个循环,如果hash和key均相等,则替换掉现有的值,直接return了。

那么这里就有一种意外的情况,是不是有可能hash相等,key不相等。即哈希冲突。

在这样的情况下,我们发现HashTable选择将所有hash相等的键值对,存成一个链表。这样,每次我们既可以用hash值,统一索引位置,又可以避免hash冲突。

剩下的代码就是扩容、创建新的键值对,然后将新的键值对存入table。这里还会将和它hash值相同的链表,放在它的尾部。

我们再看看get(Object key)方法,与我们上面描述的原理相对应。

    public synchronized V get(Object key) {
        int hash = Collections.secondaryHash(key);
        HashtableEntry<K, V>[] tab = table;
        for (HashtableEntry<K, V> e = tab[hash & (tab.length - 1)];
                e != null; e = e.next) {
            K eKey = e.key;
            if (eKey == key || (e.hash == hash && key.equals(eKey))) {
                return e.value;
            }
        }
        return null;
    }

每次HashTable并不能直接在table中取得正确的值。取到的只是一个hash能够对应上的链表。然后,在这个链表中进行遍历,取到正确的值。这个方法叫“拉链法”。


HashMap

HashMapEntry的代码与HashTableEntry的代码几乎完全一样。因此,我们直接看put和get方法。

    @Override public V put(K key, V value) {
        if (key == null) {
            return putValueForNullKey(value);
        }

        int hash = Collections.secondaryHash(key);
        HashMapEntry<K, V>[] tab = table;
        int index = hash & (tab.length - 1);
        for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) {
            if (e.hash == hash && key.equals(e.key)) {
                preModify(e);
                V oldValue = e.value;
                e.value = value;
                return oldValue;
            }
        }

        // No entry for (non-null) key is present; create one
        modCount++;
        if (size++ > threshold) {
            tab = doubleCapacity();
            index = hash & (tab.length - 1);
        }
        addNewEntry(key, value, hash, index);
        return null;
    }

我们发现put的方法也非常接近。只有一些细微的不同:

  1. HashMap的put方法没有加锁,因此HashMap并非线程安全的。
  2. HashMap的put方法,允许key和value为空。
  3. HashTable中有一个contains方法很容易引起误解,已在HashMap中取消。
    public boolean contains(Object value) {
        return containsValue(value);
    }

ConcurrentHashMap

我们直接看ConcurrentHashMap的put方法:

    public V put(K key, V value) {
        return putVal(key, value, false);
    }

    /** Implementation for put and putIfAbsent */
    final V putVal(K key, V value, boolean onlyIfAbsent) {
        if (key == null || value == null) throw new NullPointerException();
        int hash = spread(key.hashCode());
        int binCount = 0;
        for (Node<K,V>[] tab = table;;) {
            Node<K,V> f; int n, i, fh;
            if (tab == null || (n = tab.length) == 0)
                tab = initTable();
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                if (casTabAt(tab, i, null,
                             new Node<K,V>(hash, key, value, null)))
                    break;                   // no lock when adding to empty bin
            }
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            else {
            ...
        }
        addCount(1L, binCount);

由于代码比较长,我们来逐段分析。其中Node的结构和我们前面所说的HashMapEntry非常类似是一个链表的节点。table也与前面一样是个Node的数组。代码首先就进入了死循环,获取了table对象,如果table为空则会创建一个table,如果hash值所在的索引为空(即之前没有相同的key存放在Map中),则直接通过CAS原子操作赋值并退出循环。

接下来我们看看,如果ConcurrentHashMap中已经存在了相同的key,ConcurrentHashMap是如何工作的。

                V oldVal = null;
                synchronized (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;
                            }
                        }
                    }
                }
                if (binCount != 0) {
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }

这段代码首先锁定了Node<K,V> f。并重新判断了f有没有被改变,如果已经发生改变程序会跑出同步锁,binCount为0,会继续循环。如果没有改变,且f的hash值不小于0,则binCount = 1。此时已经决定死循环一定会退出。此时再进入新的循环,和HashMap非常类似,通过拉链法防哈希冲突。

接下来我们再来看看ConcurrentHashMap的get方法:

    public V get(Object key) {
        Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
        int h = spread(key.hashCode());
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (e = tabAt(tab, (n - 1) & h)) != null) {
            if ((eh = e.hash) == h) {
                if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                    return e.val;
            }
            else if (eh < 0)
                return (p = e.find(h, key)) != null ? p.val : null;
            while ((e = e.next) != null) {
                if (e.hash == h &&
                    ((ek = e.key) == key || (ek != null && key.equals(ek))))
                    return e.val;
            }
        }
        return null;
    }

由于在并发中,读并不是很受影响。所以ConcurrentHashMap的get方法与HashMap的get方法比较相似。如果hash和key均相等则直接取出,只是hash相等则需要在链表中遍历寻找key相等的对象。


通过分析三个类的源码分析,我们尝试总结一些结论:

共同点:
  • 通过拉链法防哈希碰撞
HashTable:
  • 通过synchronized关键词锁定方法,保证线程安全。
  • key和value均不能为空
  • 有一个容易被误解的contains,其实就是containsValue
HashMap:
  • 不保证线程安全
  • key和value均可以为空
  • 不再有contains方法
ConcurrentHashMap:
  • 通过死循环检测值是否相等,然后CAS的方式保证线程安全。只有在确认需要更换已有对象时才会加锁
  • key和value均不能为空

以上。 水平有限,望斧正。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Golang语言社区

问题帖子--Concurrent Read/Write Map

DK1.5 引入了 concurrent package, 提供了更多的concurrent 控制方法。 还提供了一个 ConcurrentHashMap 类...

3305
来自专栏Golang语言社区

问题帖子--Concurrent Read/Write Map

DK1.5 引入了 concurrent package, 提供了更多的concurrent 控制方法。 还提供了一个 ConcurrentHashMap 类...

34312
来自专栏杂烩

spring的XML装配 原

673
来自专栏微信公众号:Java团长

HashMap和Hashtable的区别

HashMap和Hashtable的比较是Java面试中的常见问题,用来考验程序员是否能够正确使用集合类以及是否可以随机应变使用多种思路解决问题。HashMap...

871
来自专栏IT可乐

JDK1.8源码(七)——java.util.HashMap 类

  本篇博客我们来介绍在 JDK1.8 中 HashMap 的源码实现,这也是最常用的一个集合。但是在介绍 HashMap 之前,我们先介绍什么是 Hash表。...

3526
来自专栏博岩Java大讲堂

Java集合--ConcurrentMap

3459
来自专栏butterfly100

ConcurrentHashMap源码阅读

1. 前言 HashMap是非线程安全的,在多线程访问时没有同步机制,并发场景下put操作可能导致同一数组下的链表形成闭环,get时候出现死循环,导致CPU利用...

2657
来自专栏Phoenix的Android之旅

你不知道的HashMap

面试中经常会问到常用数据结构,比如HashMap。 相信你平时几乎每天都会用到HashMap,但是你知道它是的实现原理是怎样的吗? 这里先提几个问题:HashM...

753
来自专栏Java爬坑系列

【Java入门提高篇】Day26 Java容器类详解(八)HashSet源码分析

  前面花了好几篇的篇幅把HashMap里里外外说了个遍,大家可能对于源码分析篇已经讳莫如深了。

724
来自专栏大数据架构

Java进阶(六)从ConcurrentHashMap的演进看Java多线程核心技术

2005

扫码关注云+社区