转载--LinkedHashMap-最正确的数据结构

转载自https://segmentfault.com/a/1190000012964859

推荐一个画的较认真的一张LinkedHashMap的内存逻辑结构图。放在网上一搜，你就会发现讲LinkedHasHMap的人很多：HashMap+双向链表的组合用法，但是给出红黑树场景下双向链表结构图的作者不多。然后我们知道java8针对HashMap引入了红黑树，那么问题来来，红黑树存在下的LinkedHashMap的双向链表结构是怎样的呢？

LinkedHashMap拉链链表进化成红黑树图-1

tips:
HashMap的TreeNode继承子类LinkedHashMap的Entry节点。很有意思的设计。

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }