JavaJava基础与提高java Web

HashMap底层实现和原理

2019-08-08  本文已影响296人  奇点一氪

文章的内容基于JDK1.7进行分析。1.8做的改动文章末尾进行讲解。

一、先来熟悉一下我们常用的HashMap:

1、概述

HashMap基于Map接口实现,元素以键值对的方式存储,并且允许使用null 建和null 值,因为key不允许重复,因此只能有一个键为null,另外HashMap不能保证放入元素的顺序,它是无序的,和放入的顺序并不能相同。HashMap是线程不安全的。

2、继承关系

public class HashMap<K,V>extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable

3、基本属性

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //默认初始化大小 16 
static final float DEFAULT_LOAD_FACTOR = 0.75f;     //负载因子0.75
static final Entry<?,?>[] EMPTY_TABLE = {};         //初始化的默认数组
transient int size;     //HashMap中元素的数量
int threshold;          //判断是否需要调整HashMap的容量  
Note:HashMap的扩容操作是一项很耗时的任务,所以如果能估算Map的容量,最好给它一个默认初始值,避免进行多次扩容。HashMap的线程是不安全的,多线程环境中推荐是ConcurrentHashMap。

二、常被问到的HashMap和Hashtable的区别

1、线程安全

两者最主要的区别在于Hashtable是线程安全,而HashMap则非线程安全。
Hashtable的实现方法里面添加了synchronized关键字来确保线程同步,因此相对而言HashMap性能会高一些,我们平时使用时若无特殊需求建议使用HashMap,在多线程环境下若使用HashMap需要使用Collections.synchronizedMap()方法来获取一个线程安全的集合。

Note:Collections.synchronizedMap()实现原理是Collections定义了一个SynchronizedMap的内部类,这个类实现了Map接口,在调用方法时使用synchronized来保证线程同步,当然了实际上操作的还是我们传入的HashMap实例,简单的说就是Collections.synchronizedMap()方法帮我们在操作HashMap时自动添加了synchronized来实现线程同步,类似的其它Collections.synchronizedXX方法也是类似原理。

2、针对null的不同

HashMap可以使用null作为key,而Hashtable则不允许null作为key
虽说HashMap支持null值作为key,不过建议还是尽量避免这样使用,因为一旦不小心使用了,若因此引发一些问题,排查起来很是费事。

Note:HashMap以null作为key时,总是存储在table数组的第一个节点上。

3、继承结构

HashMap是对Map接口的实现,HashTable实现了Map接口和Dictionary抽象类。

4、初始容量与扩容

HashMap的初始容量为16,Hashtable初始容量为11,两者的填充因子默认都是0.75。
HashMap扩容时是当前容量翻倍即:capacity2,Hashtable扩容时是容量翻倍+1即:capacity2+1。

5、两者计算hash的方法不同

Hashtable计算hash是直接使用key的hashcode对table数组的长度直接进行取模

int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;

HashMap计算hash对key的hashcode进行了二次hash,以获得更好的散列值,然后对table数组长度取摸。

int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);

static int hash(int h) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }
 
 static int indexFor(int h, int length) {
        return h & (length-1);

三、HashMap的数据存储结构

1、HashMap由数组和链表来实现对数据的存储

HashMap采用Entry数组来存储key-value对,每一个键值对组成了一个Entry实体,Entry类实际上是一个单向的链表结构,它具有Next指针,可以连接下一个Entry实体,以此来解决Hash冲突的问题。

数组存储区间是连续的,占用内存严重,故空间复杂的很大。但数组的二分查找时间复杂度小,为O(1);数组的特点是:寻址容易,插入和删除困难;

链表存储区间离散,占用内存比较宽松,故空间复杂度很小,但时间复杂度很大,达O(N)。链表的特点是:寻址困难,插入和删除容易。


image.png
image.png
image.png

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

HashMap里面实现一个静态内部类Entry,其重要的属性有 hash,key,value,next。

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的大致实现,我们应该已经清楚了。

public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value); //null总是放在数组的第一个链表中
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        //遍历链表
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            //如果key在链表中已存在,则替换为新value
            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;
    }
什么时候扩容:

当向容器添加元素的时候,会判断当前容器的元素个数,如果大于等于阈值(知道这个阈字怎么念吗?不念fa值,念yu值四声)---即当前数组的长度乘以加载因子的值的时候,就要自动扩容啦。

扩容(resize)介绍:

就是重新计算容量,向HashMap对象里不停的添加元素,而HashMap对象内部的数组无法装载更多的元素时,对象就需要扩大数组的长度,以便能装入更多的元素。当然Java里的数组是无法自动扩容的,方法是使用一个新的数组代替已有的容量小的数组,就像我们用一个小桶装水,如果想装更多的水,就得换大水桶。

