谈谈HashMap与HashTable

图片 7

本文来自网易云社区

谈谈HashMap与HashTable

前言:
HashMap是Java程序员使用频率最高的用于映射(键值对)处理的数据类型。随着JDK(Java
Developmet
Kit)版本的更新,JDK1.8对HashMap底层的实现进行了优化,例如引入红黑树的数据结构和扩容的优化等。最近刚好有时间,刚好把HashMap相关的内容和之前做唯品会网关的一些经验整理一下。

关于HashMap在并发场景下的问题有很多人,很多公司遇到过!也很多人总结过,我们很多时候都认为这样都坑距离自己很远,自己一定不会掉入这样都坑。可是我们随时都有就遇到了这样都问题,坑一直都在我们身边。今天遇到了一个非线程安全对象在并发场景下使用的问题,通过这个案例分析HashMap
在并发场景下使用存在的问题(当然在这个案例中还有很多问题值得我们去分析,值得大家引以为戒。)通过分析问题产生都原因,让我们今后更好远离这个BUG。

HashMap

我们一直知道HashMap是非线程安全的,HashTable是线程安全的,可这是为什么呢?先聊聊HashMap吧,想要了解它为什么是非线程安全的,我们得从它的原理着手。

一.HashMap的概述

图片 1

jdk7中的HashMap

HashMap底层维护一个数组,数组中的每一项都是Entry

transient Entry<K,V>[] table;

我们向HashMap放置的对象实际上是放置在Entry数组中

而Map中的key、value则以Entry的形式存放在数组中

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

而这个Entry应该放在数组的哪一个位置上(这个位置通常称为位桶或者hash桶,即hash值相同的Entry会放在同一位置,用链表相连),是通过key的hashCode来计算的。

图片 2

当两个key通过hashcode计算是相同的时候,就会发生hash冲突,HashMap解决hash冲突的办法是使用链表。

简而言之就是,jdk1.7的情况:如果该位置没有对象,则将对象直接放到数组中,如果该位置有对象,顺着存在此对象的链找(Map中不允许存在相同的key和value),如果不存在相同的,第一种情况:如果该链表扩容了,则把对象放入到数组中,原先存放在数组中的数据放置该对象的后面。第二种情况:如果该链表没有扩容,则直接放到链表的最后。如果存在相同的,则进行替换。jdk1.8的情况:如果该位置没有对象,则将对象直接放到数组中,如果该位置有对象,顺着存在此对象的链找(Map中不允许存在相同的key和value),如果不存在相同的,则直接放到链表的最后。如果存在相同的,则进行替换。

当HashMap中的元素越来越多的时候,hash冲突的几率也就越来越高,因为数组的长度是固定的。所以为了提高查询的效率,就要对HashMap的数组进行扩容,而在HashMap数组扩容之后,最消耗性能的点就出现了:原数组中的数据必须重新计算其在新数组中的位置,并放进去,这就是resize。

值得注意的是,HashMap中key和value都允许有null值存在,不过只允许一个null的key,可以有多个null值的value。

1.1 HashMap的数据结构

HashMap的内存结构和原理,以及线程安全都是面试的热点问题。Java中的数据结构基本可以用数组+链表的解决。

  • 数组的优缺点:通过下标索引方便查找,但是在数组中插入或删除一个元素比较困难。
  • 链表的优缺点:由于在链表中查找一个元素需要以遍历链表的方式去查找,而插入,删除快速。因此链表适合快速插入和删除的场景,不利于查找

而HashMap就是综合了上述的两种数据结构的优点,HashMap由Entry数组+链表组成,如下图所示:

图片 3

从上图我们可以发现HashMap是由Entry数组+链表组成的,一个长度为16的数组中,每个元素存储的是一个链表的头结点。那么这些元素是按照什么样的规则存储到数组中呢。一般情况是通过hash(key)%len获得,也就是元素的key的哈希值对数组长度取模得到。比如上述哈希表中,12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。

代码如图所示,大家都应该知道HashMap不是线程安全的。那么
HashMap在并发场景下可能存在哪些问题?

jdk8中的HashMap

在JDK1.7的部分就只有链表结构,但是由于链表过长的时候查找元素时间较长,在JDK1.8的时候加入了红黑树,当链表超过一定长度之后,链表就会转换成红黑树,便于查找和插入,在最坏的情况下,链表的时间复杂度是O(n),红黑树是O(logn),这样会提高HashMap的效率。
图片 4

在jdk8中,当同一个hash值得节点数大于8的时候,将不再以链表的形式存储了,而是会调整成一颗红黑树。

