HashMap

2021-01-03   51 次阅读


HashMap

1. 简介

  • HashMap基于哈希表的Map接口实现。
  • 是以key-value存储形式存在,即主要用来存放键值对。
  • HashMap的实现不是同步的,即其不是线程安全的。
  • 它的key值、value值都可以为null,但是键位置只能是一个null。
  • 它的key值是唯一的,不可以重复 。
  • HashMap中的映射 不是有序 的。
  • JDK1.8之前HashMap由 数组+链表 组成的,数组是HashMap的主体,链表则是主要为了解决哈希冲突(两个对象调用的hashcode方法计算的哈希码值一致导致计算的数组索引值相同)而存在的(“拉链法解决冲突)。
  • JDK1.8以后在解决哈希冲突时有了较大的变化,当链表长度大于阈值(或者红黑树的边界值,默认为8)并且当前数组的长度大于64时,此时此索引位置上的所有数据改为使用红黑树存储。
    • 补充:将链表转换成红黑树前会判断,即使阈值大于8,但是数组长度小于64,此时并不会将链表变为红黑树,而是选择进行数组扩容。这样做的目的是因为数组比较小,尽量避开红黑树结构,这种情况下变为红黑树结构反而会降低效率,因为红黑树需要进行左旋,右旋,变色这些操作来保持平衡。同时数组长度小于64时,搜索时间相对要快一些所以综上所述为了提高性能和减少搜索时间,底层在阈值大于8并且数组长度大于64时,链表才转换为红黑树。

2. HashMap集合底层数据结构

2.1 HashMap的结构组成以及变革

  • JDK1.8之前HashMap由数组+链表数据结构组成的。
  • JDK1.8之后HashMap由数组+链表+红黑树数据结构组成的。

2.2 HashMap底层的数据结构存储数据的过程

HashMap<String, Integer> hashMap = new HashMap<>();
/*
该语句的执行过程:
-- 1.8之前,构造方法中创建一个长度是16的Entry[] table用来存储键值对数据。
-- 1.8之后,在构造方法中不创建数组了,而是在第一次调用put()方法时创建数组Node[] table来存储键值对数据。
*/
  1. 假设向哈希表中存储键值对 <"a", 1> ,根据键值 “a” 调用String类中重写之后的hashCode()方法计算出值,然后结合数组长度采用某种算法(这里的算法有很多,比如无符号右移(>>>)、按位异或(^)、按位与(&)等,也有平方取中法、取余数、伪随机数法,不过更多的是按位运算的方法,效率较高。通过这些算法来获取索引值)计算出向Node数组中存储数据的空间的索引值,如果计算出的索引空间没有数据,则直接将 <"a", 1> 存储到数组中。
  2. 向哈希表中存储键值对 <"b", 2> ,根据键值“b” 计算出的Hash值并经过算法处理后得到的索引值如果与 "a" 的索引相同,由于该索引值的数组空间已经被占用,则比较 “a”“b” 的hash值,如果hash值相等,此时发生哈希碰撞,此时底层调用equals方法比较两个键的内容的值是否相等,如果相等,则更新数组内容为2,否则,则继续向下比较,如果都不想等,则在此空间上划出一个节点来存储键值对 <"b", 2>
    • 我用的示例键值对只做介绍之用,实际其hash值并不相等。
  3. 如果节点长度即链表长度大于阈值8并且数组长度大于64则将链表变为红黑树
    • 当链表长度大于阈值8,但是数组长度小于64时进行数组扩容,具体是获取一个容量为原来二倍的空间,然后将原来的数据复制过来。

image-20201216180214823

tips:

  • size表示HashMap中K-V的实时数量,并不是数组的长度。
  • threshold(临界值)= capacity(容量)* loadFactor(加载因子),这个值是当前已占用数组长度的最大值。size超过这个临界值就重新resize(扩容),扩容后的HashMap是之前容量的两倍。