HashMap 添加节点和扩容(resize)
/** 
 * HashMap 添加节点 
 * 
 * @param hash        当前key生成的hashcode 
 * @param key         要添加到 HashMap 的key 
 * @param value       要添加到 HashMap 的value 
 * @param bucketIndex 桶,也就是这个要添加 HashMap 里的这个数据对应到数组的位置下标 
 */  
void addEntry(int hash, K key, V value, int bucketIndex) {  
    //size:The number of key-value mappings contained in this map.  
    //threshold:The next size value at which to resize (capacity * load factor)  
    //数组扩容条件:1.已经存在的key-value mappings的个数大于等于阈值  
    //             2.底层数组的bucketIndex坐标处不等于null  
    if ((size >= threshold) && (null != table[bucketIndex])) {  
        resize(2 * table.length);//扩容之后,数组长度变了  
        hash = (null != key) ? hash(key) : 0;//为什么要再次计算一下hash值呢?  
        bucketIndex = indexFor(hash, table.length);//扩容之后,数组长度变了,在数组的下标跟数组长度有关,得重算。  
    }  
    createEntry(hash, key, value, bucketIndex);  
}  
  
/** 
 * 这地方就是链表出现的地方,有2种情况 
 * 1,原来的桶bucketIndex处是没值的,那么就不会有链表出来啦 
 * 2,原来这地方有值,那么根据Entry的构造函数,把新传进来的key-value mapping放在数组上,原来的就挂在这个新来的next属性上了 
 */  
void createEntry(int hash, K key, V value, int bucketIndex) {  
    HashMap.Entry<K, V> e = table[bucketIndex];  
    table[bucketIndex] = new HashMap.Entry<>(hash, key, value, e);  
    size++;  
}
分析下resize的源码

鉴于JDK1.8融入了红黑树,较复杂,为了便于理解我们仍然使用JDK1.7的代码,好理解一些,本质上区别不大,具体区别后文再说。

void resize(int newCapacity) {   //传入新的容量
        Entry[] oldTable = table;    //引用扩容前的Entry数组
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {  //扩容前的数组大小如果已经达到最大(2^30)了
            threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1),这样以后就不会扩容了
            return;
        }
 
        Entry[] newTable = new Entry[newCapacity];  //初始化一个新的Entry数组
        transfer(newTable);                         //!!将数据转移到新的Entry数组里
        table = newTable;                           //HashMap的table属性引用新的Entry数组
        threshold = (int) (newCapacity * loadFactor);//修改阈值

这里就是使用一个容量更大的数组来代替已有的容量小的数组,transfer()方法将原有Entry数组的元素拷贝到新的Entry数组里。

void transfer(Entry[] newTable) {
        Entry[] src = table;                   //src引用了旧的Entry数组
        int newCapacity = newTable.length;
        for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组
            Entry<K, V> e = src[j];             //取得旧Entry数组的每个元素
            if (e != null) {
                src[j] = null;//释放旧Entry数组的对象引用(for循环后,旧的Entry数组不再引用任何对象)
                do {
                    Entry<K, V> next = e.next;
                    int i = indexFor(e.hash, newCapacity); //!!重新计算每个元素在数组中的位置
                    e.next = newTable[i]; //标记[1]
                    newTable[i] = e;      //将元素放在数组上
                    e = next;             //访问下一个Entry链上的元素
                } while (e != null);
            }
        }
}

newTable[i]的引用赋给了e.next,也就是使用了单链表的头插入方式,同一位置上新元素总会被放在链表的头部位置;这样先放在一个索引上的元素终会被放到Entry链的尾部(如果发生了hash冲突的话),这一点和Jdk1.8有区别,下文详解。在旧数组中同一条Entry链上的元素,通过重新计算索引位置后,有可能被放到了新数组的不同位置上。

详细介绍for循环内部这个转存的过程和怎么进行头插入

Entry<K, V> e = src[j];
这句话,就把原来数组上的那个链表的引用就给接手了,所以下面src[j] = null;可以放心大胆的置空,释放空间。告诉gc这个地方可以回收啦。
继续到do while 循环里面,
Entry<K, V> next = e.next;
int i = indexFor(e.hash, newCapacity);计算出元素在新数组中的位置
下面就是单链表的头插入方式转存元素啦

关于这个 单链表的头插入方式 的理解,我多说两句。
这地方我再看的时候,就有点蒙了,他到底怎么在插到新的数组里面的?
要是在插入新数组的时候,也出现了一个数组下标的位置处,出现了多个节点的话,那又是怎么插入的呢?
1,假设现在刚刚插入到新数组上,因为是对象数组,数组都是要默认有初始值的,那么这个数组的初始值都是null。不信的可以新建个Javabean数组测试下。
那么e.next = newTable[i],也就是e.next = null啦。然后再newTable[i] = e;也就是 说这个时候,这个数组的这个下标位置的值设置成这个e啦。
2,假设这个时候,继续上面的循环,又取第二个数据e2的时候,恰好他的下标和刚刚上面的那个下标相同啦,那么这个时候,是又要有链表产生啦、
e.next = newTable[i];,假设上面第一次存的叫e1吧,那么现在e.next = newTable[i];也就是e.next = e1;
然后再,newTable[i] = e;,把这个后来的赋值在数组下标为i的位置,当然他们两个的位置是相同的啦。然后注意现在的e,我们叫e2吧。e2.next指向的是刚刚的e1,e1的next是null。

