【打怪升级】【容器】关于Map

关于Map接口，具体的实现有HashMap、HashTable、TreeMap等

• HashMap

老规矩，如果我们要看源码，我们要从这么几点去看：它的继承结构、它的核心实现能力。我们知道hashMap是一个kv容器，那么它的实现其实主要取决于这几点：

1.存放 如何处理hash冲突 怎么存？

2.获取 怎么通过key获取？

(资料图片)

3.扩容 什么时候 什么条件会扩容？

4.删除 怎么样删除一个元素

非常简洁的继承结构，除了序列化和拷贝支持还继承了AbstractMap复用key，value结构的部分通用功能。

我们先来看一下hashmap的结构

首先说明一下，(n - 1) % hash 和 (n - 1) & hash，(2^h - 1) & hash 是等价的，其中n = 2^h，后者运算效率更高。

通过hashMap的继承结构，我们可以发现首先它实现了上层Map，并且实现了AbstractMap，HashMap内部采用的是数组+链表的结构，作为元素的存放，在存入的时候会先进行(n - 1) & hash。

HashMap采用了数组加链表的结构，在存入元素的时候，会先通过(n - 1) & hash获取hash存储的位置，这个位置就是key存放的位置，其实就是(n - 1) % hash，n相当于数组的长度，因为要&运算，所以长度必须是2的n次幂。

只有当hash发生了冲突，元素的内容不一样，但是hash值一样，这时候两个元素通过(n - 1) & hash均放在了同一个位置，这时候才会在链表中放入元素。

那么。在hashMap中，Node又是用来干什么的呢？

数组中每个元素都被包装成了Node，其内部有四个属性，详情看源码：

/* ---------------- Fields -------------- */    /**     * The table, initialized on first use, and resized as     * necessary. When allocated, length is always a power of two.     * (We also tolerate length zero in some operations to allow     * bootstrapping mechanics that are currently not needed.)     */

//这个就是存储元素的数组

transient Node[] table;

