菜单

HashMap源码剖析

2018年11月15日 - jQuery

前言

宣称,本文用得是jdk1.8

眼前都谈了Collection的总览和剖析List集合以及散列表、Map集合、红黑树的基础了:

本篇第一讲解HashMap,以及涉嫌到有及hashtable的比~

关押即首稿子之前最好是发出接触数据结构的根基:

本了,如果说得有错的地方还请大家多原谅并无吝在评价去指正~

HashMap的落实原理

关注点 结论
是否允许空 key和value都运行空
是否允许重复元素 key重复会覆盖,value允许重复
是否有序 无序
是否线程安全 非线程安全

一、HashMap剖析

首先看望HashMap的顶部注释说了些什么:

图片 1

双重来看看HashMap的类继承图:

图片 2

下我们来拘禁一下HashMap的习性:

图片 3

分子属性有如此几独:

图片 4

更来拘禁一下hashMap的一个内部类Node:

图片 5

我们清楚Hash的脚是散列表,而以Java中散列表底落实是经数组+链表的~

重复来简单看看put方法就可以证明我们的传教了:数组+链表–>散列表

图片 6

咱得以简简单单总结出HashMap:

一. HashMap的数据结构


在Java语言中,最中心的星星种植结构就是数组和模拟指针(引用),所有的数据结构都可采取即时点儿单中心结构来布局。HashMap实际就是是一个”链表散列”的数据结构,即数组与链表的结合体。

图片 7

从今上图可以见见,HashMap底层就是一个数组结构,数组中的各个一样码又是一个链表。当新建一个HashMap的时刻,就会初始化一个数组。

率先看一下HashMap的一个存储单元Node:

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

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

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

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

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

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

来上面代码可以看来,Node就是数组中的元素,每个Map.Entry其实就是一个Key-value对,它有一个针对性下一个因素的援,这便成了链表。

1.1HashMap构造方法

HashMap的构造方法有4独:

图片 8

图片 9

以上头的构造方法最后一实施,我们见面意识调用了tableSizeFor(),我们进去看看:

图片 10

即时是位运算算法,具体流程可参看:

看罢上面可能会见倍感奇怪的是:呢甚是将2的整数幂的数赋给threshold

实际上这里仅是一个初始化,当创建哈希表的上,它见面再也赋值的:

图片 11

至于别的构造方法都多,这里自己不怕不细致讲了:

图片 12

二. 功能实现-方法


1.2put方法

put方法可以说凡是HashMap的着力,我们来探:

图片 13

我们来看看它是怎计算哈希值的:

图片 14

为什么要如此提到也??我们一般的话一直拿key作为哈希值不纵吓了吗,做异或运算是干嘛用的??

咱们看下来:

图片 15

我们是根据key的哈希值来保存在散列表中的,我们表默认的始发容量是16,要置散列表中,就是0-15的职务及。也就是是tab[i = (n - 1) & hash]。可以发现的凡:在召开&运算的时节,仅仅是后4位有效~那要我们key的哈希值高位变化很大,低位变化非常有点。直接用过去召开&运算,这即见面招计算出来的Hash值相同之很多。

若是设计者拿key的哈希值的上位也做了运算(与大16各做异或运算,使得以做&运算时,此时之没有实际上是高位与小的三结合),这就算多了随机性,减少了碰冲突之可能性!

脚我们重新来瞧流程是何等的:

图片 16

新值覆盖旧值,返回旧值测试:

图片 17

联网下去我们省resize()方法,在初始化的时光要调用这个点子,当散列表元素大于capacity * load factor的上吧是调用resize()

图片 18

1.规定哈希桶数组索引位置

任多、删除、查找键值对,定位及哈希桶数组的职还是非同小可的一致步,而一定数组索引的基本点方法如下。

