HashMap简介

HashMap是Java语言中的一种调集类，它完成了Map接口，用于存储Key-Value对。它依据哈希表数据结构，经过核算Key的哈希值来快速定位Value的方位，然后完成高效的刺进、删去和查找操作。下面咱们对照着JAVA1.8中的HashMap源码来剖析一下它的内部完成逻辑

根本的结构

在开端剖析HashMap的完成逻辑之前，咱们需求先了解一下根底的组成和内部的成员变量都有哪些，别离代表什么意思。

1、Node<K,V>

首先咱们看一下HashMap其间一个子类:Node<K,V>，这个子类用于存储根本的元素，即Key-Value对、Key的Hash值以及指向下一个节点的Node<K,V>变量。在HashMap内部，由Node<K,V>类型组成的数组用来存储一切的元素。 Node<K,V>完成自Map.Entry<K,V>接口，而且完成了接口中规则的多个根本办法:

    interface Entry<K,V> {
        K getKey();
        V getValue();
        V setValue(V value);
        boolean equals(Object o);
        int hashCode();
        ...
    }

一起，在Node<K,V>类中，界说了4个成员变量：

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>,Cloneable,Serializable {
    ....
    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;
            }
            ...
    }
    ...
}

其间hash是key的hash值，key和value存储键和值，next变量指向链表中的下一个元素。

2、HashMap的成员变量

    transient Node<K,V>[] table;
    transient Set<Map.Entry<K,V>> entrySet;
    transient int size;
    transient int modCount;
    int threshold;
    final float loadFactor;

table：保存一切元素的数组。
entrySet：一个用于遍历一切数据节点的调集。
size：记录HashMap中元素的总数量。
modCount：用来判别在对HashMap数据项进行遍历时，其间的数据项是否有修改过，如删去或许新增一项。 threshold：操控扩容时机，当数据项数量大于threshold时进行扩容，新的容量巨细是老的两倍。
loadFactor：默许值0.75，加载因子决定threshold巨细，核算公式是threshold=table.length*loadFactor。
咱们先大致了解一下HashMap成员变量及根底的Key-Value承载的结构，之后随着介绍的进度咱们再介绍新的类型。下面咱们开端正式剖析HashMap的逻辑。

初始化办法

HashMap有4个初始化办法，别离是：

    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        // MAXIMUM_CAPACITY = 1 << 30
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }
    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

第一个初始化办法有两个参数:initialCapacity和loadFactor，看参数名initialCapacity好像是操控初始化时HashMap容量巨细的，实际上它不直接操控巨细，而是经过tableSizeFor办法核算出threshold的值，此刻threshold为大于等于传入的initialCapacity的2的次幂最小值。比方传入3，那么threshold=222^222=4，假如传入9，则threshold=242^424=16。loadFactor初始化HashMap的成员变量loadFactor。

    /**
     * Returns a power of two size for the given target capacity.
     */
    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;
    }

而实际操控容量巨细的逻辑在增加第一个元素时确认，现在先放一边不论，比及介绍增加逻辑时再剖析。
第二个结构函数很简略，直接调用了第一个结构函数，传入initialCapacity和默许的加载因子DEFAULT_LOAD_FACTOR，默许加载因子是0.75。
第三个是无参的结构函数，没有设置threshold，只设置了默许的加载因子0.75。
第四个结构函数则是运用一个现有的Map目标进行初始化操作，首先设置好默许的加载因子，然后运用putMapEntries办法初始化数据项。

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        int s = m.size();
        //若传入的Map为空，则不进行初始化操作
        if (s > 0) {
            //初始化时，HashMap中还没有任何元素，所以table为null，此刻依据传入的map巨细核算出threshold。
            if (table == null) { // pre-size
                float ft = ((float)s / loadFactor) + 1.0F;
                int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                         (int)ft : MAXIMUM_CAPACITY);
                if (t > threshold)
                    threshold = tableSizeFor(t);
            }
            //非初始化（例如调用putAll办法）时，假如传入的map巨细大于threshold，则进行resize扩容操作。
            else if (s > threshold)
                resize();
            //遍历传入的map,顺次调用putVal办法将一切数据加到当时HashMap目标中
            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);
            }
        }
    }

这个办法中所调用的resize和putVal办法在其他当地也有调用，咱们在put办法的完成中再详细剖析，此处只需求知道这个结构函数是经过其他Map目标结构HashMap目标的。
现在现已了解了它的根本结构和一切的结构函数，咱们用一张图先直观的看一下HashMap是什么样的。

操作

1、put操作

put操作的完成逻辑是调用一个内部不可重写的办法putVal完成，这个办法有5个入参，别离是Key的Hash值、Key、Value、onlyIfAbsent、evict。onlyIfAbsent表明是否掩盖相同Key的Value值，为true时，只要本来的Value值为null时才会掩盖，不然不掩盖。为false时直接掩盖原值。下来咱们直接看源码并逐行剖析。

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    @Override
    public V putIfAbsent(K key, V value) {
        return putVal(hash(key), key, value, true, 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;
        /**
        *  将目标成员变量table赋值给局部变量tab并判别是否为null，假如为null，或许不为null则将长度赋给局部变量n，并判别长度是否0。
        *  条件建立的话调用resize()办法对table进行初始化，并将初始化后的table长度从头赋值给n。
        *  留意：除了调用第四个结构办法运用其他Map目标进行初始化，其他三个结构办法结构HashMap目标时，
        *  table默许是null,所以在第一次往HashMap里增加数据时就需求初始化table目标。
        *  resize()办法是HashMap内部的一个通用办法，初始化table、扩容缩容都要用到它，后续还会呈现许屡次，所以一定要眼熟他。
        */
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        /**
        *  长度与key的hash值做按位与运算，得到的成果一定小于长度值。然后将得到的值赋给i，
        *  并从tab中对应槽位取值并赋值给p。假如取到的是null，则标明当时方位没有存其他元素，
        *  能够直接将新元素增加到tab中。若非null，表明key重复或许Key的hash值核算槽位抵触，则进行其他操作。
        */
        if ((p = tab[i = (n - 1) & hash]) == null)
            //直接创建新节点并赋值给tab[i]
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            /**
            *  若新元素的hash值和刚才取到的p的hash值相同，而且p的key和新元素的key相同，
            *  那就表明当时要保存的新key值是已存在的，不必新增，所以将p赋值给e以备后面操作。
            */
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            /**
            *  不然便是Key的槽位抵触，HashMap中假如产生Hash值核算后的槽位抵触，有两种结构进行存储，第一个是链表，第二个是红黑树。
            *  下面的代码会判别p节点是否为TreeNode类型，假如是则将p转为TreeNode，并调用它的putTreeVal办法，将新元素保存到树中。
            */
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            /**
            *  假如不是TreeNode类型便是上面刚开端介绍的一般Node，它里面的next变量能够指向一个Node目标，然后形成链表。
            *  循环遍历p的next是否为null而且复制给e，假如为null，表明现已循环到了链表尾部，接下来创建一个Node节点并赋给p.next，
            *  即链表尾部增加元素。假如不为null表明还没循环到链表尾部，判别是否存在重复元素，和上面判别逻辑相同。假如相同，
            *  则在接下来处理e，假如不相同则进入下一轮循环判别，直到链表尾部。
            *  要留意一点是每新增一个元素到链表尾部时，要判别一下当时链表长度是否大于等于TREEIFY_THRESHOLD，是的话会测验将当时链表转化为红黑树。
            *  TREEIFY_THRESHOLD是用来判别链表是否需求转化红黑树的阈值，它的值为8，即链表长度大于等于8时测验转化为红黑树。
            */
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        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;
                }
            }
            /**
            *  经过上面的核算后，局部变量e假如不为null，则表明当时需求增加的key值以存在，此刻就判别onlyIfAbsent值，
            *  若为false，或许已存在的key值对应的value值是null，则直接掩盖旧值。
            */
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        /**
        *  每进行一次操作（增加，删去等），modCount就加1。每新增一个元素size就加1，
        *  然后判别当时tab中元素数量是否大于threshold，大于则调用resize函数进行扩容。
        */
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

上面put办法整体逻辑概括下来是，Key的hash值是否与数组中已有元素槽位抵触，若未抵触则直接在对应槽位增加元素。不然需求判别Key是否共同，不共同，则将新元素加到链表尾部或许红黑树中，若链表长度超越阈值还需求将链表转化为红黑树。若共同，则需求判别是否掩盖旧值。最终再判别是否要扩容。
reseize()办法在HashMap内部承担着十分重要的使命，包含初始化table，操控table的巨细，操控扩容阈值threshold和扩容操作等。接下来咱们看看resize()的完成逻辑。

final Node<K,V>[] resize() {
        /**
        *  首先将当时table，capacity，threshold悉数暂存到old最初的变量中。
        *  界说新的capacity，threshold变量。界说newCap,newThr变量表明扩容后的table容量和扩容阈值。
        */
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        /**
        *  1、当时容量假如大于0，新的容量将翻倍，而且当时容量假如大于默许的初始化容量（16），那么扩容阈值也翻倍，不然扩容阈值运用加载因子进行核算。
        *  2、当时容量假如等于0，而且当时扩容阈值大于0，那么当时扩容阈值就作为新的容量巨细，用于初始化table，而且从头核算扩容阈值。（无参结构函数初始化HashMap,而且第一次增加元素时的情况）
        *  3、当时容量和扩容阈值都为0时，运用默许的初始化容量（16）并核算扩容阈值（12）
        */
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            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;
        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;
        //扩容结束后，假如旧的table数组不为null，就将旧的数组元素搬迁到扩容后新的table数组中。
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                //不为null阐明旧数组中的这个槽位有元素，将数据赋值给变量e,并开端搬迁。
                if ((e = oldTab[j]) != null) {
                    //旧数组里这个槽方位为null，等候内存回收
                    oldTab[j] = null;
                    //next等于null阐明当时槽位不存在hash抵触的元素，从头核算槽位后放到新数组中。
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    //不然阐明存在抵触，并判别当时槽位中的元素是否是TreeNode类型，假如是的话阐明现已转为红黑树了，所以搬迁逻辑由红黑树逻辑完成。
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    /**
                    *  不是TreeNode类型，那必然是Node类型了，也便是链表，此刻就搬迁链表。但也不是单纯的把链表原样搬迁曩昔，而是会进行核算，
                    *  因为存在这种情况，假如table的长度不长，可是有很多的key产生hash抵触，那么就会呈现某个槽位的链表很长有许大都据，
                    *  但其他槽位根本上没数据的情况，这时就需求将这个长链表拆分红两个长度相对较短的链表，存储在新table的不同槽位上，增加查找效率。
                    */
                    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;
                            /**
                            *  运用元素的hash值和旧链表长度做按位与运算，将长链表拆分红两个链表，一个链表放在和旧table相同方位的新table槽位中，
                            *  另一个链表的槽位间隔第一个槽位隔了一个旧table的长度。
                            */
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            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;
                        }
                    }
                }
            }
        }
        return newTab;
    }

上面说过在增加元素的时候，假如某个槽位的链表长度超越8个就会将链表转化为红黑树，严格来说并非只看链表长度来决定是否进行转化，咱们来剖析一下treeifyBin办法。

final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        //假如当时table数组长度小于转化数规则的最小容量即64时，不转红黑树，只进行扩容。
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        /**
        *  进行转化红黑树前的准备工作，将当时槽位的链表元素由Node类型转化为TreeNode类型，然后运用TreeNode类型的prev和next属性将一切节点连接起来，
        *  构成TreeNode类型链表。最终才调用链表头节点的treeify办法进行红黑树转化。
        */
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;
            do {
                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);
        }
    }

经过上面的treeifyBin办法，咱们知道假如数组长度假如小于64时，即便某个槽位的链表长度超越8也不会转红黑树，而是首先将数组长度扩容到超越64，一起resize办法也会在搬迁数据时依据条件将链表长度超越原数组长度的链表拆分红两个链表保存到不同的槽位。一起咱们也知道了不但是元素个数超越threshold才会扩容，当某个槽位的链表长度超越8而且数组长度小于64也会触发数组扩容。而红黑树的原理和详细操作本文不做详细介绍，有兴趣的能够看看网上这篇文章或许自行查找。

现在咱们现已剖析了增加元素的源代码逻辑了，接下来咱们结合几个比如和图来进一步加深理解。为了模仿Hash抵触的情况，咱们先界说一个类Student，而且重写它的hashCode和equals办法，hashCode办法只核算name，equals办法核算name和age，保证Student类作为Key保存到HashMap中时产生Hash抵触，使程序依照咱们预想的方向运转。

package com.xxx.demo;
import java.util.Objects;
public class Student {
    private Integer age;
    private String name;
    public Student(Integer age, String name) {
        this.age = age;
        this.name = name;
    }
    public Integer getAge() {
        return age;
    }
    public String getName() {
        return name;
    }
    @Override
    public boolean equals(Object o) {
        if (Objects.isNull(o)) {
            return false;
        }
        if (!(o instanceof Student)) {
            return false;
        }
        Student target = (Student) o;
        return age.equals(target.getAge()) && name.equals(target.getName());
    }
    @Override
    public int hashCode() {
        return name.hashCode();
    }
}

接下来咱们创建一个HashMap，并往其间增加若干元素，然后剖析一下这个HashMap内部是如何运转的。

public static void main(String[] args){
  Map<Student,String> map = new HashMap<>(4);
  map.put(new Student(18,"张三"),"value1");
  map.put(new Student(18,"李四"),"value2");
  map.put(new Student(19,"王五"),"value3");
  map.put(new Student(18,"张三"),"value4");
  map.put(new Student(19,"张三"),"value5");
  map.put(new Student(20,"张三"),"value6");
  map.put(new Student(21,"张三"),"value7");
  map.put(new Student(22,"张三"),"value8");
  map.put(new Student(23,"张三"),"value9");
  map.put(new Student(24,"张三"),"value10");
  map.put(new Student(25,"张三"),"value11");
  map.put(new Student(16,"张麻子"),"value12");
  map.put(new Student(26, "张三"), "value13");
}

首先初始化HashMap时传入了initialCapacity=4，依据咱们上面剖析的初始化逻辑，此刻map目标中的loadFactor=0.75（默许），threshold=4（大于等于4的2的最小次幂值），table=null，size=0，modCount=0。
然后增加第一个Key-Value对后，size=1，modCount=1，table初始化长度为4的Node<Student,String>数组，threshold变为3（4*0.75）

    public void putAll(Map<? extends K, ? extends V> m) {
        putMapEntries(m, true);
    }

2、删去元素操作

咱们首先看一下删去办法源码

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

remove办法内部调用removeNode办法，将指定Key的元素删去，并在删去成功后回来对应Key的value值。下面是removeNode的源码。

    /**
    *  hash:Key的hashcode
    *  matchValue: 是否匹配value，true的话表明不但匹配Key，还需求匹配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的hash值和要删去的hash值一样，而且Key本身持平，阐明p便是要删去的值，则将p赋值给node；
            *  不然阐明存在hash相同，但值不相同的key，即hash抵触。此刻判别p.next是否有值，
            *  有值代表链表或红黑树存在，能够在链表或红黑树上进一步检索Key，假如找到了则赋值给node。
            */
            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);
                }
            }
            /**
            *  若node有值，而且不匹配value值，或许value值匹配成功，即开端删去操作。
            *  假如node是TreeNode类型，则调用红黑树的移除操作对元素进行移除。不然是Node类型；
            *  node==p阐明直接在槽位上匹配到元素了，没有进行hash抵触判别，所以直接将node的next赋值给槽位，
            *  node目标在当时办法履行完后就失去了引证，能够被GC。
            *  若node不等于p，则阐明进行了hash抵触判别，也是相同的道理，把node的next复制给p.next，
            *  node失去引证等候被GC。最终回来匹配到的node即可。
            */
            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;
    }

上面的删去办法咱们剖析了删去的相关逻辑，当然除了红黑树的删去办法，本文不详细介绍红黑树。不过HashMap中有个逻辑还得说一下。在增加元素的办法中，咱们知道链表转红黑树的条件是：数组长度大于等于64，链表长度超越8，那么就会被转化成红黑树。假如删去红黑树里的元素，达到什么条件时，红黑树才退化成链表？这块的逻辑在removeTreeNode办法和split中