static final int TREEIFY_THRESHOLD = 8;

从JDK1.8开始,HashMap的元素是以Node形式存在,主要结构如下:

 static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

JDK中Entry的名字变成了Node,原因是和红黑树的实现TreeNode相关联。

可以看一下jdk8中的put方法,跟jdk7相比还是做了很大的改变。

    public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //如果当前map中无数据,执行resize方法。并且返回n
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //如果要插入的键值对要存放的这个位置刚好没有元素,那么把他封装成Node对象,放在这个位置上就可以了
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        //如果这个元素的key与要插入的一样,那么就替换一下
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
         //如果当前节点是TreeNode类型的数据,存储的链表已经变为红黑树了,执行putTreeVal方法去存入
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
         //还是链表状态
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    //判断是否要转成红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1) 
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    //判断阀值,决定是否扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

1.2 HashMap的存取实现简单说明

  1. 数据丢失

  2. 数据重复

  3. 死循环

HashMap的多线程不安全

个人觉得HashMap在并发时可能出现的问题主要是两方面,首先如果多个线程同时使用put方法添加元素,而且假设正好存在两个put的key发生了碰撞(hash值一样),那么根据HashMap的实现,这两个key会添加到数组的同一个位置,这样最终就会发生其中一个线程的put的数据被覆盖。第二就是如果多个线程同时检测到元素个数超过数组大小*loadFactor,这样就会发生多个线程同时对Node数组进行扩容,都在重新计算元素位置以及复制数据,但是最终只有一个线程扩容后的数组会赋给表,也就是说其他线程的都会丢失,并且各自线程put的数据也丢失。

对第二种不安全的情况进行分析:HashMap的死循环

由于插入过程,新插入元素总是插入到头部,源码如下:

void transfer(Entry[] newTable)  {  
Entry[] src = table;  
int newCapacity = newTable.length;   
for (int j = 0; j < src.length; j++) {  
    Entry<K,V> e = src[j];  
    if (e != null) {  
        src[j] = null; 
        //这里在做插入的过程中,总是将新插入元素放在链表头 
        do {  
            Entry<K,V> next = e.next;  
            int i = indexFor(e.hash, newCapacity);  
            e.next = newTable[i];  
            newTable[i] = e;  
            e = next;  
        } while (e != null);  
    }  
}  
}

解析代码:

e=3

Entry<K,V> next = e.next;  保存了3.next也就是7

e.next = newTable[i];  表示3后面跟着的是null,newTable表示重新建立的一张表

newTable[i] = e; 表示在表的下标的那个位置放的是e(也就是3),也就说下图中的下标为3的地方放了key=3这个对象

e=next;表示e=7了

第二次循环–

Entry<K,V> next = e.next;  保存了7.next也就是5

e.next = newTable[i];   表示7.next=3了,说明3放到7的尾巴上去了

newTable[i] = e;    表示下图中的下标为3的地方放了key=7这个对象

e=next;表示e=5了

又开启了再一次的循环。

图片 5

为什么会发生死循环呢?

解析:多线程情况下,多个线程同时检测到对数组进行扩容

当线程1正好插入了3(e=3),并且保存了e.next(也就7)

CPU正好切到了线程2,并且完成了扩容,如上图所示。

之后我们对线程1继续进行操作,把7也插进线程1中,可以看到如下所示:

图片 6

但是由于受到线程2的影响,e=7,e.next=3,我们后面又得插入3了,然后插入3之后,因为3.next=7,所以我们又插入7,这样就形成了死循环。

这个问题在JDK1.8中得到了解决,它用了新的索引插入方式

Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
//还是原索引位置
if ((e.hash & oldCap) == 0) {
    if (loTail == null)
        loHead = e;
    else
        loTail.next = e;
    loTail = e;
}
//原索引+ oldCap位置
else {
    if (hiTail == null)
        hiHead = e;
    else
        hiTail.next = e;
    hiTail = e;
    }
} while ((e = next) != null);
if (loTail != null) {
   loTail.next = null;
   newTab[j] = loHead;
 }
if (hiTail != null) {
   hiTail.next = null;
newTab[j + oldCap] = hiHead;
} 

由于扩容是在原容量基础上乘以2,那么hash码校验的时候会比原来的多一位,那么只需要比较这个位置是0还是1即可,是1那么就在原索引位置向后位移原容量大小即可,是0就不动。

图片 7

1.2.1 HashMap put方法实现

1.首先HashMap里面实现一个静态内部类Entry,其重要的属性有 key , value, next,从属性key,value我们就能很明显的看出来Entry就是HashMap键值对实现的一个基础bean,我们上面说到HashMap的基础就是一个线性数组,这个数组就是Entry[],Map里面的内容都保存在Entry[]里面。