static class Node implements Map.Entry {　　　　  //key hash        final int hash;　　　　　// 元素的key　        final K key;　　　　　//元素的value        V value;　　　　 //下一个node指针        Node next;        Node(int hash, K key, V value, Node 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;        }    }

当发生了hash冲突、元素内容不一样但是hash一样，才会在链表中放入元素，数组中的元素被Node进行包装，内部分别是key、value、hash、和next指针。

那么，hashmap是如何进行hash计算的呢？

static final int hash(Object key) {        int h;        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

key的hash计算并没有我们想想的那么复杂，首先null的hash永远为0，其次是将元素本身的hashCode取反，再与高16位异或计算。我们知道hashCode返回的是int值，所以最大就是32个字节。由于计算下标的时候是，(n-1) & hash。所以当n - 1，比较小的时候，只能与hash 的低位计算。比如数字 786431 和 1835007 的低位全都是1，但是他们的高位却不相同。这个时候让高位参与计算，会进一步减少碰撞的概率。

那么了解到hashmap的基本结构后，我们要从源码的结构和方法进一步了解它

首先看看HashMap的成员变量

//默认的数组长度 16static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //数组最大长度 1073741824static final int MAXIMUM_CAPACITY = 1 << 30;//默认的扩容因子static final float DEFAULT_LOAD_FACTOR = 0.75f;//当链表的长度大于这个数字的时候，会转换成数结构static final int TREEIFY_THRESHOLD = 8;//存放数据的数组，内部都是一个个链表transient Node[] table;//entrySet的引用，会在调用entrySet()时候赋值transient Set> entrySet;//这个是Map内的元素个数，每put一个元素进来就会+1。当size大于threshold的时候就会扩容transient int size;//防止并发修改的计数器transient int modCount;//扩容的阈值//当数组初始化的时候会被用来记录初始化数组长度，这个时候他的长度就是数组的长度。其他的时候就和数组长度没哈关系了int threshold;//扩容因子，默认值是 DEFAULT_LOAD_FACTOR = 0.75。用来计算扩容的阈值final float loadFactor;

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 很重要！！！ 它通过获取最近的2^n，指定初始化长度        this.threshold = tableSizeFor(initialCapacity);    }    /**     * Constructs an empty HashMap with the specified initial     * capacity and the default load factor (0.75).     *     * @param  initialCapacity the initial capacity.     * @throws IllegalArgumentException if the initial capacity is negative.     */    public HashMap(int initialCapacity) {　　　　　//指定长度，扩容因子0.75        this(initialCapacity, DEFAULT_LOAD_FACTOR);    }    /**     * Constructs an empty HashMap with the default initial capacity     * (16) and the default load factor (0.75).     */    public HashMap() {　　　　　//默认长度16 扩容因子0.75        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted    }    /**     * Constructs a new HashMap with the same mappings as the     * specified Map.  The HashMap is created with     * default load factor (0.75) and an initial capacity sufficient to     * hold the mappings in the specified Map.     *     * @param   m the map whose mappings are to be placed in this map     * @throws  NullPointerException if the specified map is null     */    public HashMap(Map m) {        this.loadFactor = DEFAULT_LOAD_FACTOR;        putMapEntries(m, false);    }

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;    }

当cap正好就是2^n时 不减1会直接扩大一倍    之前说了cap最近的2^n数字，比如 3 离它最近的是4，那么对于4呢？其实离他最近的是8。    如果直接运算，会扩大一倍，所以将4减1，变成3，也就是离3最近的就是4。

n溢出，或者达到最大容量。正常情况下将n+1还原

扩容：

扩容，是hashmap的一个核心方法，这个跟其他容器一样，为了节约空间。所以我们在业务开发中，往往在特定长度需要指定它的长度避免它频繁扩容！！！

final Node[] resize() {    //记住当前的元素数组    Node[] oldTab = table;    //当前的数组容量，没有初始化就是0    int oldCap = (oldTab == null) ? 0 : oldTab.length;    //当前的数组的分配长度    int oldThr = threshold;    //newCap是新的数组长度和newThr 是新的数组容量    int newCap, newThr = 0;    //原来的数组不是空的    if (oldCap > 0) {        //原来的数组已经达到最大长度限制        if (oldCap >= MAXIMUM_CAPACITY) {            //直接将分配长度扩大成最大值，其实就是不能扩容了。            threshold = Integer.MAX_VALUE;            return oldTab;        }        //如果不是初始容量，老的数组长度扩大2倍 并且还在最大容量内        //并且老的容量已经超过了默认的初始值16        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&                 oldCap >= DEFAULT_INITIAL_CAPACITY)            //新的阈值是原来的2倍            newThr = oldThr << 1;     }    //初始化的时候指定了容量，直接使用指定的容量初始化    //这里比较绕，因为它构造里边用的是threshold来记录的初始化长度    //所以后边还会有 newThr == 0 的情况    else if (oldThr > 0)         newCap = oldThr;    else {       //采用默认的数据初始化，数组长度是 16，扩容因子是0.75。阈值是12        newCap = DEFAULT_INITIAL_CAPACITY;        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);    }    //这里是，初始化的时候指定了容量    //或者现有的容量小于 DEFAULT_INITIAL_CAPACITY 或者 扩容后超出MAXIMUM_CAPACITY 是触发    if (newThr == 0) {        //新的数组扩容阈值        float ft = (float)newCap * loadFactor;        //确定新的阈值，新的容量小于MAXIMUM_CAPACITY 并且临界值 也小于MAXIMUM_CAPACITY 才会用ft        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?                  (int)ft : Integer.MAX_VALUE);    }    //新的阈值    threshold = newThr;    @SuppressWarnings({"rawtypes","unchecked"})        //使用新的容量去初始化一个新的Node数组,newCap必须是2^n        Node[] newTab = (Node[])new Node[newCap];    table = newTab;    //处理旧数组里的数组    if (oldTab != null) {        //遍历原来数组的每个元素        for (int j = 0; j < oldCap; ++j) {            Node e;            if ((e = oldTab[j]) != null) {                oldTab[j] = null;                if (e.next == null)                    //如果只有一个元素，将元素的hash与现在的位置取余确定新的数组下标                    newTab[e.hash & (newCap - 1)] = e;                else if (e instanceof TreeNode)                    //对于数结构的处理                    ((TreeNode)e).split(this, newTab, j, oldCap);                else {                     //这个是将原始的链表拆分开，分成高位和低位。                    //低位不用移动，高位放到现有的位置 + 数组的原始长度处                    Node loHead = null, loTail = null;                    Node hiHead = null, hiTail = null;                    Node next;                    do {                        next = e.next;                        //这个就是判断数据是处于低位还是高位                        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;}

对于新数组容量和扩容阈值；

数组中链表只有一个元素，那么直接存储；

数组中是一个红黑树结构；

数组中还没有到达红黑树结构、但是有多个、拆分链表；

其中，HashMap提供了TreeNode，当数组内链表长度大于8后转换为TreeNode。

其中，默认的扩容因子是0.75，意味着：当添加某个元素后，数组的总的添加元素数大于了 数组长度 * 0.75(默认,也可自己设定),数组长度扩容为两倍。(如开始创建HashMap集合后，数组长度为16，临界值为16 * 0.75 = 12，当加入元素后元素个数超过12，数组长度扩容为32，临界值变为24)

Map只有在添加的时候才会扩容，删除的时候是不会缩容的。

接下来，我们看看针对容器的操作方法：

添加元素：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,               boolean evict) {    Node[] tab; Node p; int n, i;    //如果table 还没初始化，调用resize()初始化一个数组    if ((tab = table) == null || (n = tab.length) == 0)        n = (tab = resize()).length;    //通过(n - 1) & hash 计算元素的下标，如果下标出没有元素，直接初始化一个    if ((p = tab[i = (n - 1) & hash]) == null)        tab[i] = newNode(hash, key, value, null);    else {        //下标出已经有元素了，p就是下标处链表的头        Node e; K k;        //当前元素的hash和下标处表头的hash相等，并且他们的key相等，直接辅助e        //这其实是个优化措施，比如你put一个key已经存在的元素        if (p.hash == hash &&            ((k = p.key) == key || (key != null && key.equals(k))))            e = p;        //如果p已经转化成树结构，树结构处理        else if (p instanceof TreeNode)            e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);        else {            //以p为起点，循环链表            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;            }        }        //当前key对应的节点已经存在        if (e != null) {             //将原来节点里的值替换掉            V oldValue = e.value;            //原来的值是null或者明确指定了onlyIfAbsent 的才更新            if (!onlyIfAbsent || oldValue == null)                e.value = value;            //模板方法，里边是个空实现            afterNodeAccess(e);            return oldValue;        }    }    //操作次数加1    ++modCount;    //元素数量+1，并且与扩容阈值比较    if (++size > threshold)        resize();    //模板方法，里边是个空实现    afterNodeInsertion(evict);    return null;}

总体来说，HashMap添加元素可以分为这几步：

1.初始化

2.查找元素位置，如果当前位置是空，那么直接放，如果不是空就遍历链表看看元素是否存在？存在就更新，不存在则添加

public V put(K key, V value) {    return putVal(hash(key), key, value, false, true);}public V putIfAbsent(K key, V value) {    return putVal(hash(key), key, value, true, true);}

这些都是基于putVal去实现的。

如果通过别的方式添加元素，例如putMapEntries：

final void putMapEntries(Map m, boolean evict) {    //获取待添加的map元素个数    int s = m.size();    if (s > 0) {        if (table == null) {             //反算一下容量的大小            float ft = ((float)s / loadFactor) + 1.0F;            int t = ((ft < (float)MAXIMUM_CAPACITY) ?                     (int)ft : MAXIMUM_CAPACITY);            //已经超过了容量的阈值            if (t > threshold)                //将容量阈值规整为2^n形式                threshold = tableSizeFor(t);        }        //如果超限了 直接去扩容，确定一个合适的容量        else if (s > threshold)            resize();        for (Map.Entry e : m.entrySet()) {            K key = e.getKey();            V value = e.getValue();            //使用putVal一个一个添加            putVal(hash(key), key, value, false, evict);        }    }}//快捷方法public void putAll(Map m) {    putMapEntries(m, true);}

删除元素：

final Node removeNode(int hash, Object key, Object value,                           boolean matchValue, boolean movable) {    Node[] tab; Node p; int n, index;    //只有table不为空，并且存在数据的时候才处理    if ((tab = table) != null && (n = tab.length) > 0 &&        (p = tab[index = (n - 1) & hash]) != null) {        Node node = null, e; K k; V v;        //这里是为了key对应的元素位置，一样是个优化策略。直接看第一个位置是不是要找的元素        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)p).getTreeNode(hash, key);            else {                //循环列表，看能不能找到key对应的位置                do {                    if (e.hash == hash &&                        ((k = e.key) == key ||                         (key != null && key.equals(k)))) {                        node = e;                        break;                    }                    p = e;                } while ((e = e.next) != null);            }        }        //通过上边的查找，如果找到了key对应的node节点        //如果启用了value匹配，并且value是匹配的。就准备删除节点         if (node != null && (!matchValue || (v = node.value) == value ||                             (value != null && value.equals(v)))) {            //树节点单独处理            if (node instanceof TreeNode)                ((TreeNode)node).removeTreeNode(this, tab, movable);            else if (node == p)                //如果第一个节点就是node，直接替换掉第一个元素                tab[index] = node.next;            else                //直接替换next指针到node的下一个节点                p.next = node.next;            //操作次数增加            ++modCount;            //元素数量减少            --size;            //模板方法，其实是个空实现            afterNodeRemoval(node);            return node;        }    }    return null;}

删除元素的动作也可以分为两步：

1.找到key对应的位置，且hash和key都相等

2.处理结构，数组还是链表？

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

以上都是通过removeNode实现。

清空元素：

public void clear() {    Node[] tab;    modCount++;    if ((tab = table) != null && size > 0) {        size = 0;        //直接把数组的元素置空，数组的大小不变        for (int i = 0; i < tab.length; ++i)            tab[i] = null;    }}

查找元素：

这是比较核心，也比较粗暴的方式

final Node getNode(int hash, Object key) {    Node[] tab; Node first, e; int n; K k;    //table不是空的，并且key对应的下标是有数据存在的    if ((tab = table) != null && (n = tab.length) > 0 &&        (first = tab[(n - 1) & hash]) != null) {        //优化策略，首先检查第一个节点不是要找e 的key，如果是直接返回。        if (first.hash == hash &&             ((k = first.key) == key || (key != null && key.equals(k))))            return first;        //链表不止一个元素        if ((e = first.next) != null) {            //树结构单独处理            if (first instanceof TreeNode)                return ((TreeNode)first).getTreeNode(hash, key);            do {                //循环链表一直找到key                if (e.hash == hash &&                    ((k = e.key) == key || (key != null && key.equals(k))))                    return e;            } while ((e = e.next) != null);        }    }    return null;}

查找元素，就过于粗暴了。当然为了效率，会在链表长度大于8时自动转化为红黑树结构。

public V get(Object key) {    Node e;    return (e = getNode(hash(key), key)) == null ? null : e.value;}public boolean containsKey(Object key) {    return getNode(hash(key), key) != null;}//不存在元素的时候，使用一个默认值替换public V getOrDefault(Object key, V defaultValue) {    Node e;    return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;}

这些都是通过getNode实现。

修改元素：

public boolean replace(K key, V oldValue, V newValue) {    Node e; V v;    //直接获取元素，如果是空的或者和oldValue不想等，就不处理    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;}//和上边一样，只是少了旧值的比较操作public V replace(K key, V value) {    Node e;    if ((e = getNode(hash(key), key)) != null) {        V oldValue = e.value;        e.value = value;        afterNodeAccess(e);        return oldValue;    }    return null;}public void replaceAll(BiFunction function) {    Node[] tab;    if (function == null)        throw new NullPointerException();    if (size > 0 && (tab = table) != null) {        int mc = modCount;        //先循环数组        for (int i = 0; i < tab.length; ++i) {            //在循环数组内的链表            for (Node e = tab[i]; e != null; e = e.next) {                //使用function替换每个元素                e.value = function.apply(e.key, e.value);            }        }        //如果发生了并发修改，就报错        if (modCount != mc)            throw new ConcurrentModificationException();    }}

遍历容器：

HashIterator 是针对内部key和value的迭代器实现

abstract class HashIterator {    Node next;        // next entry to return    Node current;     // current entry    int expectedModCount;  // for fast-fail    int index;             // current slot    HashIterator() {        //记录当前被操作数量        expectedModCount = modCount;        //table引用        Node[] t = table;        current = next = null;        index = 0;        //这个是为找到数组中第一个不是空的链表        if (t != null && size > 0) { // advance to first entry            do {} while (index < t.length && (next = t[index++]) == null);        }    }    public final boolean hasNext() {        return next != null;    }    final Node nextNode() {        Node[] t;        Node e = next;        //并发操作检测        if (modCount != expectedModCount)            throw new ConcurrentModificationException();        //如果数组中存在空的就报错        if (e == null)            throw new NoSuchElementException();        //获取到下一个不是空的元素，并赋值给current 和 next        if ((next = (current = e).next) == null && (t = table) != null) {            do {} while (index < t.length && (next = t[index++]) == null);        }        return e;    }        //就是用的removeNode 其实只是加了并发检测    public final void remove() {        Node p = current;        if (p == null)            throw new IllegalStateException();        if (modCount != expectedModCount)            throw new ConcurrentModificationException();        current = null;        K key = p.key;        removeNode(hash(key), key, null, false, false);        expectedModCount = modCount;    }}

KeySet

public Set keySet() {    Set ks = keySet;    if (ks == null) {        //创建一个KeySet引用        ks = new KeySet();        keySet = ks;    }    return ks;}final class KeySet extends AbstractSet {    public final int size()                 { return size; }    public final void clear()               { HashMap.this.clear(); }    //这个就是for循环语法糖会用的    public final Iterator iterator()     { return new KeyIterator(); }    public final boolean contains(Object o) { return containsKey(o); }    public final boolean remove(Object key) {        return removeNode(hash(key), key, null, false, true) != null;    }    public final Spliterator spliterator() {        return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);    }    public final void forEach(Consumer action) {        Node[] tab;        if (action == null)            throw new NullPointerException();        if (size > 0 && (tab = table) != null) {            int mc = modCount;            //先循环数组            for (int i = 0; i < tab.length; ++i) {                //再循环链表，但是只寻找元素的key                for (Node e = tab[i]; e != null; e = e.next)                    action.accept(e.key);            }            if (modCount != mc)                throw new ConcurrentModificationException();        }    }}//继承了上边的HashIterator，next里只keyfinal class KeyIterator extends HashIterator    implements Iterator {    public final K next() { return nextNode().key; }}

Values

public Collection values() {    Collection vs = values;    if (vs == null) {        //使用Values,和keySet机会        vs = new Values();        values = vs;    }    return vs;}final class Values extends AbstractCollection {    public final int size()                 { return size; }    public final void clear()               { HashMap.this.clear(); }    //这个就是for循环语法糖会用的    public final Iterator iterator()     { return new ValueIterator(); }    public final boolean contains(Object o) { return containsValue(o); }    public final Spliterator spliterator() {        return new ValueSpliterator<>(HashMap.this, 0, -1, 0, 0);    }    public final void forEach(Consumer action) {        Node[] 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 e = tab[i]; e != null; e = e.next)                    action.accept(e.value);            }            if (modCount != mc)                throw new ConcurrentModificationException();        }    }}//继承了上边的HashIterator，next里只valuefinal class ValueIterator extends HashIterator    implements Iterator {    public final V next() { return nextNode().value; }}

快速失败

8版本之后的快速失败：HashMap提供了一个modCount来定义修改的次数，如果常规遍历的情况下，再进行操作时会修改modCount的值，但是不会修改expectedModCount，每次操作时只要它两不相等就会出现ConcurrentModificationException异常。如果使用迭代器Iterator本身的操作例如remove方法操作时，会同时更新expectedModCount，那么就不会抛出ConcurrentModificationException的异常了。

树化

TreeNode是HashMap的内部类，当数组内链表的长度大于8的时候会转换为TreeNode，进一步加强查找效率

首先，为什么HashMap要采用红黑树呢？具体我们可以参考红黑树的数据结构模型。这里不做过多解释，但是要明确一点，红黑树的特性就是从根到叶子节点的长度不会过长，它们是一个相对平衡的状态，哪怕有大量的数据，也能避免在一个根节点下大量遍历查找。从而提高查找效率。

但是通过添加到指定长度以上，会进入treeifyBin方法，这个方法会将Node节点转为TreeNode节点。注意！！！！因为Node有指针的，这里还是上下节点，所以它还没有达到一个红黑树的标准。

我们都知道看一个树形结构，我们要通过它的继承看到它的特性。我们来看看Node和TreeNode的区别：

static final class TreeNode extends LinkedHashMap.Entry static class Node implements Map.Entry

它们都基于KV存储实现，但是不一样的是TreeNode又继承了linkedHashMap。

final void treeifyBin(Node[] tab, int hash) {        int n, index; Node e;        //如果当前列表小于64 就进行扩容就够了        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)            resize();        else if ((e = tab[index = (n - 1) & hash]) != null) {            //如果已经大于64了，先将链表转化为树结构，注意此时还不是红黑树 这些树的元素通过next指针相连            TreeNode hd = null, tl = null;            do {                //先生成TreeNode节点                TreeNode p = replacementTreeNode(e, null);                if (tl == null)                    //先将head 设置为第一个TreeNode                    hd = p;                else {                    //新插入的TreeNode 的parent 就是上一个Node 如果前面没有那就是header                    p.prev = tl;                    tl.next = p;                }                //尾设置为最新插入的节点                tl = p;            } while ((e = e.next) != null);            if ((tab[index] = hd) != null)                //树化                hd.treeify(tab);        }    }

通过treeifyBin我们可以发现，这里开始处理TreeNode了，但此时它应该称为树，而不是红黑树，因为它们的节点是相连的

final void treeify(Node[] tab) {            TreeNode root = null;            //遍历树节点            for (TreeNode x = this, next; x != null; x = next) {                //处理第一个树节点                next = (TreeNode)x.next;                x.left = x.right = null;                if (root == null) {                    //如果当前没有根节点，那么它就当根节点 它是一个black节点                    x.parent = null;                    x.red = false;                    root = x;                }                else {                    K k = x.key;                    int h = x.hash;                    Class kc = null;                    for (TreeNode p = root;;) {                        //如果已经有根节点，那么就要遍历处理向左或者向右偏移                        int dir, ph;                        K pk = p.key;                        //如果hash大于插入节点的hash 那么就要去左树继续查找                        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 xp = p;                        //根据dir 就知道到底在左还是在右                        //如果当前为空了，那么就应该将它插入了                        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);        }

那么在数据找到位置并插入后，就要做红黑树的处理balanceInsertion

static  TreeNode balanceInsertion(TreeNode root,                                                    TreeNode x) {            x.red = true;            for (TreeNode xp, xpp, xppl, xppr;;) {                if ((xp = x.parent) == null) {                    x.red = false;                    return x;                }                else if (!xp.red || (xpp = xp.parent) == null)                    return root;                if (xp == (xppl = xpp.left)) {                    if ((xppr = xpp.right) != null && xppr.red) {                        xppr.red = false;                        xp.red = false;                        xpp.red = true;                        x = xpp;                    }                    else {                        if (x == xp.right) {                            root = rotateLeft(root, x = xp);                            xpp = (xp = x.parent) == null ? null : xp.parent;                        }                        if (xp != null) {                            xp.red = false;                            if (xpp != null) {                                xpp.red = true;                                root = rotateRight(root, xpp);                            }                        }                    }                }                else {                    if (xppl != null && xppl.red) {                        xppl.red = false;                        xp.red = false;                        xpp.red = true;                        x = xpp;                    }                    else {                        if (x == xp.left) {                            root = rotateRight(root, x = xp);                            xpp = (xp = x.parent) == null ? null : xp.parent;                        }                        if (xp != null) {                            xp.red = false;                            if (xpp != null) {                                xpp.red = true;                                root = rotateLeft(root, xpp);                            }                        }                    }                }            }        }

这里是将节点旋转处理，做左旋转或右旋转，这里对这个不做过多解释，有兴趣可以根据源码看看如何转换的，其中在插入数据时如果检查到是TreeNode，就根据putTreeVal处理，这里的方法类似。

其中如果是treeNode进行查找 也是根据树形查找方式，这里如果对数据结构比较熟悉的朋友应该已经知道了

final TreeNode getTreeNode(int h, Object k) {            return ((parent != null) ? root() : this).find(h, k, null);        }

• ConcurrentHashMap

ConcurrentHashMap是juc下的一个线程安全容器，主要是为了解决HashMap线程不安全的场景。

在jdk7中，ConcurrentHashMap保证线程安全的方式就是Segment，分段锁，默认Segment是16个，分段加锁保证读写效率。可以在初始化时修改

每个Segment中，我们可以看作每个Segment里面就是一个HashMap的结构，每个Segment都持有了独立的ReentrantLock，关于ReentrantLock可以参考aqs的原理。

所以在操作每个Segment时，互相是不干扰的。

但是在jdk8里，将Segment换成了Node，每个Node有自己的锁，通过CAS原理。

简单了解一下7中的原理

static final class Segment extends ReentrantLock implements Serializable {    private static final long serialVersionUID = 2249069246763182397L;    static final int MAX_SCAN_RETRIES =        Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;    transient volatile HashEntry[] table;    transient int count;    transient int modCount;    transient int threshold;    final float loadFactor;}final Segment[] segments;

HashEntry(哈希数组)，threshold(扩容阈值)，loadFactor(负载因子)表示segment是一个完整的HashMap。

public ConcurrentHashMap(int initialCapacity,float loadFactor, int concurrencyLevel)

初始容量：初始容量表示所有的segment数组中，一共含有多少个hashentry。若initialCapacity不为2的幂，会取一个大于initialCapacity的2的幂。　　负载因子：默认0.75　　并发级别：可以同时允许多少个线程并发。concurrencyLevel为多少，就有多少个segment，当然也会取一个大于等于这个值的2的幂。

而在8中，其实采用的是Node数组+链表+红黑树，例如put方法就是通过CAS原理 比较替换的方式添加。

那8下的ConcurrentHashMap如何保证线程安全的呢？其实是使用Unsafe操作+synchronized关键字；

synchronized在操作的位置进行加锁、比如我们向某个链表插入数据，那就会在Node上先同步、然后通过CAS插入。在8版本下其实也有分段的思想、但是在7中其实我们指定了桶的数量、而在8中认为是每个Node的每个位置都有一把锁。

如果我们这时去put 一个key-value

根据key计算数组下标、如果没有元素，则CAS添加；

如果有元素 那么先synchronized锁定；

加锁成功，判断元素类型，如果是链表那么就添加到链表、如果是红黑树节点那么添加到TreeNode；

添加完成，需要看是否需要转化成树结构；

• HashTable

hashTable跟HashMap最大的区别，就是HashTable是保证线程安全的，它的所有操作都进行了加锁。

HashMap底层是一个Entry数组，当发生hash冲突的时候，hashmap是采用链表的方式来解决的，在对应的数组位置存放链表的头结点。对链表而言，新加入的节点会从头结点加入。在hashmap做put操作的时候可能会造成数据丢失。现在假如A线程和B线程同时对同一个数组位置调用addEntry，两个线程会同时得到现在的头结点，然后A写入新的头结点之后，B也写入新的头结点，那B的写入操作就会覆盖A的写入操作造成A的写入操作丢失。

• TreeMap

对于treeMap，很多人很陌生、它也是基于Map接口实现的。

TreeMap是一个基于key有序的key value的散列。

map根据创建的key的排序方式、或者重写Comparator的排序方式进行排序；底层还是基于红黑树的结构实现的。

从它的继承结构可以清晰的看出来，它又实现了sorted排序方式，所以它是一个有序的。

关键词：

• 

  【打怪升级】【容器】关于Map

  关于Map接口，具体的实现有HashMap、HashTable、TreeMap等HashMap老规矩，如果我们要看源码，我们要从这么

  来源： 2023-05-25
• 

  全球微动态丨海康威视SDK - 非非门禁和报警主机产品的用户密码设置

  获取配置信息非门禁和报警主机产品，可通过该文章来获取和设置相关用户的密码，而门禁和报警主机无法使

  来源： 2023-05-25
• 

  每日资讯：游戏逆向-D3D9绘制

  做游戏逆向期间通常会用到绘制技术，比如FPS游戏逆向矩形透视，骨骼等。接下来几章内容主要介绍几种比较常

  来源： 2023-05-25
• 

  59岁水均益罕现身和富婆合影，吃大餐喝名贵酒，模样大变发福油腻

  5月25日，有媒体晒出了一则央视主持人水均益的近况照片，只见他现身友人聚会，整个人红光满面，生活潇洒惬

  来源： 2023-05-25

• 【打怪升级】【容器】关于Map

• 全球微动态丨海康威视SDK - 非非门禁和报警主机产品的用户密码设置

• 每日资讯：游戏逆向-D3D9绘制

• 59岁水均益罕现身和富婆合影，吃大餐喝名贵酒，模样大变发福油腻

• 债市日报：5月25日

• 比奥迪Q3更值得买！全新凯迪拉克GT4官图发布：颜值真能打 时讯

• 要涨价了！上海迪士尼6月23日起门票调价 世界动态

• OpenAI CEO：在重压下会考虑退出欧洲市场

• 双飞燕推出VM20蓝牙鼠标：用嘴“打字”见过没

• 新西兰航空空乘努力用中文报菜名 拍摄者：他不懂中文但努力服务 环球快报

• 大阪宝可梦中心因发放特别宝可梦卡造成人潮混乱 现场一片狼藉

• 微信向部分Windows用户推送版本更新 现已增加锁定功能

• 苹果于国外上架可定位控温旅行杯 售价高达1413元引发网友吐槽

• 前《战地》创意总监成立新工作室 称正在研发在线射击游戏

• 热头条丨linux shell编程规范和变量

• idea修改idea64.exe.vmoptions导致打不开问题

• 全球热文：突围低代码下半场，未来悬而未决

• Python集合 (set) 的增删改查及 copy()方法_焦点简讯

• 苹果iOS 17将改进锁屏界面 会使iPhone变成家居智能屏幕

• 我国研究团队成功研制出高柔韧性单晶硅太阳电池 可以像纸片一样弯曲

• 药学基本题（药学基本知识）_天天快资讯

• 惠普打印机型号有哪些？惠普打印机墨盒怎么加墨水？

• 每日机构分析：5月25日

• 环球速看：双13.3寸OLED触屏！联想YOGA Book 9i国内发布：16999元

• 长城举报比亚迪排放不达标背后：专家称如果坐实 审核标准会被动摇|天天关注

• 全球仅此一份！布加迪在迪拜推出首批住宅：每家均独一无二 当前独家

• 30万魅友参与！魅族20新配色定名“独白”：行业唯一白面板机身|天天聚看点

• 中国电影华表奖颁奖典礼太接地气：一大波明星坐路边等待 环球微头条

• 2023年安徽合肥公积金缴存基数标准调整 3月1日起执行！

• 上海SIAL食品博览会成功举办！济州品牌初露头角！

• 它来了！真正的 python 多线程

• KKRT-PSI

• 环球简讯:创新应用场景下的可视化大屏：重新定义信息展示

• 今日视点：如何证明Servlet是单例的?

• 构建高可用云原生应用，如何有效进行流量管理？

• 天天观天下！【新华500】新华500指数（989001）25日下跌0.22%

• 学堂有名堂｜30分钟午睡时间，教室里睡不着睡不好怎么办？黄浦区这所小学展开了研究

• 比亚迪高管回怼长城举报：挡别人的路 不会让自己行得更远|天天消息

• 单价6.5亿 国产大飞机快能坐了 东航C919将于近期投入实际运营 当前要闻

• 全球播报:恩怨还没完！暴雪在中国起诉网易雷火公司

• 顶配16999元 联想YOGA Air 32 4K一体机发布：13代i9+RTX 4050 一线连所有

• 1.28kg超轻身材！联想发布YOGA Air 14s 2023轻盈本 天天微资讯

• 【PC迁移与管理】上海道宁为每个用户和每个 PC 传输和迁移场景提供解决方案——PCmover_每日热讯

• 天天热推荐：Pytest - setup 和 teardown

• 全球即时看！yolov5+deepsort+slowfast复现

• 全国护肤日（国际爱肤日）：关注内外抗衰 远离皮肤疾病

• 最美小米手机！小米Civi 3亮相

• 减肥新方法！研究证实画饼真的能充饥|焦点滚动

• 新一代自拍之王！小米Civi 3前置双主摄：拍照Vlog全面兼顾 天天即时

• 称比亚迪污染物排放不达标 长城举报的是个啥：油箱成争议焦点

• 暖心!国羽苏杯夺冠黄东萍视频连线王懿律,黄鸭组合一同登台领奖

• Maven的核心解压与配置 观热点

• 当前通讯！你怎么看？统计称上海人能挣钱更能花钱 全国北京人赚的钱最耐花

• 图灵奖得主：人类大脑是生物机器 一定会有超级AI超越它 今日热议

• 焦点消息！《雨血》精神续作！国产黑暗武侠大作《影之刃零》发布首支预告

• 天天关注：黄芪加枸杞大枣泡水喝的功效与作用 枸杞大枣泡水喝的功效与作用

• SRE心里话：要求100%服务可用性就是老板的无知_环球信息

• 助数字人民币“飞入寻常百姓家”

• 国外玩家吐槽PS发布会拉跨：是不是最差的一届？-环球新资讯

• 消失70多年 一度被认为灭绝：广西发现珍稀植物巨型蜘蛛抱蛋

• 世界今日讯！AMD超算三连冠！唯一投入实用的百亿亿次

• 高性价高颜值轻薄本代表作！华硕无畏15 2023 4299元首发抢购中|世界快播

• 焦点速读：老人遛狗不牵绳还将猫踢飞 网友吵翻：这是在保护猫 你怎么看？

• 焦点资讯：5人5月用容器技术保卫蓝天

• 关于 Workstation Pro 的基础知识

• 文物 | 博物馆文物的数字化保护与管理

• 马上就要过期的食品打一折：能买吗？安全吗？

• 马斯克计划打造世界第三大AI公司 或整合特斯拉和推特

• 世界快报:强对流天气预警：今天起 多地将有8-10级雷暴大风或冰雹

• 奇丑无比的洞洞鞋凭啥风靡全球？但是 绝对别穿它上扶梯-天天热消息

• 蔚来ES6上市当天 李想立下flag：10月份理想L7月销破2万辆_前沿热点

• 天天动态:弃“元”投“AI”，传百度副总裁马杰加入创新工场，成立AIGC公司

• 实时：gPTP时钟同步（时间同步服务器）助力智能驾驶应用

• 当前消息！直播源码技术实现游戏组队功能

• 【环球财经】惠誉评级把美国长期外币发行人违约评级展望列为“负面”

• 美媒：无人机袭击克宫或为乌特别部门策划-全球热讯

• springboot~统一处理日期请求参数java.utils.Date和java.time.LocalDate_天天播报

• 【一步步开发AI运动小程序】七、进行运动计时、计数

• 36.8万起！蔚来全新ES6开卖：激光雷达、零百4.5秒 会成爆款吗

• 入门即高配！比亚迪宋Pro DM-i冠军版今日上市：纯电续航再提升

• 超110万辆特斯拉到底何时召回？时间点来了 强制单踏板再见

• 百公里油耗仅仅7.4升！依维柯聚星正式上市：13.68万元起

• 全新宝马5系发布：内饰、科技大升级 看眼后视镜就能自动变道

• 世界今亮点！在旧时光里注入新生机——湖南郴州“唤醒老屋”行动观察

• 全球快报:第六章.数据结构与算法基础(重点)

• 今日快讯：海康威视SDK - 门禁admin用户密码设置

• 当前速递！走进Linux世界，学习Linux系统的必备指南

• 最美不过二次元【AI】

• 黑人女玩家谈《Forspoken》差评如潮：种族主义者的偏见|世界观热点

• 结婚6年没孩子 查出丈夫非男性：医生科普是性反转综合征 网友刷新认知

• 焦点短讯！Windows 11打破隔阂 苹果安卓手机都能连 五大功能你用过没？

• 最高省1800元！iPhone 14 Pro系列京东618便宜了：抢券6499元起

• 当前关注：首款高通骁龙W5+智能手表！TicWatch Pro 5发布 续航45天

• 学系统集成项目管理工程师（中项）系列26_新兴信息技术-环球短讯

• tn系统的三种适用范围_tn系统 天天新要闻

• 【环球时快讯】国际金融市场早知道：5月25日

• 四大证券报精华摘要：5月25日-环球今亮点

• 索尼宣布串流掌机

• 磁带存储不死！2022年逆市增长 2028年机械硬盘将消失？

• 天天微动态丨能像纸一样弯曲！我国成功研制出高柔韧性单晶硅太阳电池