3. HashMap的继承关系

  • HashMap继承自AbstractMap(正如名字一样,其是一个抽象类,并且实现了Map接口)

    image-20201216191536096

    tips:

    • Cloneable空接口。表示可以克隆,创建并返回HashMap对象的一个副本。
    • Serializable序列化接口。属于标记型接口,HashMap对象可以被序列化和反序列化。
    • AbstractMap父类提供了Map实现接口。以最大限度地减少实现此接口所需的工作。
    • AbstractMap实现了Map接口而HashMap也实现了Map接口的原因是因为没有原因,java集合框架的创始人Josh Bloch手抖了,写了这么个bug,后续维护的程序员表示这根本不叫事,我分分钟几十万上下的人怎么可能去修改这种bug。

4. HashMap集合类的成员

4.1 成员变量

  1. 序列化版本号

    private static final long serialversionUID = 362498820763181265L;
    
  2. 集合的初始化容量( 必须是二的n次幂

    //默认的初始容量是16 -- 1<<4相当于1*2的四次方
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    //HashMap构造方法还可以执行集合的初始化容量大小
    HashMap(int initialCapacity);
    //构造一个带指定初始容量和默认加载因子(0.75)的空HashMap。
    

    tips:

    为什么默认值是2的n次幂?这样有什么好处?

    根据上面的内容我们已经知道,当向HashMap中添加一个元素的时候,需要根据key的hash值,去确定其在数组中的具体位置,HashMap为了存取高效,要尽量减少碰撞,就是要尽量把数据分配均匀,每个链表长度大致相同,这个实现就在于把数据存到哪个链表中的算法。

    这个算法实际上就是取模运算,而计算机中通过求余数的方式取模效率较低,而位运算的效率相对较高。所以源码中的取模运算 hash%length 优化为了hash&(length - 1) ,但是实际上这样优化的前提是length为2的n次幂。

    为什么使用2的n次幂就能均匀分布,减少碰撞呢?

    2的n次幂转化为二进制为:1 0 0… (n个0)

    2的n次幂-1转化为二进制:1 … (n个1)

    当key与一个值进行按位与的时候,其分散程度取决于这个数的二进制中1的个数(因为按位与的原则是同一为一,否则为零,因此当一个值为1时,结果和另一个值相同),而2的n次幂-1全是1,在位数相同的情况下不存在分散程度更好的情况。

    既然HashMap进行了这样的优化,如果自定义容量的参数不是2的n次幂会怎么样?

    自定义容量并不是你指定多少容量就i是多少的,当传入的参数不是2的n次幂时,会通过或运算以及位移运算对参数进行二进制的向上取整(比如你传入的是7,向上取整就是8,9就是16,保证是2的n次幂)。(具体算法挺精妙的,n通过和n右移1/2/4/8/16位进行或运算保证最后得到的数为n的二进制向上取整-1,然后返回其+1就是n向上取整的值)

    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
    
  3. 默认的负载因子,默认值为0.75

    //负载因子的作用是进行容量预警,在实际进行加载的时候并不会整个数组填满才进行扩容或者变形,而是达到容量*负载因子就开始进行扩容或变形。因为数组填满是很难的,往往在接近填满的时候数组中部分链表已经巨长了,效率会很低下,而负载因子就是在数组容量增加率还是降低,链表长度增长率开始增价的时候进行预警,并且进行扩容或者变形
    static final float DEFALULT_LOAD_FACTOR = 0.75f;
    
  4. 集合最大容量

    //集合最大容量的上限是:2的30次幂
    static final int MAXIMUM_CAPACITY = 1 << 30;
    
  5. 当链表的值超过8则会转红黑树(jdk1.8以后加入)

    //当桶(bucket)上的结点大于这个值时会转成红黑树
    static final int TREEIFY_THRESHOLD = 8;
    

    这个8是怎么得到的?

    官方的解释是因为树节点的大小大约是普通链表结点的两倍,所以只在数组中包含足够多的结点时才使用树节点;当结点因为一系列删除或者调整大小等操作变的足够少时,其又会转换为链表结点。通过大量的实验获取到转换的数据,发现其频率服从泊松分布。通过对空间和时间的权衡,发现在链表长度达到8时转为红黑树,当长度降到6时,转化为链表是最优的结果。

  6. 当链表的值小于6则会从红黑树转会链表

    //当桶(bucket)上的结点小于这个值时会转换为链表
    static final int UNTREEIFY_THRESHOLD = 6;
    
  7. 当Map里面的数量超过这个值时,表中的桶才能进行树形化,否则桶内元素太多时会扩容,而不是树形化为了避免进行扩容、树形化选择的冲突,这个值不能小于4 * UNTREEIFY_THRESHOLD(8)

    //桶中结构转换为红黑树对应的数组长度最小的值
    static final int MIN_TREEIFY_CAPACITY = 64;
    
  8. table用来初始化(必须是2的n次幂)

    //存储元素的数组
    transient Node<K, V>[] table;   //jdk1.8之前叫做Entry
    
  9. 用来存放缓存

    //存放具体元素的集合
    transient Set<Map.Entry<K, V>> entrySet;
    
  10. HashMap中存放元素的个数

    //存放元素的实时个数,注意这个不等于数组的长度
    transient int size;
    
  11. 用来记录HashMap的修改次数

    //每次扩容和更改map结构的计数器
    transient int modCount;
    
  12. 用来调整大小,下一个容量的值计算方式为(容量*负载因子)

    //临界值 当实际大小(容量*负载因子)超过临界值,会进行扩容
    int threshold;
    
  13. 哈希表的加载因子

    //加载因子,用来衡量HashMap满的程度,表示HashMap的疏密程度,影响hash操作到同一个数组位置的概率,计算试试加载因子的方法为:size/capacity。加载因子影响数组的利用率,官方默认的0.75是一个比较好的临界值。
    final float loadFactor;
    //由于扩容比较耗时,因此尽量减少扩容次数,另外HashMap通过了在构造器中定制loadFactor的方法,但是不建议修改,上面已经说了0.75是最优的值
    HashMap(int initialCapacity, float loadFactor);
    

4.2 构造方法

  1. 无参构造,构造一个空的HashMap,默认初始容量16和默认负载因子0.75

    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
    }
    
  2. 构造一个具有指定的初始容量和默认负载因子0.75的HashMap

    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    
  3. 构造一个具有指定的初始容量和负载因子的HashMap

    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
        this.loadFactor = loadFactor;
        //tableSizeFor()方法上面有
        this.threshold = tableSizeFor(initialCapacity);
    }
    /*
    关于this.threshold = tableSizeFor(initialCapacity);这行代码
    threhold是临界值,具体计算应该为size*loadFactor,但是这里却传入了本应该为size的值。这是因为在jdk1.8以后的构造方法中,并没有对table这个成员变量进行初始化,table的初始化推迟到了put方法中,在put方法中会对threshold重新计算。
    */
    
  4. 构造一个映射关系与指定Map相同的新HashMap

    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }
    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        int s = m.size();
        if (s > 0) {
            if (table == null) { // pre-size
                //+1的原因和进行转换的时候-1相同,就是为了防止数组填满甚至越界
                float ft = ((float)s / loadFactor) + 1.0F;
                int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);
                if (t > threshold)
                    //这里跟上一段讲的一样
                    threshold = tableSizeFor(t);
            }
            else if (s > threshold)	//大于临界值就扩容
                resize();
            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
                K key = e.getKey();
                V value = e.getValue();
                putVal(hash(key), key, value, false, evict);
            }
        }
    }
    

