欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

为什么HashMap不是线程安全的 博客分类: java javahashmaphashtable线程安全线程不安全 

程序员文章站 2024-03-24 20:43:04
...

最近因为项目的需求,经常会面试一些新人,也就会问他们一些基本的问题,例如,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的底层存储结构的前提来举例的,如果底层结构不了解,那么此文看起来就可能很迷糊。