// jdk1.8 & jdk1.7
static final int hash(Object key) {
    int h;
    // 第一步:h = key.hashCode() 取hashCode值
    // 第二步:h ^ (h >>> 16)     高位参与运算
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// jdk1.7的源码,jdk1.8没有这个方法,但是实现原理一样的
static int indexFor(int h, int length) {
     // 第三步: 取模运算
     return h & (length-1);  
}

这边Hash算法本质上即是三步:取key的hashCode值、高位运算、取模运算

对自由给定的靶子,只要其的hashCode()值相同,那么调用hash()方法吃所计算得到的hash码总是一样之。我们率先想到就是管hash值对数组长度求模,这样就是管了元素的遍布相对较全匀。但是,求模运算时消耗较生,所以下了indexFor()方法来测算该目标应保留于table数组中的谁索引处。

其一措施好抢眼,它通过h & (table.length –
1)来取该目标的保存位,而HashMap底层数组的尺寸总是2之n次方,这是HashMap在速度上的优化。当length总是2的n次方时,h
& (length – 1)运算等价于对length取模,也就是是h %
length,但是&比%具有双重强的频率。

以JDK1.8之实现着,优化了高位运算的算法,通过hashCode()的胜16员不同或低16位实现的:(h
= k.hashCode()) ^ (h >>>
16),主要是于进度、功效、质量来设想的,这么做足以三番五次组table的length比较粗的时,也能确保考虑到高低Bit都与到Hash的算计中,同时不见面发生最可怜之开发。

如下图,其中n为table的长度。

图片 19

1.3get方法

图片 20

搭下去我们省getNode()凡怎么落实之:

图片 21

2.添加和修改数据

是因为Java8针对hashMap底层进行了优化,当链表长度逾8时,转换为吉祥黑树进行拍卖,因此以下采用了美团点评技术团队的教。

HashMap的put方法执行进程可通过下图来解。

手续一样:判断键值对数组table[i]是不是也空或也null,否则执行resize()进行扩容;

手续二:根据键值key计算hash值得到插入的数组索引i,如果table[i]==null,直接新建节点添加,转向⑥,如果table[i]不为空,转向③;

步骤三:判断�table[i]的首单因素是否与key一样,如果同直接盖value,否则转向④,这里的等同指的是hashCode以及equals;

步骤四:判断table[i] 是否为treeNode,即table[i]
是否是吉祥黑树,如果是吉黑树,则一直当培育被插入键值对,否则转向⑤;

步骤五:遍历table[i],判断链表长度是否超过8,大于8之话语将链表转换为红黑树,在红黑树中执行插入操作,否则进行链表的插操作;�遍历过程中设发现key已经在直接覆盖value即可;

手续六:插入成功后,判断实际在的键值对数据size是否超过多了无限深容量threshold,如果超过,进行扩容。

public V put(K key, V value) {
    // 对key的hashCode()做hash
    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;
    // 步骤一:tab为空则创建
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 步骤二: 计算index,并对null进行处理 
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 步骤三:节点key存在,直接覆盖value
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 步骤四:判断该链为红黑树
        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);
                    // 链表长度大于8转换为红黑树进行处理
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // key已经存在直接覆盖value
                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.4remove方法

图片 22

再来探望removeNode()的实现:

图片 23

3.剔除数据

下面是Java8吃去除数据源代码的解析:

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;
}