4.3 成员方法

4.3.1 增加方法

put方法实现步骤:

  1. 先通过hash值计算出key映射到哪个桶
  2. 如果桶上没有碰撞冲突,则直接插入
  3. 如果出现了冲突,则需要处理冲突
    • 如果该桶使用红黑树处理冲突,则调用红黑树的方法插入数据
    • 否则采用传统的链式方法插入;如果链的长度达到临节值,则把链表转换为红黑树
  4. 如果桶中存在重复的键,则为该键替换新值value
  5. 如果size大于阈值threshold,则进行扩容

具体代码如下:

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
    int h;
    /*
    	1. 如果key等于null,则返回0
    	2. 如果key不等于null,则计算出key的hashCode值赋予h,然后与h无符号右移16位后的二进制进行按位异或得到最后的hash值。
    	这样操作的原因是由于hashCode直接获得的值较大,后面要进行位压缩,这里进行低16位和高16位的异或操作,其实就是进行了初步压缩,并且因为hashCode的计算方式,可以减少哈希冲突
    */
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
/*
putVal方法中多了两个参数,
onlyIfAbsent:如果为true代表不更改现有的值
evict:如果位false代表table为创建状态
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //因为在上述hash()中获得到的值较大,这一步主要是进行位压缩,其实就是对数组长度取余(这里采用的是上述的位运算,效率更高)(n默认为16)
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);	//newNode就是new新的结点
    else {	//如果当前数组不是null,也就是冲突了
        Node<K,V> e; K k;
        //比较hash值和key值的内容,如果完全相同就覆盖修改
        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;
                }
                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;
            //当插入的key在Map中已经存在时,进行标识符的修改,并且覆盖原有值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    //插入结点完成,进行全局参数的修改
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

4.3.2 treeifyBin方法

结点添加完成之后判断此时结点个数是否大于TREEIFY_THRESHOLD,如果大于则将链表转换为红黑树

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    //如果数组长度小于MIN_TREEIFY_CAPACITY(默认64),则进行扩容
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        //遍历转换为树节点
        do {
            //replacementTreeNode()就是创建一个树结点
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            //红黑树的旋转
            hd.treeify(tab);
    }
}

final void treeify(Node<K,V>[] tab) {
    TreeNode<K,V> root = null;
    for (TreeNode<K,V> x = this, next; x != null; x = next) {
        next = (TreeNode<K,V>)x.next;
        x.left = x.right = null;
        if (root == null) {
            x.parent = null;
            x.red = false;
            root = x;
        }
        else {
            K k = x.key;
            int h = x.hash;
            Class<?> kc = null;
            for (TreeNode<K,V> p = root;;) {
                int dir, ph;
                K pk = p.key;
                if ((ph = p.hash) > h)
                    dir = -1;
                else if (ph < h)
                    dir = 1;
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0)
                    dir = tieBreakOrder(k, pk);

                TreeNode<K,V> xp = p;
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    x.parent = xp;
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    root = balanceInsertion(root, x);
                    break;
                }
           }
        }
    }
    moveRootToFront(tab, root);
}

4.3.3 resize方法

  • 什么时候需要扩容
    • 当HashMap中的元素个数超过数组大小(数组长度) * loadFactor(负载因子)时,就会进行数组扩容。每次扩容,源码中的操作是原大小左移一位,即扩大了两倍,然后重新计算每个元素在数组中的位置,而这是一个非常消耗性能的操作;因此如果我们已经预知HashMap中元素的个数,可以通过预设数组大小来有效的提高HashMap的性能。
  • HashMap的扩容是什么
    • 进行扩容,往往会伴随着一次重新hash分配,并且会遍历hash表中的所有元素。因为每次扩容都是左移一位,与原来计算的(n-1)&hash的结果相比,只是多了一个bit位(多这一位是hash值的扩容位,如果为0,则会在原来的位置,如果为1,则加上扩容量),所以结点的位置会在原来的位置或者被分配到了“原位置+扩容量”这个位置;因此就不需要重新计算hash值。
//扩容方法
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    //如果旧的容量大于零
    if (oldCap > 0) {
        //如果旧的容量已经达到最大,不能扩容了就把旧的返回回去
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }	//如果旧的容量扩容后(这里左移1位就是容量变为2倍)依旧小于容量最大值,并且旧的容量达到了扩容条件(DEFAULT_INITIAL_CAPACITY这个参数就是用来判断扩容条件的)则进行扩容
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }	//如果旧的容量不大于零并且旧的临界值大于零,就把旧的临界值赋值给新的
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
	//如果旧的容量和临界值都不大于0
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];	//创建了新的数组
    table = newTab;
    if (oldTab != null) {
        //遍历转存
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                //如果e.next为空也就是这个数组还是空的,没有发生冲突
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                //如果发生了冲突,就要判断是否使用红黑树解决冲突了
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                //进行链表处理
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        //检查高位是否是0,如果是0就存在原来的位置
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        //如果是1,就存在j + oldCap的位置
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    //检查高位是否是0,如果是0就存在原来的位置
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    //如果是1,就存在j + oldCap的位置
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

4.3.4 remove方法

删除比较简单,首先要找到元素的位置,如果是链表就遍历删除;如果是红黑树,就也是遍历删除,然后判断树是否小于6,如果小于6就转换成链表。

//remove方法
public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;
}
//removeNode方法
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;
    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;
        //判断数组中的结点是否是要删除的结点
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        //如果不是,判断是否有链表
        else if ((e = p.next) != null) {
            //判断是不是树节点
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            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);
            }
        }
        if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) {
            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;
}
//removeTreeNode方法
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab, boolean movable) {
    int n;
    if (tab == null || (n = tab.length) == 0)
        return;
    int index = (n - 1) & hash;
    TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
    TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
    if (pred == null)
        tab[index] = first = succ;
    else
        pred.next = succ;
    if (succ != null)
        succ.prev = pred;
    if (first == null)
        return;
    if (root.parent != null)
        root = root.root();
    if (root == null
        || (movable
            && (root.right == null
                || (rl = root.left) == null
                || rl.left == null))) {
        tab[index] = first.untreeify(map);  // too small
        return;
    }
    TreeNode<K,V> p = this, pl = left, pr = right, replacement;
    if (pl != null && pr != null) {
        TreeNode<K,V> s = pr, sl;
        while ((sl = s.left) != null) // find successor
            s = sl;
        boolean c = s.red; s.red = p.red; p.red = c; // swap colors
        TreeNode<K,V> sr = s.right;
        TreeNode<K,V> pp = p.parent;
        if (s == pr) { // p was s's direct parent
            p.parent = s;
            s.right = p;
        }
        else {
            TreeNode<K,V> sp = s.parent;
            if ((p.parent = sp) != null) {
                if (s == sp.left)
                    sp.left = p;
                else
                    sp.right = p;
            }
            if ((s.right = pr) != null)
                pr.parent = s;
        }
        p.left = null;
        if ((p.right = sr) != null)
            sr.parent = p;
        if ((s.left = pl) != null)
            pl.parent = s;
        if ((s.parent = pp) == null)
            root = s;
        else if (p == pp.left)
            pp.left = s;
        else
            pp.right = s;
        if (sr != null)
            replacement = sr;
        else
            replacement = p;
    }
    else if (pl != null)
        replacement = pl;
    else if (pr != null)
        replacement = pr;
    else
        replacement = p;
    if (replacement != p) {
        TreeNode<K,V> pp = replacement.parent = p.parent;
        if (pp == null)
            root = replacement;
        else if (p == pp.left)
            pp.left = replacement;
        else
            pp.right = replacement;
        p.left = p.right = p.parent = null;
    }

    TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);

    if (replacement == p) {  // detach
        TreeNode<K,V> pp = p.parent;
        p.parent = null;
        if (pp != null) {
            if (p == pp.left)
                pp.left = null;
            else if (p == pp.right)
                pp.right = null;
        }
    }
    if (movable)
        moveRootToFront(tab, r);
}

get方法

查找方法,通过元素的key找到value。具体步骤如下:

  • 通过hash值获取该key映射到的桶
  • 桶上的key就i是要查找的key,则直接返回
  • 桶上的key不是要找的key,则查看后续结点:
    • 如果后续节点是红黑树结点,通过调用红黑树的方法根据key获取value
    • 如果后续结点是链表节点,则通过循环遍历链表根据key获取value
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
//getNode方法
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    //如果哈希表不为空并且key对应的桶上不为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        //判断数组元素是否相等,如果相等就返回
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        //如果存在链表,先判断是不是树结点
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {	//不是树就进行遍历
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}
//查找红黑树结点,红黑树本身就是有序的,因此通过折半查找就行,效率很高,具体操作和插入相同
final TreeNode<K,V> getTreeNode(int h, Object k) {
    return ((parent != null) ? root() : this).find(h, k, null);
}
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
    TreeNode<K,V> p = this;
    do {
        int ph, dir; K pk;
        TreeNode<K,V> pl = p.left, pr = p.right, q;
        if ((ph = p.hash) > h)
            p = pl;
        else if (ph < h)
            p = pr;
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        else if (pl == null)
            p = pr;
        else if (pr == null)
            p = pl;
        else if ((kc != null ||
                  (kc = comparableClassFor(k)) != null) &&
                 (dir = compareComparables(kc, k, pk)) != 0)
            p = (dir < 0) ? pl : pr;
        else if ((q = pr.find(h, k, kc)) != null)
            return q;
        else
            p = pl;
    } while (p != null);
    return null;
}

4.3.6 遍历HashMap的几种方式

  1. 分别便利key和values

    for (String key : map.keySet()) {
        System.out.println(key);
    }
    for (Object value : map.values()) {
        System.out.println(value);
    }
    
  2. 使用迭代器Iterator迭代

    Iterator<Map.Entry<String, Object>> iterator = map.entrySet().iterator();
    while (iterator.hasNext()) {
        Map.Entry<String, Object> mapEntry = iterator.next;
        System.out.println(mapEntry.getKey() + ": " + mapEntry.getValue());
    }
    
  3. 通过get方式(不建议使用,效率太低了)

    Set<String> keySet = map.keySet(); //这里进行了一次迭代,下面的get又进行了一次迭代
    for (String str : keySet) {
        System.out.println(str + ": " + map.get(str));
    }
    
  4. jdk1.8以后使用Map接口中的默认方法:

    default void forEach(BiConsumer<? super K, ? super V> action)
    /*
    BiConsumer是消费接口,它的两个参数:
        t	key
        u   value
    */
    map.forEach((key, value)->{
        System.out.println(key + ": " + value);
    });
    