final void removeTreeNode(HashMap<K,V> map,Node<K,V>[] tab, boolean movable){
          ......
          //树根节点为null，或许不为null的情况下，跟节点的右节点是空的，或许左节点是空的，或许右节点的左节点是空的，此刻履行退化操作
          if (root == null
                || (movable
                    && (root.right == null
                        || (rl = root.left) == null
                        || rl.left == null))) {
                tab[index] = first.untreeify(map);  // too small
                return;
            }
            ......
}
final void split(HashMap<K,V> map,Node<K,V>[] tab,int index, int bit){
          ......
          //lchc为树上的元素个数，假如元素个数少于等于UNTREEIFY_THRESHOLD时，则将树退化到链表，UNTREEIFY_THRESHOLD的值为6.
          if (loHead != null) {
                if (lc <= UNTREEIFY_THRESHOLD)
                    tab[index] = loHead.untreeify(map);
                else {
                    tab[index] = loHead;
                    if (hiHead != null) // (else is already treeified)
                        loHead.treeify(tab);
                }
            }
            if (hiHead != null) {
                if (hc <= UNTREEIFY_THRESHOLD)
                    tab[index + bit] = hiHead.untreeify(map);
                else {
                    tab[index + bit] = hiHead;
                    if (loHead != null)
                        hiHead.treeify(tab);
                }
            }
            ......
}

在咱们剖析完增加元素的逻辑和源码后，再看上面移除元素的逻辑就很简略了，其间匹配元素的逻辑在putVal办法中也呈现过，老眼熟了。下面咱们简略的图示一下移除的步骤。

    public void clear() {
        Node<K,V>[] tab;
        modCount++;
        if ((tab = table) != null && size > 0) {
            size = 0;
            for (int i = 0; i < tab.length; ++i)
                tab[i] = null;
        }
    }

3、查找元素

在介绍查找元素办法之前，咱们先看一下HashMap中调集相关的源码和逻辑。HashMap中有三个获取调集的办法：keySet(),values(),entrySet()，别离回来Key的调集，value的调集及键值对调集，三个办法的完成都依靠内部类KeySet,EntrySet,Values。其间KeySet和EntrySet承继自AbstractSet抽象类，Values承继自AbstractCollection抽象类，下面咱们只剖析EntrySet调集的源码和逻辑，KeySet和Values调集逻辑类似，有兴趣的能够自行查看。

    public Set<Map.Entry<K,V>> entrySet() {
        Set<Map.Entry<K,V>> es;
        return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
    }
    final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
        //大都办法的中心完成逻辑都是依靠HashMap中的逻辑完成。
        public final int size()                 { return size; }
        public final void clear()               { HashMap.this.clear(); }
        public final Iterator<Map.Entry<K,V>> iterator() {
            return new EntryIterator();
        }
        public final boolean contains(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry<?,?> e = (Map.Entry<?,?>) o;
            Object key = e.getKey();
            Node<K,V> candidate = getNode(hash(key), key);
            return candidate != null && candidate.equals(e);
        }
        public final boolean remove(Object o) {
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>) o;
                Object key = e.getKey();
                Object value = e.getValue();
                return removeNode(hash(key), key, value, true, true) != null;
            }
            return false;
        }
        public final Spliterator<Map.Entry<K,V>> spliterator() {
            return new EntrySpliterator<>(HashMap.this, 0, -1, 0, 0);
        }
        /**
        *  遍历办法对一切元素进行遍历时，会判别modCount是否有改变，假如有变，阐明在遍历途中，有其他线程对元素进行了增加或许删去，
        *  有线程安全问题所以抛出反常。或许在遍历办法内对调集元素进行了增加或删去操作。
        */
        public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
            Node<K,V>[] tab;
            if (action == null)
                throw new NullPointerException();
            if (size > 0 && (tab = table) != null) {
                int mc = modCount;
                for (int i = 0; i < tab.length; ++i) {
                    for (Node<K,V> e = tab[i]; e != null; e = e.next)
                        action.accept(e);
                }
                if (modCount != mc)
                    throw new ConcurrentModificationException();
            }
        }
    }