static class Entry<K,V> implements Map.Entry<K,V> {
      final K key;//Key-value结构的key
      V value;//存储值
      Entry<K,V> next;//指向下一个链表节点
      final int hash;//哈希值
}

2.既然是线性数组,为什么能随机存取?这里HashMap用了一个小算法,大致是这样实现:

 

//存储时:
// 这个hashCode方法这里不详述,只要理解每个key的hash是一个固定的int值
int hash = key.hashCode();
int index = hash % Entry[].length;
Entry[index] = value;
//取值时:
int hash = key.hashCode();
int index = hash % Entry[].length;
return Entry[index];

到这里我们轻松的理解了HashMap通过键值对实现存取的基本原理

3.疑问:如果两个key通过hash%Entry[].length得到的index相同,会不会有覆盖的危险?

  这里HashMap里面用到链式数据结构的一个概念。上面我们提到过Entry类里面有一个next属性,作用是指向下一个Entry。打个比方,
第一个键值对A进来,通过计算其key的hash得到的index=0,记做:Entry[0] =
A。一会后又进来一个键值对B,通过计算其index也等于0,现在怎么办?HashMap会这样做:B.next
= A,Entry[0] = B,如果又进来C,index也等于0,那么C.next = B,Entry[0] =
C;这样我们发现index=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起。所以疑问不用担心。也就是说数组中存储的是最后插入的元素。到这里为止,HashMap的大致实现,我们应该已经清楚了。

  当然HashMap里面也包含一些优化方面的实现,这里也说一下。比如:Entry[]的长度一定后,随着map里面数据的越来越长,这样同一个index的链就会很长,会不会影响性能?HashMap里面设置一个因素(也称为因子),随着map的size越来越大,Entry[]会以一定的规则加长长度。
     

关于死循环的问题,在Java8中个人认为是不存在了,在Java8之前的版本中之所以出现死循环是因为在resize的过程中对链表进行了倒序处理;在Java8中不再倒序处理,自然也不会出现死循环。

HashTable

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 = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    @SuppressWarnings("unchecked")
    Entry<K,V> entry = (Entry<K,V>)tab[index];
    for(; entry != null ; entry = entry.next) {
        if ((entry.hash == hash) && entry.key.equals(key)) {
            V old = entry.value;
            entry.value = value;
            return old;
        }
    }

    addEntry(hash, key, value, index);
    return null;
}

在主要的函数上都加了synchronize同步关键字,所有线程竞争同一把锁,所以线程安全。

二.HashMap非线程安全

对这个问题Doug Lea 是这样说的:

2.1 HashMap进行Put操作

Doug Lea writes:"This is a classic symptom of an incorrectly synchronized use ofHashMap. Clearly, the submitters need to use a thread-safeHashMap. If they upgraded to Java 5, they could just useConcurrentHashMap. If they can't do this yet, they can useeither the pre-JSR166 version, or better, the unofficial backportas mentioned by Martin. If they can't do any of these, they canuse Hashtable or synchhronizedMap wrappers, and live with poorerperformance. In any case, it's not a JDK or JVM bug."I agree that the presence of a corrupted data structure alonedoes not indicate a bug in the JDK.

2.1.1 Jdk8以下HashMap的Put操作

put操作主要是判空,对key的hashcode执行一次HashMap自己的哈希函数,得到bucketindex位置,还有对重复key的覆盖操作。

在HashMap做put操作的时候会调用到以下的方法,addEntry和createEntry

public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        //得到key的hashcode,同时再做一次hash操作
        int hash = hash(key.hashCode());
        //对数组长度取余,决定下标位置
        int i = indexFor(hash, table.length);
        /**
          * 首先找到数组下标处的链表结点,
          * 判断key对一个的hash值是否已经存在,如果存在将其替换为新的value
          */
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            //Hash碰撞的解决
            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;
    }

涉及到的几个方法:

 

static int hash(int h) {
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

static int indexFor(int h, int length) {
        return h & (length-1);
    }

现在假如A线程和B线程同时进入addEntry,然后计算出了相同的哈希值对应了相同的数组位置,因为此时该位置还没数据,然后对同一个数组位置调用createEntry,两个线程会同时得到现在的头结点,然后A写入新的头结点之后,B也写入新的头结点,那B的写入操作就会覆盖A的写入操作造成A的写入操作丢失。

You can leave a response, or trackback from your own site.

Leave a Reply

网站地图xml地图