为什么HashMap不是线程安全的

序

最近因为项目的需求，经常会面试一些新人，也就会问他们一些基本的问题，例如，HashMap和HashTable的区别是什么，一般人想到的就是HashMap不是线程安全，这点我想几乎来面试的人都知道，但是再深入问下为什么HashMap不是线程安全的，几乎没有人答上来，当然了，我也不会因为你回答不上来就认为能力不行，只能认为是这个题目是一道附加题，大家都懂得，下面我们就简单看下为什么HashMap不是线程安全的。

 

正文

例如我有几个线程同时给里面放入元素，key为线程的名字，value为一个对象，也可以是一个list，暂且不管，好了，现在我们一起看源代码吧。

public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
//此时的hash值是根据传入的key值进行hash得到的，尽管有些人认为线程的名字命名的好的话就不会有hash相同的情况，即使如此也是有可能的，这里我们就假如hash的结果是相同的
        int hash = hash(key);
        int i = indexFor(hash, table.length);//此时的i也是相同的。
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);//跟进去看下
        return null;
    }

 

进入addEntry方法

void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }
        //假设都是第一次进入这个方法的，那么此时table数组应该是空的。
        createEntry(hash, key, value, bucketIndex);
    }

 

进入createEntry方法

void createEntry(int hash, K key, V value, int bucketIndex) {
//加入有很小的概率两个线程同时进入这个方法，并且此时的hash和bucketIndex是一模一样的，那么此时就会有问题了，两个线程在同时在同一个数组的位置放入Entry链表，所以就出现了线程安全的问题
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }

 

同样的，在addEntry方法中的如果判断容量超过了限制，就会扩容，此时resize也是会有问题的

void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

 

删除一个元素呢？其实在某种场景下也是会有问题的。

final Entry<K,V> removeEntryForKey(Object key) {
        if (size == 0) {
            return null;
        }
        int hash = (key == null) ? 0 : hash(key);
        int i = indexFor(hash, table.length);
        //(1)
        Entry<K,V> prev = table[i];
        Entry<K,V> e = prev;

        while (e != null) {
            Entry<K,V> next = e.next;
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k)))) {
                modCount++;
                size--;
               //(2)
                if (prev == e)
                    table[i] = next;
                else
                    prev.next = next;
                e.recordRemoval(this);
                return e;
            }
            prev = e;
            e = next;
        }

        return e;
    }

 在（1）处时，根据i获取了对应数组的链表的头部，然后在（2）处进行把链表的头部指定为当前头部的下一个元素，如果此时恰巧有另外一个线程在此处放入了一个元素，虽然几率不大，但是总有可能发生，因此还是线程不安全的。

 

再看下HashTable的源码：

public synchronized V put(K key, V value) {
        // Make sure the value is not null
        if (value == null) {
            throw new NullPointerException();
        }

        // Makes sure the key is not already in the hashtable.
        Entry tab[] = table;
        int hash = hash(key);
        int index = (hash & 0x7FFFFFFF) % tab.length;
        for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                V old = e.value;
                e.value = value;
                return old;
            }
        }

public synchronized V remove(Object key) {
        Entry tab[] = table;
        int hash = hash(key);
        int index = (hash & 0x7FFFFFFF) % tab.length;
        for (Entry<K,V> e = tab[index], prev = null ; e != null ; prev = e, e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                modCount++;
                if (prev != null) {
                    prev.next = e.next;
                } else {
                    tab[index] = e.next;
                }
                count--;
                V oldValue = e.value;
                e.value = null;
                return oldValue;
            }
        }
        return null;
    }

public synchronized V get(Object key) {
        Entry tab[] = table;
        int hash = hash(key);
        int index = (hash & 0x7FFFFFFF) % tab.length;
        for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) && e.key.equals(key)) {
                return e.value;
            }
        }
        return null;
    }

 全部都同步了，因此敢说HashTable是线程安全的。

 

PS： 本文是基于我们已经知道了HashMap的底层存储结构的前提来举例的，如果底层结构不了解，那么此文看起来就可能很迷糊。

评论

1 楼 welcomezhang 2016-06-20  

学习了，这块自己还得深挖下