static int indexFor(int h, int length) {
    return h & (length-1);
}
8的二进制表示:1000
8&(length-1)= 1000 & 1110 = 1000,索引值即为8;

9的二进制表示:1001
9&(length-1)= 1001 & 1110 = 1000,索引值也为8;

这样一来就产生了相同的索引值,也就是说两个hash值为8和9的key会定位到数组中的同一个位置上形成链表,这就产生了碰撞。

而查询的时候需要遍历这个链表,这样就降低了查询的效率。同时,我们也可以发现,当数组长度为15的时候,hash值会与length-1(1110)进行按位与,那么最后一位永远是0,而0001,0011,0101,1001,1011,0111,1101这几个位置永远都不能存放元素了,会造成严重的空间浪费,更糟的是这种情况下,数组可以使用的位置比数组长度小了很多,这意味着进一步增加了碰撞的几率,减慢了查询的效率。

因此可以看出,只有当数组长度为2的n次方时,不同的key计算得出的index索引相同的几率才会较小,数据在数组上分布也比较均匀,碰撞的几率也小,相对的,查询的时候就不用遍历某个位置上的链表,这样查询效率也就较高了。

此外,位运算快于十进制运算,hashmap扩容也是按位扩容,这样同时也提高了运算效率。

关于什么时候resize()的说明:

最后总结一下:

就是这个map里面包含的元素,也就是size的值,大于等于这个阈值的时候,才会resize();
具体到实际情况就是:假设现在阈值是4;在添加下一个假设是第5个元素的时候,这个时候的size还是原来的,还没加1,size=4,那么阈值也是4的时候,
当执行put方法,添加第5个的时候,这个时候,4 >= 4。元素个数等于阈值。就要resize()啦。添加第4的时候,还是3 >= 4不成立,不需要resize()。
经过这番解释,可以发现下面的这个例子,不应该是在添加第二个的时候resize(),而是在添加第三个的时候,才resize()的。
这个也是我后来再细看的时候,发现的。当然,这个咱可以先忽略,重点看如何resize(),以及如何将旧数据移动到新数组的


image.png

下面我们讲解下JDK1.8做了哪些优化。经过观测可以发现,我们使用的是2次幂的扩展(指长度扩为原来2倍),所以,

经过rehash之后,元素的位置要么是在原位置,要么是在原位置再移动2次幂的位置。对应的就是下方的resize的注释。

/** 
 * Initializes or doubles table size.  If null, allocates in 
 * accord with initial capacity target held in field threshold. 
 * Otherwise, because we are using power-of-two expansion, the 
 * elements from each bin must either stay at same index, or move 
 * with a power of two offset in the new table. 
 * 
 * @return the table 
 */  
final Node<K,V>[] resize() {  }

看下图可以明白这句话的意思,n为table的长度,图(a)表示扩容前的key1和key2两种key确定索引位置的示例,图(b)表示扩容后key1和key2两种key确定索引位置的示例,其中hash1是key1对应的哈希值(也就是根据key1算出来的hashcode值)与高位与运算的结果。


image.png

元素在重新计算hash之后,因为n变为2倍,那么n-1的mask范围在高位多1bit(红色),因此新的index就会发生这样的变化:


image.png
这个设计确实非常的巧妙,既省去了重新计算hash值的时间,而且同时,由于新增的1bit是0还是1可以认为是随机的,因此resize的过程,均匀的把之前的冲突的节点分散到新的bucket了。这一块就是JDK1.8新增的优化点。有一点注意区别,JDK1.7中rehash的时候,旧链表迁移新链表的时候,如果在新表的数组索引位置相同,则链表元素会倒置,但是从上图可以看出,JDK1.8不会倒置。有兴趣的同学可以研究下JDK1.8的resize源码.

小结

(1) 扩容是一个特别耗性能的操作,所以当程序员在使用HashMap的时候,估算map的大小,初始化的时候给一个大致的数值,避免map进行频繁的扩容。
(2) 负载因子是可以修改的,也可以大于1,但是建议不要轻易修改,除非情况非常特殊。
(3) HashMap是线程不安全的,不要在并发的环境中同时操作HashMap,建议使用ConcurrentHashMap。
(4) JDK1.8引入红黑树大程度优化了HashMap的性能。
(5) 还没升级JDK1.8的,现在开始升级吧。HashMap的性能提升仅仅是JDK1.8的冰山一角。

上一篇下一篇

猜你喜欢

热点阅读