5. 其他

5.1 JDK1.8为什么加入红黑树?单纯为了效率嘛?

  • HashMap导致的DOS

    由于当前使用的容器多为Tomcat,其在处理HTTP请求时,会通过HashMap存储请求参数;加入攻击者通过制造大量的hash冲突的key,就会产生链表巨长的HashMap,这也就导致服务器在查询时占用大量的CPU资源用来轮询,从而使服务器拒绝其他的服务,即DOS攻击。

5.2 如何设计多个非重复的键值对要存储HashMap的初始化?

5.2.1 HashMap的初始化问题描述

  • 如果我们能确切的知道我们有多少键值对需要存储,那么我们在初始化HashMap的时候就应该指定它的容量,以防止ashhMap自动扩容,影响使用效率。

5.2.2 HashMap中容量的初始化

当我们使用HashMap(int initialCapacity)来初始化容量的时候,jdk会默认帮我们计算一个相对合理的容量(也就是默认为向上取整为2的n次幂),但是HashMap在元素个数达到size*0.75时就会进行扩容,这明显不行,因此我们建议使用这样一个算法来计算合理的初始化参数:

initialCapacity = (需要存储的元素个数 / 负载因子) + 1.

这样虽然会牺牲一些内存,但是提升了性能,仍然是合算的。

Q.E.D.

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

If you don't come, I will snow.