经过上面的forEach办法，咱们总算知道了modCount到底是干吗用的了，modCount便是为了保证，在任何时候遍历该键值对的调集时保证调集内的值不会改变，导致产生“明明我都遍历一切元素统一处理了，为什么还有好几个元素不收效”这种事情。
接下来咱们正式看看查询相关代码逻辑。

    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        /**
        *  依据Key的hash值，核算出所在槽位。并去除对应槽位的值赋值给first变量。
        *  first变量hash值和办法入参的hash值持平，而且first.key与入参key持平，表明找到节点数据，并回来。
        *  hash值持平，但first.key与入参key不持平，阐明有hash抵触。若first是TreeNode类型阐明当时槽位现已是红黑树，则运用红黑树的办法进行元素查找。不然是链表，遍历链表的next属性进行查找
        *  将找到的元素回来，未找到则回来null
        */
        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;
    }
    public boolean containsKey(Object key) {
        return getNode(hash(key), key) != null;
    }
    @Override
    public V getOrDefault(Object key, V defaultValue) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
    }

查找元素的办法逻辑十分清晰和简单理解，getNode办法作为内部的办法被许多办法调用，是一个公共的查找元素办法。

其他办法

除了根本增加元素、删去元素、查找元素等办法，还有其他的办法供给给咱们，以支持更多的功能。

  /**
  *  替换Value，查到对应Key的元素节点后，判别Value值是否等于给定的oldValue，持平则将newValue值替换至元素节点，不持平则不替换。
  */
  public boolean replace(K key, V oldValue, V newValue) {
        Node<K,V> e; V v;
        if ((e = getNode(hash(key), key)) != null &&
            ((v = e.value) == oldValue || (v != null && v.equals(oldValue)))) {
            e.value = newValue;
            afterNodeAccess(e);
            return true;
        }
        return false;
    }
    /**
    *  查找到对应Key元素节点后，直接对Value值进行替换，不进行其他逻辑判别。
    */
    @Override
    public V replace(K key, V value) {
        Node<K,V> e;
        if ((e = getNode(hash(key), key)) != null) {
            V oldValue = e.value;
            e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
        return null;
    }
    /**
    *  经过给定的Key查找元素，将查到的元素Key、Value值传入入参的回调函数，并经过回调函数承受一个回来值，
    *  若回来值不为null，用回来值替换旧的value值，不然删去查到的元素。
    */
    public V computeIfPresent(K key,
                              BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
        if (remappingFunction == null)
            throw new NullPointerException();
        Node<K,V> e; V oldValue;
        int hash = hash(key);
        if ((e = getNode(hash, key)) != null &&
            (oldValue = e.value) != null) {
            V v = remappingFunction.apply(key, oldValue);
            if (v != null) {
                e.value = v;
                afterNodeAccess(e);
                return v;
            }
            else
                removeNode(hash, key, null, false, true);
        }
        return null;
    }

除了上面介绍的几类办法，还有逻辑类似或许效果类似的几个办法，包含兼并办法，替换元素办法，遍历办法等等，就不逐个介绍了，有兴趣的话各位能够自己看看。
另外在咱们上面剖析的很多的源码逻辑中，能够看到呈现了许屡次的afterNodeAccess,afterNodeInsertion,afterNodeRemoval的办法调用，这些办法在HashMap内部没有完成是个空办法，实际上的完成是在LinkedHashMap类中，而LinkedHashMap则是承继自HashMap的，所以LinkedHashMap实例在调用父类办法，也便是HashMap中的相关逻辑时，这几个办法才有本质的效果。

总结

HashMap是建立在Hash算法和数组之上，具有对数组进行随机拜访才能的Key-Value结构，一起在处理Hash抵触时运用了不同的战略即链表和红黑树，得益于此，HashMap具有比较高的性能，各类开源中间件中也有很多的运用，日常编程中也会十分频繁的运用到HashMap。但HashMap是非线程安全的，多个线程一起对它进行操作会呈现线程安全问题，假如要在多线程环境中运用Key-Value结构的数据结构容器，能够运用ConcurrentHashMap。