final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    // 步骤一:找到要删除数组元素为p
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        // 步骤二:数组元素p存在,表示要删除的节点node赋为p
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        // 数组元素p是链表,则将链表的下一个节点赋给节点e
        else if ((e = p.next) != null) {
            // 步骤三:如果p为红黑树,则调用方法找到要删除的节点赋给node
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            // 步骤四:如果为链表,则找到对应要删除的节点赋给node
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                            (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        // 如果找到要删除的节点node
        if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) {
            // 步骤五:判断此时数组元素的类型,并删除对应的节点node
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

二、HashMap与Hashtable对比

从存储结构及实现来讲基本上都是同等的。它和HashMap的极度充分之不比是她是线程安全的,另外她不允key和value为null。Hashtable是个过时的集合类,不建议在初代码中以,不需线程安全的场子可以为此HashMap替换,需要线程安全之场合可以用ConcurrentHashMap替换

图片 24

Hashtable具体看源码可参考:

三. HashMap的其余相关讲解


四、总结

以JDK8中HashMap的底部是:数组+链表(散列表)+红黑树

每当散列表中有装载因子这样一个特性,当装载因子*启容量小于散列表元素时,该散列表会再散列,扩容2加倍!

装因子的默认值是0.75,无论是开始大了或者开小了对咱HashMap的性都不好

千帆竞发容量的默认值是16,它也同等,无论初始大了还是略了,对咱的HashMap都是有震慑之:

自打源码上我们得发现:HashMap并无是直将key的哈希值来所以的,它见面以key的哈希值的赛16各类展开异或操作,使得我们将元素放入哈希表的上多了定的随机性

还要值得注意的是:并无是桶子上发8各类元素的时刻它就是能变成红黑树,它得而满足我们的散列表容量大于64才行的~

图片 25

图片 26


明天要是无意外的言语,可能会见刻画TreeMap,敬请期待哦~~~~

图片 27

苟文章产生摩擦的地方迎指正,大家相互交流。习惯在微信圈技术文章,想只要博更多之Java资源的校友,可以关爱微信公众号:Java3y。为了大家好,刚新建了转qq群:742919422,大家呢可以去交流交流。
谢谢支持了!希望会多介绍为任何产生亟待之冤家

参考资料:

1.扩容机制

扩容就是再计算容量,当HashMap中无法包容更多之要素时,就要扩大数组的长短,以便容纳更多之素。由于Java中的数组是无法活动扩容的,所以要是利用一个新的数组来替代已部分容量小之数组。

脚我们解析resize()方法的源码,由于Java8引入了吉黑树,因此还下Java7的源码进行分析。

// 传入新的容量
void resize(int newCapacity) {
    // 引用扩容前的Entry数组
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    // 扩容前的数组大小如果已经达到最大(2^30)了     
    if (oldCapacity == MAXIMUM_CAPACITY) {
        // 修改阈值为int的最大值(2^31-1),这样以后就不会扩容了
        threshold = Integer.MAX_VALUE;
        return;
    }
    // 初始化一个新的Entry数组
    Entry[] newTable = new Entry[newCapacity];
    // 将数据转移到新的Entry数组里
    transfer(newTable);
    // HashMap的table属性引用新的Entry数组
    table = newTable;
    // 修改阈值
    threshold = (int)(newCapacity * loadFactor);
}
// 将原有Entry数组的元素拷贝到新的Entry数组里
void transfer(Entry[] newTable) {
    // src引用了旧的Entry数组
    Entry[] src = table;                
    int newCapacity = newTable.length;
    // 遍历旧的Entry数组
    for (int j = 0; j < src.length; j++) {
        // 取得旧Entry数组的每个元素
        Entry<K,V> e = src[j];           
        if (e != null) {
            // 释放旧Entry数组的对象引用(for循环后,旧的Entry数组不再引用任何对象)
            src[j] = null;
            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冲突),这一点Java8跟那殊。由于还计算了hash值,所以最后或在新数组的差位置。

下举个例简单说明一下扩容的法则。我们采取的hash算法就是key对屡次组的长短取模。其中哈希桶数组table数组的长度size=2,put的逐一是3、7、5。在mod
2后还当table[1]有了冲突。这里要负载因子loadFactor=1,即当键值对实际大小size大于table的骨子里尺寸时开展扩容。下面是resize的进程示意图。

图片 28

Java8面临对新数组的目计算以了更加简明的算法,不需每次去算hash值;而且当初链表迁移到新链表的早晚,如果新表的数组索引位置相同,则链表元素会倒置,而Java8虽说非见面,详细剖析可以展现tech.meituan.com/java-hashmap.html

2.HashMap的table是transient的

transient Node<K,V>[] table;

出于table采用了transient修饰,也便是意味其不得以被序列化,它的缘由如下:

public native int hashCode();

立即意味着hashCode与底层相关,对于不同平台的虚拟机,会时有发生永不的hashCode实现方式,也便是与一个对象在不同的阳台下会发出例外之hashcode值。

由Java的跨平台特性,如果table不用transient修饰,在编造机A下的主次在虚拟机B下就算会导致无法正常运转,这样就算去了彼越平台的意义,所以为了避免这样的情形,Java自己再次写了那个序列化table的计,源码如下:

private void writeObject(java.io.ObjectOutputStream s)
    throws IOException {
    int buckets = capacity();
    // Write out the threshold, loadfactor, and any hidden stuff
    s.defaultWriteObject();
    s.writeInt(buckets);
    s.writeInt(size);
    internalWriteEntries(s);
}

private void readObject(java.io.ObjectInputStream s)
    throws IOException, ClassNotFoundException {
    // Read in the threshold (ignored), loadfactor, and any hidden stuff
    s.defaultReadObject();
    reinitialize();
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new InvalidObjectException("Illegal load factor: " +
                                            loadFactor);
    s.readInt();                // Read and ignore number of buckets
    int mappings = s.readInt(); // Read number of mappings (size)
    if (mappings < 0)
        throw new InvalidObjectException("Illegal mappings count: " +
                                            mappings);
    else if (mappings > 0) { // (if zero, use defaults)
        // Size the table using given load factor only if within
        // range of 0.25...4.0
        float lf = Math.min(Math.max(0.25f, loadFactor), 4.0f);
        float fc = (float)mappings / lf + 1.0f;
        int cap = ((fc < DEFAULT_INITIAL_CAPACITY) ?
                    DEFAULT_INITIAL_CAPACITY :
                    (fc >= MAXIMUM_CAPACITY) ?
                    MAXIMUM_CAPACITY :
                    tableSizeFor((int)fc));
        float ft = (float)cap * lf;
        threshold = ((cap < MAXIMUM_CAPACITY && ft < MAXIMUM_CAPACITY) ?
                        (int)ft : Integer.MAX_VALUE);
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] tab = (Node<K,V>[])new Node[cap];
        table = tab;

        // Read the keys and values, and put the mappings in the HashMap
        for (int i = 0; i < mappings; i++) {
            @SuppressWarnings("unchecked")
                K key = (K) s.readObject();
            @SuppressWarnings("unchecked")
                V value = (V) s.readObject();
            putVal(hash(key), key, value, false, false);
        }
    }
}

参考资料


相关文章

标签:

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图