Java基础深究----集合框架数学原理

2022/1/3 20:12:05

编程Tag： node Java null 集合 int 节点哈希 ---- 数学原理

本文主要是介绍Java基础深究----集合框架数学原理，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

前言：本文很长很长，对原理深入至数学原理，以顺序结构讲述集合框架的设计故事，请耐心阅读顺序阅读或挑选疑惑点阅读。

目录结构太大，导致点击后索引到内容末尾，需要查看上滑即可。

你是否看到过类似的这样的一张图：

几乎所有的后台开发都会要求，熟悉/精通集合框架。

不用数了，29个类，而且JDK1.8有更多的结构，框架设计者 Josh Bloch, Neal Gafter 肯定不是靠记忆去设计集合框架。

实际上，我们应该清楚编程语言是思想的记录，

掌握集合框架，不妨去深究它背后的思想：数据结构。

一、集合溯源：数据结构

1. 关系

二、有序集合

2.有序列表 List

2.1 顺序存储方式 ArrayList

2.2 线程安全顺序存储序列 Vector

2.3 链式存储方式 LinkList

2.4 顺序存储与链式存储的本质区别

2.5 LIFO规则 ---- 栈（Stack、LinkedList）

2.6 LILO规则 ---- 队列（ArrayDeque/LinkedList）

三、无序集合与映射关系

3.1 一个散列的方法 ---- 哈希(Hash)函数

3.2 一个存储散列值的无序集合 ----HashSet

3.2.1 K-V关系的源起

3.3 HashMap的推导

3.3.1 HashMap避免Hash碰撞攻击的办法---- 红黑树

3.3.2 红黑树前提：二叉查找树（又名：二叉搜索树、二叉排序树） Binary Search Tree（BSTree or BTree）

3.3.3 红黑树前提：平衡树 Balance Tree （BT）

3.3.4 平衡二叉查找树（AVL）

3.3.5 TreeMap的实现原理----红黑树（平衡二叉B树）的原理

3.4 HashTable只是线程安全的HashMap？

3.5 _Map + Set = _Set

3.6 LinkedHashMap 双向链接哈希表

3.7 WeakHashMap 与GC相关的弱引用(Key)哈希表

3.8 IdentityHashMap 避免引用覆盖的Id哈希表

四、一些相关的问题探究(持续补充)

4.1 为什么类重写equals时，一定要重写HashCode()?

集合溯源：数据结构

理解的数据结构从一个元素开始：

什么是数据结构？ | ProcessOn免费在线作图,在线流程图,在线思维导图 |

简而言之：结构是客观存在的真理，不以人的意志而转移，因此，学习数据结构是一个发现真理掌握真理的过程，并不是一个去创造的过程，这是理解结构的方法论。研究结构就是研究元素之间二元关系的过程，当元素 is 计算机数据时，便有了数据结构的研究理论。

我们无法否认的是：元素总是存在于某个集合当中。

此处的“集合”是数学学科中的抽象集合，即当我们发现一个元素a时，{a}自己便是一个集合,并且a属于{a}恒为真。集合框架采用自顶而下的设计，对于集合的操作进行协议声明----Collection接口。

个体元素可以表示的物理状态只有：存在与不存在（恰好对应着计算机中的01数字电路符号）。

那么多个元素可以表示什么？不妨先研究最简单的模型：个体元素与个体元素，二者以某种抽象关系联系，集合中这样的关系为数学意义上的二元关系。

关系

二元关系实际上就是指两个元是否具有关系，具体什么关系与具体问题有关。

基于二元关系，我们可以枚举出元素间的关系：

一对一关系

一对多关系

多对多关系

当集合中的元素以某一粗细度去组织与观察，所有元素为一个整体关系的，为有序集合。反之为无序集合。

有序集合：List
无序集合：Set

接下来分别讨论这两种集合的性质与实现方式：

有序集合

有序列表 List

集合中元素以一种线性方案去组织，因此也可称作序列。

初中我们都学过，线性方案的基本表达式为： y = kx+c ，常数c不影响线性方案，当k等于单位1时，得到 y = x 。两个非空集合A与B间存在着对应关系f，而且对于A中的每一个元素a，B中总有唯一的一个元素b与它对应，就这种对应为从A到B的映射，即我们用物质的Collection B映射了抽象的Collection A，并以线性组织。

可以得到结论：序列=元素集合+组织关系。

我们回到Java层面，面向对象语言对于抽象一向是去实体化的，因此：抽象序列=抽象集合+组织关系。

因此，我们会在 AbstractList 类中查找到观察者（即迭代器）对组织关系的映射：

其实现方法就是寻址：连续地址+1 。

为了面向对象开发者可以精确地控制每个元素，用户可以通过整数索引(在列表中的位置)访问元素，并搜索列表中的元素，集合框架对此设计类List接口协议，并让AbstractList 实现 interface List完成上述需求。

理论证明通过，可以开始实现，计算机存储单元本就被设计为线性表结构，因此，我们要首先了解2种线性表上的连续存储方式：

顺序存储方式 ArrayList

其实现原理很直接，就是在存储单元上连续的申请物理空间，因此地址也是连续的。

这样存储有如下特点：

因为地址的连续，所以查询、修改元素会很快捷
一次迭代只需要单个引用，便可遍历整个集合
为了保持地址连续的特点，增加删除操作将牵一发而动全身

集合框架在List接口、AbstractList的基础上，采用顺序存储方式存储集合，就是ArrayList。

ArrayList（数组列表）的实现方式并不复杂，就是利用数组的特点来实现----在内存上连续申请一段空间。

因此，当我们：

ArrayList arrayList = new ArrayList();

时，实际上就是实例化ArrayList这个类，JVM会自动调用默认构造方法：

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
private static final int DEFAULT_CAPACITY = 10;
transient Object[] elementData;

public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

即指向了一个缓存在MetaSpace的空Object数组,可以将这个空Obj数组理解为元信息。那么，我们都知道数组一旦初始化，申请空间大小是要声明的，ArrayList是如何实现“动态数组”的？

所谓动态数组，就是可增(add)可减(remove)，其原理并不难，并且相同：

add:首先会调用

ensureCapacityInternal(size + 1)，这是分析当前序列长度与实际所需长度

elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA 即空实例化

（前序列长度：0，实际所需长度：1）框架会利用DEFAULT_CAPACITY申请一块新的连续内存，大小为10，让*elementData指向首地址。即默认分配大小为10的数组给实例化的ArrayList，然后：

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

直接寻址赋值，设计者是这么解释的：

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

// minCapacity is usually close to size, so this is a win:

设计者认为：大多数情况下，我们需要一块连续的内存大小是小于10的，这是一种高效的设计。

显然，设计者是做过统计的。那么我们分析下为什么申请一块默认的连续的数组会高效：

如果我们每次add的时候，都去申请一段[currentSize+1]的内存，并迁移数据到新的地址，最后将*elementData指向新内存段的首地址，利用GC去回收没有引用的旧内存段，这无疑是需要付出很多代价的。如果80%的情况，开发者都只需要小于一个DEFAULT_CAPACITY的顺序存储的序列，那么在首次add的情况下，直接开辟一段内存，会很大程度降低所需时间的期望值。

0<size <=DEFAULT_CAPACITY 即集合有元素，个数小于等于默认容量

直接寻址赋值。

size >DEFAULT_CAPACITY 即集合有元素，个数大于默认容量

这时最初申请的DEFAULT_CAPACITY已经不够用了，于是计算新的容量大小，算法为：原容量+trunc(原容量/2,0)，

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

// minCapacity is usually close to size, so this is a win:

可以发现，elementData* 指向了新的地址，这个新的地址由Arrays,copyOf(新容量)产生：

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        @SuppressWarnings("unchecked")
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

copy是一个Array的新实例，并且采用了newLength，System.arraycopy完成了数据拷贝。所以elementData*指向的是新数组的首地址。而旧数组就交给GC去完成它的工作。

remove

public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

原理也很简单，逻辑为：边界检查->计算是否尾部 ? 赋值为null，GC会根据策略回收这个存储空间 : 移除索引到尾部数据向前移动1步长

通过分析ArrayList的add与remove，可以发现所谓的“动态数组”实际上是一种面向接口编程，以较小的代价完成了需求。

ArrayList对外开启了增删改查的接口，那么可以很自然的考虑一个问题：它是线程安全的吗？

线程是否安全实际上有一个很简单的判断标准：多线程情况下，如果不用考虑这些线程在运行时环境下的调度和交替执行，都可以获得正确的结果，那么就是线程安全的，否则就不是。

那我们继续观察ArrayList，对于元素的操作，如果存在2个线程，高次数的循环执行方法，由于ArrayList的许多方法会涉及类内全局变量的改动，这就导致在这两个线程看来，对方污染了自己正在操作的对象，如果无视这个情况，那么方法的结构将会返回非预期的错误的结果，因此ArrayList不是线程安全的。

public class Main {
    static ArrayList arrayList = new ArrayList();

    public static class Test implements Runnable{

        @Override
        public void run() {
            for (int i=0;i<50;i++){
                arrayList.add(i+"abc");
            }
        }
    }

    public static void main(String[] args) {
        //4个线程同时向arrayList中添加元素
        Test test = new Test();
        Thread thread1 = new Thread(test);
        Thread thread2 = new Thread(test);
        Thread thread3 = new Thread(test);
        Thread thread4 = new Thread(test);

        thread1.start();
        thread2.start();
        thread3.start();
        thread4.start();
    } 
}

在线程先后分得时间片的情况下会产生并发修改异常：

原因：在面对并发修改时，迭代器会快速而干净地失败，而不是冒着在未来未知时间出现任意、不确定性行为的风险：所有ArrayList对象继承了父类的字段modCount，modCount代表方法执行的次数，是一个类内的全局变量，并在执行增删改查方法时自增。当前线程A分得时间片执行add方法的modCount自增，由于某种资源分配策略，其他线程分得时间片也执行add方法，modCount再次自增，等到A线程再次被唤醒，执行时，判断出预期的方法执行次数不等于modCount，立即抛出ConcurrentModifiedExceptoon:

private void checkForComodification() {
        if (this.modCount != l.modCount)
            throw new ConcurrentModificationException();
    }

我们都知道并发异常实际上都是由一个根源问题导致的：临界资源的争夺，对此，集合框架提供了一个线程安全的序列 Vector 类。

下面将介绍Vector是如何实现线程安全的。

线程安全顺序存储序列 Vector

Vector类实现了一个可增长的对象数组。与ArrayList一样，它包含可以使用整数索引访问的组件。但是，大小可以根据需要增加或缩小，以适应创建Vector后添加和删除项的情况。甚至连缺省构造方法的initialCapacity也与ArrayList的DefaultCapacity数值相同，都为10，只不过Vector在缺省实例化时便会默认申请initialCapacity大小的内存空间。

public Vector() {
        this(10);
    }

那么在ArrayList的基础上，Vector做了什么，使得自己的实例是线程安全的：

synchronized 同步

通过观察Vector的方法可以发现,所有涉及到数据污染的可能的临界资源全部加上了关键字synchronized：

public synchronized boolean add(E e) {
     //...
}
public synchronized boolean removeElement(Object obj){
     //...
}
public synchronized E set(int index, E element) {
     //...
}
public synchronized E get(int index) {
     //...
}

其实现原理简而言之是：

synchronized是通过对象内部的一个叫做监视器锁（monitor）来实现的，监视器锁本质又是依赖于底层的操作系统的Mutex Lock（互斥锁）来实现的。由于互斥锁的存在，临界资源被互斥器比标记用来保证在任一时刻，只能有一个线程访问该资源。

实际实现原理不算太复杂，这里暂时不展开叙述，我们再回到ArrayList的临界争夺问题：

public class Main {
    static ArrayList arrayList = new ArrayList();
//    static Vector vector = new Vector();
    public static class Test implements Runnable{

        @Override
        public synchronized void run() {
            for (int i=0;i<10000;i++){
                arrayList.add(i+"abc");
            }
        }
    }



    public static void main(String[] args) throws NoSuchMethodException, InterruptedException {
        //Vector vector = new Vector();
        Test test = new Test();
        Thread thread1 = new Thread(test);
        Thread thread2 = new Thread(test);
        Thread thread3 = new Thread(test);
        Thread thread4 = new Thread(test);

        long startTime = Calendar.getInstance().getTimeInMillis();
        thread1.start();
        thread2.start();
        thread3.start();
        thread4.start();

        thread1.join();
        thread2.join();
        thread3.join();
        thread4.join();

        long endTime = Calendar.getInstance().getTimeInMillis();
        System.out.println("time:"+(endTime - startTime));
        System.out.println(arrayList.size());
    } 
}

我们对Test方法run()加synchronized关键字，锁为当前实例，线程想获取实例的资源时，会对实例的所有权进行判断，如果不是自己，那么会进入等待或休眠状态，直至所有权交接给自己或被唤醒，这样就确保了临界区中的资源在自己访问的时刻只有自己在访问。这样便保证了，Test.run()方法的线程安全。要注意的是，ArrayList并不是线程安全，只是我们让外部的方法变得线程安全。

这样也是一种解决方案，但治标不治本，而Vector从序列层面实现了线程安全。

public class Main {
//    static ArrayList arrayList = new ArrayList();
    static Vector vector = new Vector();
    public static class Test implements Runnable{

        @Override
        public void run() {
            for (int i=0;i<10000;i++){
                vector.add(i+"abc");
            }
        }
    }



    public static void main(String[] args) throws NoSuchMethodException, InterruptedException {
        //Vector vector = new Vector();
        Test test = new Test();
        Thread thread1 = new Thread(test);
        Thread thread2 = new Thread(test);
        Thread thread3 = new Thread(test);
        Thread thread4 = new Thread(test);

        long startTime = Calendar.getInstance().getTimeInMillis();
        thread1.start();
        thread2.start();
        thread3.start();
        thread4.start();

        thread1.join();
        thread2.join();
        thread3.join();
        thread4.join();

        long endTime = Calendar.getInstance().getTimeInMillis();
        System.out.println("time:"+(endTime - startTime));
        System.out.println(vector.size());
   }
}

当然线程安全的代价就是更多的运行时间，这是因为类锁的获取与释放将带来很大的性能消耗。因此如果没有线程安全的需求，还是减少使用Vector。

链式存储方式 LinkList

其实现原理也很直接，就是不需要连续的存储空间，利用指针变量寻址特点实现“连续存储”。

链表中的节点

这样存储有如下特点：

物理地址并不连续，导致查询、修改不快捷
因为需要存储指针域，因此存储空间需求比实际元素数量要大
无需保持地址连续的特点，使得增加删除操作十分快捷
无需保持地址连续的特点，使得有限的存储空间条件下，存储空间利用率高

集合框架在List接口、AbstractList的基础上，采用链式存储方式存储集合，就是LinkedList 类。

LinkedList类首先将元素的基本单位定义为节点：

private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

节点中包含了三个指针变量，一个指向当前节点的数据域地址，其余的指向指针域：指向上一个节点的地址(prev)、下一个节点的地址(next)，这样设计的好处在于，基于某个节点的正向搜索与逆向搜索都可以显著减少寻址次数与比较次数，如果是单向节点，每次定位某个节点则需要线性搜索算法，因为存储地址并不连续，所以二分法寻址也无法使用，这样将显得性能低下，利用计算机的存储特性取代计算特性便可以大幅度提升性能。

由于节点的双向性质，导致节点组成的链表实际上没有固定的头部，因此LinkedList定义了一个指针first一直指向最先进入的节点或没有上一个节点的节点，last一直指向最先进入的节点或没有下一个节点的节点：

    transient int size = 0;

    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;

这样一直可知晓链表的两端，可能会想为什么申请存储空间去多记录一个尾部节点？

其实原因还是在搜索算法，如果只有一个指向头节点的指针，那么我们每次的寻址都将会是线性搜索，但是如果同时有一个指针指向尾节点，size是每次增删都会自增自减的变量，通过索引index与trunc(size/2)的比较，迭代器可以知道从头节点开始遍历的开销小还是从尾节点开始遍历的开销小，这样便使用了二分搜索法，大部分情况下极大的提升了搜索速度：

Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

对于链式序列节点的增加(源：linkFirst/linkLast/linkBefore)，分为：

尾部（大部分情况下）：通常添加到链表尾部，链表last节点的next*指向新节点，链表的last*指向新节点
首部：链表first节点的prev*指向新节点，链表的first*指向新节点
中间：新节点的next*指向index节点的next*->新节点的prev*指向index节点->index节点的next节点的prev*指向新节点->index节点的next*指向新节点（注意这个顺序是固定的，一旦破坏这个逻辑，将造成链表断链，导致节点没有被引用，被JVM的计数器算法或可达性算法GC）

对于链式序列节点的移除（源：unlink），分为：

尾部（大部分情况下）：缓存尾部节点地址，链表last*移动到last节点的prev节点，并将当前节点（倒数第二的节点）的next*指向null，尾部节点的prev*指向null，这样原先的尾部节点失去了引用，剩下的交给GC处理。
首部：缓存首部节点地址，链表first*移动到first节点的next节点，并将当前节点（正数第二的节点）的next*指向null，首部节点的next*指向null，这样原先首部节点失去了引用，剩下的交给GC处理。
中间：缓存索引节点地址，index节点的next*指向next节点的next,index节点的prev*指向prev节点，索引节点的prev*,next*指向null，剩下的交给GC处理。（注意这个顺序是固定的，一旦破坏这个逻辑，将造成链表断链）

那我们继续观察LinkedList，对于元素的操作，如果存在2个线程，高次数的循环执行方法，由于LinkedList的许多方法会涉及类内全局变量的改动，这就导致在这两个线程看来，对方污染了自己正在操作的对象(迭代器)，如果无视这个情况，那么方法的结构将会返回非预期的错误的结果，因此LinkedList不是线程安全的。

顺序存储与链式存储的本质区别

计算机中的所有矛盾其实根源只有一个：计算机的有限计算特性与有限存储特性的权衡

因此，顺序存储就是偏重利用计算机的计算特性（迭代器），达到时间成本压缩。

而链式存储就是偏重利用计算机的存储特性（寻址），达到时间成本压缩

当然，数据的存储与计算在有限时间内具有一个理论上限值时，采用何种存储方式取决于空间与时间的权重比。

对于序列，不论是顺序存储、还是链式存储本质都是面向存储器的方法。对于线程安全，采用面向接口编程的并发接口编程也可以实现本不安全的类变得线程安全。基于以上的基础，实际上序列还存在着规则上的应用：LIFO(Last-in-First-out)与LILO(Last-in-Last-out)，我们通常将规定LIFO的序列称作栈，规定LILO的序列称作队列。

LIFO规则 ---- 栈（Stack、LinkedList）

栈顶和栈底

栈的本质就是具有LIFO规则的序列，存储方式没有约束，而LIFO(Last-in-First-out)是在序列的基础上对元素的增减进行了约束：

元素的增加只能从逻辑顶部进行新增
元素的减少只能从逻辑顶部进行减少

简而言之，栈的通信接口只能有栈顶，且进栈(push)、出栈(pop)、查看栈顶(peak)都发生在栈顶。

顺序存储：利用顺序存储序列，进栈操作即当前数组扩容，利用Arrays.copyArray即可实现，出栈操作即当前数组缩容，多余元素=null后GC，依据前面提到的类，可以使用ArrayList与Vector，区别在于线程是否安全；
链式存储：利用链式存储序列，进栈操作即栈顶节点的next*指向新节点，新节点的prev*指向栈顶节点，出栈即缓存栈顶节点，栈顶节点的prev节点的next*指向null，栈顶节点的prev*指向null，返回栈顶节点。依据前面提到的类，可以使用LinkedList实现。

两种存储结构都可，

顺序栈 Stack：集合框架中，Stack类的实现继承自Vector类（线程安全顺序存储序列），因此我们可以明确Stack类是序列、以顺序结构存储、且继承自父类的方法线程安全，阅读Stack类中的方法，所有方法都是同步的，因此Stack是线程安全的。
链式栈 LinkedList：集合框架中，LinkedList不仅实现了List接口协议，还实现了Deque接口协议（支持两端元素插入和删除的线性集合），因此LinkedList支持两端元素插入和删除，满足栈的方法需求，在内部实现了栈的操作。

LILO规则 ---- 队列（ArrayDeque/LinkedList）

队列存储结构

队列的本质就是具有LILO规则的序列，存储方式没有约束，而LILO(Last-in-Last-out)是在序列的基础上对元素的增减进行了约束：

元素的增加只能从逻辑队尾进行新增
元素的减少只能从逻辑队头进行减少

简而言之，数据的通信只发生在队头（poll 出队、peek 查看队头）与队尾（offer 入队），集合框架将上述方法协议定义为Queue接口。

顺序存储：利用顺序存储序列，进队操作即当前数组扩容，利用Arrays.copyArray即可实现，出队操作即当前数组缩容，多余元素=null后GC，前面提到的顺序序列都是单端操作（尾端操作），不适合队列，因此集合框架在Queue接口的基础上，定义了Deque接口，它是一个双端队列协议，即可以快速的实现对两端的行为，实现该协议的类是ArrayDeque：

public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable
{
    transient Object[] elements; // non-private to simplify nested class access

    transient int head;

    transient int tail;

    private static final int MIN_INITIAL_CAPACITY = 8;
}

其实现结构与ArrayList相似，不同于多了两个索引：head（头部）、tail（尾部），它的作用与Linkedlist的first/last不同，//。试想一个问题，队列中元素出队后，在物理层面已经没有存储的必要了，所以我们将这个元素指向null交给JVM进行GC，在JVM回收这块存储空间前，是资源浪费的，因此，队列的另一种实现思路是：循环队列

这是一个逻辑想象图，在真正的实现时，没必要真创建这样一种结构，我们还是使用之前的线性数组。队列现在就是一个“直线”。将一个“直线”弯曲成一个“环型”，实际上是让数组产生一个模的概念，“模”实质上是计量器产生“溢出”的条件量，它的值在计量器上表示不出来，比如一个杯子，超过计量的水会溢出，但计算机计量器会溢出余数，我们把这个队列想象成一个计算机计量器，计量器的计数范围是6，那么这个队列的模就等于6，计量器上只能表示出模的余数，所以当索引值7超出了计量器的范围，计量器表示出来的将是7mol6=7%6=1，这样就实现了首尾相连的数学逻辑。（此时如果对模的概念模糊，请浏览模的百度百科补充知识，因为很有必要。）那么，对于队列的offer，新增之前对于 tail+1 mol QueueLenght == head ? 队列满了：队列未满。需要作出判断。

“循环”理论成立的事情后，再回来看ArrayDeque的设计思想：

public void addLast(E e) {
        if (e == null)
            throw new NullPointerException();
        elements[tail] = e;
        if ( (tail = (tail + 1) & (elements.length - 1)) == head)
            doubleCapacity();
    }

mol运算的本质就是位运算中的与运算，ArrayDeque直接利用与运算实现了“头尾相接”的逻辑，同时，每次的头尾重定位，都执行mol操作，使得实现了动态的“头尾相接”。即假如出队了n个，head*指向发生了变化，但head与tail在相对位置上依旧是一个队伍规模固定的队列。

假设没有出队的情况，一直入队，那么tail迟早走到容量的最大值，即队伍满了的情况，这时ArrayDeque选择了扩容的方法：

private void doubleCapacity() {
        assert head == tail;
        int p = head;
        int n = elements.length;
        int r = n - p; // number of elements to the right of p
        int newCapacity = n << 1;
        if (newCapacity < 0)
            throw new IllegalStateException("Sorry, deque too big");
        Object[] a = new Object[newCapacity];
        System.arraycopy(elements, p, a, 0, r);
        System.arraycopy(elements, 0, a, r, p);
        elements = a;
        head = 0;
        tail = n;
    }

又是使用了位运算，当前容量（ArrayDeque容量初始化为 ${2}^4$ ）的左移 1位<=> ${2}^5$ ，扩大了一倍，然后实例化了新实例，复制数据。

基本上ArrayDeque的原理探究完毕，由于head、tail的存在，多线程情况下无法做到原子性操作，因此ArrayDeque不是线程安全的。同时，ArrayDeque对于双端操作大量使用了位运算实现需求，提高了运算速度，利用循环数组提高了空间利用率，所以ArrayDeque在大部分情况下用作栈时可能比Stack快，在用作队列时可能比LinkedList快，推荐使用。

链式存储：利用链式存储序列，进栈操作即队尾节点的next*指向新节点，新节点的prev*指向队尾节点，出队即缓存队头节点，队头节点的next节点的prev*指向null，队头节点的next*指向null，返回栈顶节点。依据前面提到的类，可以使用LinkedList实现。循环链条也可以实现，但是效率不高，不推荐使用。

自此便结束了对有序集合的原理解剖。

无序集合与映射关系

无序集合是一种离散数学含义中的纯粹的集合抽象，集合具有外延公理：拥有完全相同元素的两个集合是等同的，因此set是无序且不重复的，重复没有意义。Set接口据此对无序集合进行了方法定义。

AbstractSet类提供了Set接口的框架实现，以最大限度地减少实现该接口所需的工作。
通过扩展这个类来实现集合的过程，除了这个类的子类中的所有方法和构造函数都必须遵守set接口强加的附加约束(例如，add方法不能允许向一个集合添加一个对象的多个实例)。

值得一提的是AbstractSet类在equals()方法中实现了外延公理：

//译文：将指定对象与该集合比较是否相等。如果给定的对象也是一个集合，两个集合具有相同的大小，
//并且给定集合的每个成员都包含在这个集合中，则返回true。
public boolean equals(Object o) {
    /**
}

Set接口方法协议明确后，AbstractSet抽象类对部分方法逻辑进行了抽象实现，接下来就要考虑实体该如何实现：

无法避免的是，计算机的存储单元在设计上就是线性，没有物理上的无关系存储空间，因此实现无序集合Set，我们通常在一定的存储空间内将元素散列的存储进去。

即需要：一个散列的方法+一个散列值的集合

一个散列的方法 ---- 哈希(Hash)函数

简言之，哈希函数就是将给定数据转化为固定长度的不规则值的函数。

你可以将哈希函数想象成一个搅拌器：

将物质（数据）装入到搅拌器（哈希函数）中，输出不规则的碎屑（哈希值）。

哈希值通常是一个整型（Integer）数字，但通常以16进制表示。

再深入其本质，计算机中的数据都是用二进制来管理，而哈希函数就是利用“加密”的方式“打散”这些二进制数据。

目前有多种哈希函数的算法，目前最常用的是SHA-2 (安全散列算法2，英语：Secure Hash Algorithm 2），其原理比较复杂，目前暂不展开解释，只需要知道SHA-2是利用非线性函数循环加密产生散列字符串（由于依托于非线性函数，散列并不是单射于数据，因此不属于加密），即哈希值。

其产生的哈希值有5个性质：

不论输入如何数据，哈希值都是长度相同的
相同的数据产生的哈希值一定相同；（这好比你每次都是以固定的方式去搅拌一个物体，它的碎屑一定是相同的）
不同的数据产生的哈希值低概率相同，如果用另一个集合去映射出哈希值，会出现重复的元素，这是无意义的，称作：哈希冲突（或叫做哈希碰撞），当然哈希冲突是有解决方案的，下面再讲
相似的数据产生的哈希值相差很大，即使只相差1bit
由于哈希值对于数据不是单射（复习：高等数学第一章映射），所以逆向哈希值是不可能的。

自此，我们便获取到了一个散列的方法。

在Java中，所有对象默认继承Object类，Object类中有返回哈希值的方法：

public native int hashCode()

native表明这个方法是一个内部方法，通过注释可以了解“通过将对象的内部地址（引用是在JVM栈内存上的指针变量，指向了堆内存上的实例首地址）转换为整数来实现”。不同的封装类都重写了Object中hashCode()方法，不同的对象没有重写hashCode()方法时，通常返回不同的hashcode，但是比如Integer类重写了hashCode()方法，读者可以尝试实例化不同的对象，bool比较后，如果value相同，会返回true。

一个存储散列值的无序集合 ----HashSet

K-V关系的源起

我们通过哈希函数可以得到数据的哈希值（后称hashcode），这个整型值可理解为数据散列的索引。

假设可以精准的存储元素到存储单元上，那n个元素，计算出各自的hashcode，存储到存储器上（地址==hashcode）即完成了无序集合的存储，届时只需要n个元素映射出的hashcode集合与集合引用存储，即可通过"引用-->hashcode-->元素"实现数据的访问：

这样的实现方案很直接有有效，但是，这样的存储方案太过“土豪”，某个存储单元仿佛只能给某个哈希值对应的数据使用，对内存的利用是很不友好的，我们通常用不够紧凑来形容，即低内聚。

继续观察上图可以发现，实际上只需要4个存储地址，即可保存一个完整的散列集合，即size=4。但是，显然上图的几个地址存入一个大小为4的存储段会溢出，不过既然将集合视为散列值的容器，那么因为模的原理，计算机中溢出的值将映射到该存储段中，即通过哈希值 mol 存储长度将需要的存储单元紧凑起来，高内聚起来：

简化上述的过程可以得到：

1个HashCode必然会对应1个存储单元，这样一一映射的关系称作：hash对关系（Hash-Value）：

可以通过强依赖实现:

static class Node{
        int hash;//hash由value计算，频繁计算的值，计算一次作为字段存储
        Object value;
}

自然地，存储数据与Hashcode-存储数据映射集合就称作：HashSet 哈希集合。

进一步抽象，我们将HashCode抽象为Key键，Key、Value代表元素，这样元素一一映射的关系称作：键值对关系（Key-Value）。

一个无序集合，即散列集合存在n个键值对映射，将存储键键值对映射集合的结构称作：Map 映射，那么很自然地，集合框架中，对于K-V集合的操作定义为Map接口协议，MapAbstract抽象类提供了Map接口的框架实现，以最小化实现该接口所需的工作。

因此，HashSet从节点层看，是一个{A{hash->a},B{hash->b},C{hash->c}}，元素为了实现散列关系，需要hash映射实现。而hash映射是一种特化的K-V映射，因此实现HashSet需要实现Map{hash->a,hash->b,hash->c} implements Map{k1->v1,k2->v2,k3->v3}

那么Map利用有序集合还是无序集合呢？

HashMap的推导

有序的映射关系，比如list实际上已经通过数据实现了index->data 。（有序的映射关系实际上就是将无序的映射关系有序组织起来）

那么只需要考虑无序集合的映射关系，考虑到无序的散列特性，Map需要依靠散列函数，根据上述的hash函数，可得：Map{hash1->{k1->v1},hash2->{k2->v2}}:

static class Node{
    int hash;//频繁计算的值，计算一次作为字段存储
    KVNode kvNode;

    static class KVNode<K,V>{
        K key;
        V value;
    }
}

这里的hash可由Key计算：

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;//频繁计算的值，计算一次作为字段存储
        final K key;
        V value;
}

这样的无序的键值对集合称之为：HashMap

接口已定义、抽象类已实现抽象行为，开始实体实现：

首先，要实现K-V映射，HashMap将其定义为Node<K,V>:

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

先只关心K与V，后续解释为什么还有next。

映射存储在集合中，HashMap为了使存储单元物理地紧凑，使用的依旧是数组：

/* ---------------- 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<K,V>[] table;

    /**
     * Holds cached entrySet(). Note that AbstractMap fields are used
     * for keySet() and values().
     */
    transient Set<Map.Entry<K,V>> entrySet;

    /**
     * The number of key-value mappings contained in this map.
     */
    transient int size;

那么实例化一个HashMap即实例化了一个Node<K,V>的数组，这是最基础的理解，进一步观察构造方法：

public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

发现，缺省的构造方法只设定啦一个默认负载因子，这个暂且按下不表，再观察增减方法窥探HashMap设计的精妙之处：

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

调用了内部的putVal方法，并且可以发现hash的值，集合框架已经通过key计算了，因此不需要开发者再次计算hashcode。putVal方法比较长，逐句分析：

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

}

当table为空时，通过resize()计算新的容量，默认16，2的幂次，与ArrayDeque扩容方式类似不再赘述。


final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        ...
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        ...

}

n是数组的长度即容器的容量，与操作( m&(n-1) / (n-1)&m )是mol的位操作表现（m%n），因此这段代码实际上就是：


final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        ...
        if ((p = tab[i = hash % (n-1)]) == null)
            tab[i] = newNode(hash, key, value, null);
        ...

}

即将hashcode映射到容器中，判断数组索引为null时，Node<K,V>存入。

然后就是else，这代表着容器既不为空，且容器索引节点也不为空的情况，即出现了哈希冲突的情况，集合框架是这么处理的：

单节点转换为单链表后可以理解为数组与链表的组合：

这也解释了为什么Node<K,V>中有next这个字段，就是为了解决哈希冲突。

static final int TREEIFY_THRESHOLD = 8;

那么，为什么超过8个节点，就会执行treeifyBin（树化Bin）方法，这是为了避免哈希冲突（碰撞）攻击行为：试想某黑客恶意构造了哈希值全部相同的数据组攻击服务器，那么HashMap将失去哈希表的索引优势，退化为单链表，拖慢服务器处理速度，最终演变为超时拒绝服务的状态。

treeifyBin执行的过程就是将单链表转换为红黑树的过程，其结果大致为：

HashMap避免Hash碰撞攻击的办法---- 红黑树

红黑树是一个自平衡的二叉树结构，它有两个知识前提：二叉查找树和平衡二叉树

红黑树前提：二叉查找树（又名：二叉搜索树、二叉排序树） Binary Search Tree（BSTree or BTree）

二叉查找树是一种树形数据结构。其特点为每个节点大于左子树所有节点，小于右子树所有节点。

根据其规则归属，新增节点的逻辑为：

    public void addNode(int key,Object value){
        root = addNode(root,key,value);
    }
    public Node addNode(Node root,int key,Object value){
        if (root == null){
            //初始化树
            return new Node(key,value);
        }

        //新节点的key大于当前节点
        if(key > root.key){
            //如果当前树的根节点右子树为null，则新节点作为根的右子节点
            if(root.rightChild == null){
                root.rightChild = new Node(key,value);
            }else {
                //否则进入子树比较
                root.rightChild = addNode(root.rightChild,key,value);
            }
        }

        //新节点的key小于等于当前节点
        if(key <= root.key){
            //如果当前树的根节点左子树为null，则新节点作为根的左子节点
            if(root.leftChild == null){
                root.leftChild = new Node(key,value);
            }else {
                //否则进入子树比较
                root.leftChild = addNode(root.leftChild,key,value);
            }
        }
        return root;
    }

很多人在实现树结构的时候往往会陷入一个误区，一定要确定树的存储结构，数组？List？实际上要清楚，树是数据结构，是数据组织的方式，并不是存储结构，存储单元本身完全够存储树的节点，我们要实现的是组织方式，而这个方式通常通过索引相链，即Node类中的Node类型的父、左子、右子。Node类中组成字段是Node类，这本身就是一种递归组织形式。因此解决非线形问题，递归的思想很重要。

查找逻辑就是：与节点比较key的大小，如果小于，那么节点可能在当前树的左子树中，移动到左子树继续比较；如果大于，那么节点可能在当前树的右子树中，移动到右子树继续比较，知道等于或没有该key：

删除的逻辑较复杂，但核心在于：破坏心操作下保持查找树的特点（左小右大），否则查找树结构将被破坏。

还需要注意的是，删除并不意味着回收存储单元，实际上在Java中，删除的体现是：去除所有引用，直至不可达

因此，移除树节点，实际上就是在递归中，重新组织父子关系：

以上图举例：

Tree.remove(13) ->引用指向待删除节点,MinNode = Min(引用), 引用.key = MinNode.key-> removeMin(MinNode)

Tree.remove(13) ->引用指向待删除节点,MaxNode = Max(引用), 引用.key = MaxNode.key-> removeMax(MaxNode)

分析完了二叉搜索树的操作，那么回到现实，二叉查找树有什么作用？

一个集合以二叉搜索树的方式组织，利用插入时的1次比较，减少后续的链式的线性搜索比较次数，是一种搜索性能优于链式序列的方式。

红黑树前提：平衡树 Balance Tree （BT）

二叉查找树是一种树形数据结构。其特点为任何节点的子树高度之差的绝对值不超过1。

换言之，树是左右两边是无限追求对称的，如果结果完全对称则称为：完美平衡树。

再回想一下二叉搜索树，假如有集合{1,2,3,4,5,6},当以{123456}插入节点和以{325146}插入：

当我们搜索节点6时，左图搜索树需要比较6次，右图搜索树只需要比较3次。这是因为左图搜索树由于树的枝干不够“平衡”，导致搜索树实际上退化为链表。“平衡”的树，对于搜索一个节点的情况，并不是完全占优，而是其缩小了最好情况与最坏情况的区间大小，使得整体期望表现优于序列，尤其在具有时间概念的系统中（越旧的数据越小概率被访问）。

所以二叉查找树引入平衡树的特性，便产生了平衡二叉查找树 Balanced Binary Tree （通常简称为AVL，是2位平衡二叉查找树作者的姓名组合）

平衡二叉查找树（AVL）

平衡二叉查找树是一种树形数据结构，其特点为:

任何节点的子树高度之差的绝对值不超过1。(平衡树)
每个节点大于左子树所有节点，小于右子树所有节点（查找树）

定义左子树与右子树的允许的高度差为该AVL的平衡因子，

高度差公式为：Depth(节点左子树)-Depth(节点右子树)

所以特点还可以表示为：

平衡因子绝对值不超过1。(平衡树)
每个节点大于左子树所有节点，小于右子树所有节点（查找树）

定义AVL就是在查找树的定义中引入深度(depth)的概念:

static class Node{
        public int key;//元素Object Element,这里特指key值
        public Object value;

        public int depth =0;//当前节点为root的树的深度 = Max(leftDepth,rightDepth)
        public int leftDepth =0;//当前节点为root的树的左深度
        public int rightDepth =0;//当前节点为root的树的右深度
        public Node parent = null;//父节点
        public Node leftChild = null;//左子节点
        public Node rightChild = null;//右子节点
}

引入深度概念后，就需要考虑什么时候失衡，如何定义失衡？

在分析整个树的深度时，实际上又是一个递归问题：设n层高的树深度是n,那么n=n-1层高的树深度+1,...,2层高的树深度是1层高的树的深度+1，1层高的树的深度=1。由此递归，可得到当前节点的深度。每次进行破坏性操作（增删）时，进行一次深度分析，获取最新的子树深度，并比较左右子树深度差，当 Math.abs(leftDepth-rightDepth) > 平衡因子时，视为以当前节点为root的树已失衡（称作最小失衡树），并且这也意味着以最小失衡树为子树的树也已经失衡。

失衡后如何调整到平衡状态？

回到平衡状态就是让最小失衡树左右子树高度差<=平衡因子，即重新组织失衡的树的节点，如上图，失衡的{5,6,7}实际上有着更好的组织方式：

它看起来像这样的过程：

我们将失衡树转变为平衡树的过程叫做旋转，当rightDepth>>leftDepth，我们需要的就是左旋(降低右子树的深度)，当leftDepth>>rightDepth需要的就是右旋（降低左子树的深度）。

旋转的实现方式为：

左旋

设：最小失衡树的根为UBroot,右子树的根节点为UBRSroot

已知：UBroot.key < UBRSroot.key

故，UBroot可作为UBRSroot的左子树。

此时，UBRSroot的子树有两种情况：（1）存在一个左子树（2）存在一个右子树

不论UBRSroot属于情况，

replacement = Min(UBRSroot) 找到UBRSroot树中最小的节点作为更换零件；

damagedNode = UBroot,引用“损坏”零件；

damagedNode.parent.Existingchild = replacement 损坏零件的父节点指向更换零件，损坏零件一定比更换零件小，所以作为更换零件的左子节点，即可完成平衡化的过程。

理论成立，实现：

public Node rotateToLeft(Node root){
        System.out.println("needToRotateToLeft:"+root.toString());
        Node damagedNode = root;
        //查找不平衡枝干的最小值并取下作为替换零件
        Node replacement = findMin(root.rightChild);
        removeMin(root.rightChild);
        //换上替换零件
        if (root.parent != null){
            damagedNode.parent.rightChild = replacement;
        }

        damagedNode.rightChild.parent = replacement;
        replacement.parent = damagedNode.parent;
        replacement.rightChild = damagedNode.rightChild;
        damagedNode.rightChild = null;
        //损坏零件作为替换零件的左子
        damagedNode.parent = replacement;
        replacement.leftChild = damagedNode;
        //损坏零件深度调整
        damagedNode.rightDepth = 0;
        damagedNode.depth = damagedNode.leftDepth;
        //替换零件深度调整
        replacement.leftDepth = replacement.leftChild.depth+1;
        replacement.rightDepth = replacement.rightChild.depth+1;
        replacement.depth = calculateDepth(replacement);
        return replacement;
    }

右旋

设：最小失衡树的根为UBroot,左子树的根节点为UBLSroot

已知：UBroot.key > UBLSroot.key

故，UBroot可作为UBLSroot的右子树。

此时，UBRSroot的子树有两种情况：（1）存在一个左子树（2）存在一个右子树

不论UBLSroot属于情况，

replacement = Min(UBLSroot) 找到UBLSroot树中最大的节点作为更换零件；

damagedNode = UBroot,引用“损坏”零件；

damagedNode.parent.Existingchild = replacement 损坏零件的父节点指向更换零件，损坏零件一定比更换零件大，所以作为更换零件的右子节点，即可完成平衡化的过程。

理论成立，实现：

public Node rotateToRight(Node root){
        System.out.println("needToRotateToRight:"+root.toString());
        Node damagedNode = root;
        //查找不平衡枝干的最大值并取下作为替换零件
        Node replacement = findMax(root.leftChild);
        removeMax(root.leftChild);
        //换上替换零件
        if (root.parent != null){
            damagedNode.parent.leftChild = replacement;
        }
        replacement.parent = damagedNode.parent;
        damagedNode.leftChild = null;
        //损坏零件作为替换零件的左子
        damagedNode.parent = replacement;
        replacement.rightChild = damagedNode;
        //损坏零件深度调整
        damagedNode.leftDepth = 0;
        damagedNode.depth = damagedNode.rightDepth;
        //替换零件深度调整
        replacement.leftDepth = replacement.leftChild.depth+1;
        replacement.rightDepth = replacement.rightChild.depth+1;
        replacement.depth = calculateDepth(replacement);
        return replacement;
    }

这样便实现了在对AVL在破坏性操作下保持两大特性的动态平衡过程，实际上就是查找树删除操作的基础上的改进，还可以通过调整平衡因子控制二叉树平衡的频率。

TreeMap的实现原理----红黑树（平衡二叉B树）的原理

红黑树是一种树形数据结构，其特点为:

是一种特化的平衡二叉查找树（AVL）
规则1:节点非红即黑，root节点初始为黑，所有叶子结点都为黑；
规则2:不出现同一枝干连续的两个红节点(就是父子不能都是红色)；
规则3:任意节点到其叶子节点的路径上黑节点数量相同（就是说比如节点3，有3个叶子结点，然后以结点3为开始路径->某个叶子结点为终点路径，路径上的黑结点数量相同）：

为什么要用红黑树？

回到AVL，AVL利用平衡树的特性，通过变化的代价减少了查询的代价。我们可得：

查询代价的减少 ->通过一定程度树形变化代价

那么，这个模式进一步优化，就需要从减少平衡所需的变化次数，红黑树便应运而生。当节点为键值对时，便为集合框架中的TreeMap。

红黑树如何减少了平衡过程中的次数？

如果将平衡，与失衡定义为两个完全相反的矢量，那么失衡所代表的就是不断的远离平衡，当发觉最小失衡树，AVL的做法是旋转，我们实验几次平衡调整就会发现：

AVL的旋转只是向平衡踏出了一小步，树并没有达到它最理想的组织结构，即没有达到完美平衡树，也就是说AVL的旋转带来的平衡调整不完全，比如上图，完美平衡树应该是这样：

相比于非完美平衡树，完美平衡树具有在最坏最好情况下，代价最小的特点。

因此，红黑树的作为特化的AVL，每次的调整都向着完美平衡树最大程度逼近。

红黑树如何自平衡？

我们用这个红黑树（例：完美平衡树）被破坏性操作（增删）时如何自平衡：

新增一个节点（key=6）,根据平衡树的特性，6将安排在：

根据红黑树的规则1，叶子节点需要为空节点（java中体现为左右子树引用指向null）：

此时可以发现，节点4到它的三个叶子结点的路径包含的黑结点个数分别为：1，2，2（左->右），这样违背了规则3，即以4为root的树失衡了，且包含这个树为子树的树也失衡了，即AVL中提到的最小失衡树也可以定义在此，以4为root的树为整个树的最小失衡树。

判断的逻辑为：深度遍历树（之前提到过树是一种特殊的图），到达每个叶子结点时计算黑节点个数：

public int countBlackPoint(LinkedList<Node> list){
  int count = 0;
  for (Node node:list){
    if(!node.redFlag){
      count++;
    }
  }
  return count;
}
//检查以node为root的树是否符合Rule3(深度优先遍历：迭代法实现)
public boolean checkRule3(Node node){
  //实例化一个stack，用于回溯
  //实例化一个LinkedList<Node> CurrentPath,存储路径

  if (root == null){
    return true;
  }

  stack.push(node);

  int regularBlackPoint = 0;//理论黑节点个数

  while(!stack.isEmpty()){
    node = stack.pop;
    currentPath.add(node);

    if(node.right!=null){//right in first, then right out later
      stack.push(node.right);
    };
    if(node.left!=null){
      stack.push(node.left);
    }else{//leaf node 
      if (regularBlackPoint == 0){//书写理论
        regularBlackPoint = countBlackPoint(CurrentPath);
      }else{//比较一致性
        if(countBlackPoint(currentPath) != regularBlackPoint){//不一致
          return false;
        }else{//一致，初始化计数器
          System.out.printIn(currentPath.toString);
          currentPath.removeLast();//回溯
        }
      }
    } 
  }
  return true;
}

当红黑树违背规则3时该如何调整平衡？

其实很简单，以节点4为root为当前结点，可以做的就是子节点变对立色,让规则3通过：

满足规则3的同时，发现当前的树违背了规则2。规则2的判断十分简单：

if (node.redFlag&&node.child.redFlag),即违背了规则2。

违背了规则2时如何调整？

显然，当前节点变对立色即可。

此时以节点4为root的树，满了所有规则。

回溯到节点3为root(Tree[3])，判断规则3未满足，子节点变对立色即可（对立节点）：

回溯到整个树的root节点，满足所有规则，红黑平衡结束。

总结可以发现，不论违背规则2或是规则3，变色规则只需要遵循：

平衡规则2：当前节点变对立色即可，
平衡规则3：子节点变对立色即可（定位子节点：如果子节点存在NewNode，NewNode变色；如果子节点不存在NewNode,判断当前节点Key与NewKey的大小，变色NewKey对立子树的子节点）

以上是变色规则，如果新增的节点破坏了AVL平衡，还需要AVL的平衡：旋转

在红黑树的平衡中，需要先确保AVL的平衡性，因此

红黑树平衡：AVL平衡->变色平衡

自此结束了红黑树的解释，并且集合框架中，红黑树实现也不是线程安全的;

->自此结束了HashMap解决Hash碰撞的解释;

->自此结束了HashMap的推导

集合框架中对于红黑树与链表的实现不是线程安全的，因此HashMap也不是线程安全的。

Q:那么集合框架中有线程安全的键值对吗？

Q:有，比如HashTbale。

HashTable只是线程安全的HashMap？

并不单纯是。

显然我们常说的哈希表，直译自HashTable，但目前也可以指HashMap，两者的本质都是键值对（K-V），但多处设计不同：

HashTable所有涉及临界资源的方法都添加了synchronized关键字，这使得HashTable是线程安全的；HashMap不是线程安全的，但却是一种合理的设计，因为日常使用当中，大部分时间是单线程操作的。
HashTable因为其性能低下，很少被使用，使用键值对时，HashMap更多。原因在于HashTable中大量的synchronized需要更多的资源用于类锁。
扩容方式不同：HashTable采用的是初始化11容量，并在溢出前扩从为一个更大的素数或质数（设计思路主均匀分散哈希值）。HashMap采用初始化2的4次方容量，固定容量为2次幂。溢出前幂次+1，并且过程利用位运算实现（设计思路主多利用位运算提高效率）。
计算hash code的原理不同：通过Key获取hashcode。HashTable直接利用除法计算内聚后的数组位置，除法是很耗时的运算；HashMap利用其容量为2次幂，通过位运算计算内聚后的数据位置，效率更高。HashMap这样的设计导致位操作大部分情况下只能利用hashcode的低位进行位运算，增大了哈希冲突的概率，但HashMap通过对hashcode无符号右移16位，使得可利用的位置更加分散，抵消了设计上的增大哈希冲突风险。
在哈希冲突的情况下，HashTable无法防御哈希冲突攻击，因为没有红黑树的支持。

综上所述，在实际应用过程中，推荐HashMap。如果有线程安全的需求，并发框架中提供了性能更好的并发编程的HashMap----ConcurrentHashMap。由于本篇幅主要探究集合框架原理，这个类将在并发框架详解。下面看一个新的需求

由于散列特性，迭代HashMap的顺序与存入的顺序是几乎不可能相同的。

如果在保留无序集合的散列特性的同时，还想保留迭代的顺序，就需要对原本的节点进行改造，HashMap中的节点是这样子的：

由hash与next*,为数组与单链表的组合结构，为了持久化迭代的顺序，可以在此基础上，增加after*，引用迭代顺序中的下一个节点：

在集合框架中，设计者考虑到了开发者需要免于HashMap(和Hashtable)提供的不确定的、混乱的排序，提供了LinkedHashMap，为开发者提供一个入口数据的持久索引副本。

_Map + Set = _Set

上述的知识点，解决了HashSet的实现前提。

实现HashSet只需在内部实例化一个HashMap，且Set元素作为Key，由Key计算hashcode，Value填入默认值（Map的K,V通常不可为null），即可实现HashSet。_Set由于Set接口协议，只允许存取，无法操作内部散列映射。

因此，如果只需要散列存储，使用_Set；需要只需要映射关系，使用_Map。

在集合框架中类似的关系还有

「TreeSet=TreeMap+Set」TreeMap在上面已解析过。

「LinkedHashSet=LinkedHashMap+Set」LinkedHashMap将在下文继续解析。

实际上_Set的操作相同，区别在于节点内部映射管理的效率。

LinkedHashMap 双向链接哈希表

LinkedHashMap的节点与上述的设计思路相同：

    //LinkedHashMap.Node
    static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }

通过Entry（Node）可得知，LinkedHashMap实际上就是HashMap.Node与LinkedList.Node的组合。在散列存入节点的同时，利用before*、after*索引存入的顺序：

这样使得我们在正向迭代LinkedHashMap，只需要从表头的after开始，逆向从表头的before开始。

值得一提的是accessOrder这个字段：

//这个链接哈希映射的迭代排序方法:访问顺序为true，插入顺序为false。
final boolean accessOrder;

这是一个默认为true，未初始化的字段，当访问顺序为true时，执行访问操作（如put、get等索引操作）时，会在操作结束后，将该节点移动至链表尾部。当访问顺序为false时，则默认双链表操作。

由于LinkedHashMap是HashMap与LinkedList的组合，并且操作是非原子性操作，所以LinkedHashMap不是线程安全的。

自此基本上结束了无序集合的解释。下面介绍2个少用的集合框架类：

WeakHashMap 与GC相关的弱引用(Key)哈希表

这里简单介绍JVM的4种引用：

1. 强引用

如果一个对象具有强引用，它就不会被垃圾回收器回收。即使当前内存空间不足，JVM也不会回收它，而是抛出 OutOfMemoryError 错误，使程序异常终止。比如String str = "hello"这时候str就是一个强引用。

2. 软引用

内存足够的时候，软引用对象不会被回收，只有在内存不足时，系统则会回收软引用对象，如果回收了软引用对象之后仍然没有足够的内存，才会抛出内存溢出异常。

3. 弱引用

如果一个对象具有弱引用，在垃圾回收时候，一旦发现弱引用对象，无论当前内存空间是否充足，都会将弱引用回收。

4. 虚引用

如果一个对象具有虚引用，就相当于没有引用，在任何时候都有可能被回收。使用虚引用的目的就是为了得知对象被GC的时机，所以可以利用虚引用来进行销毁前的一些操作，比如说资源释放等。

WeakHashMap中的Key就是基于弱引用的，因此，一旦发现弱引用对象，无论当前内存空间是否充足，都会将弱引用回收。

当使用 WeakHashMap 时，即使没有删除任何元素，它的尺寸、get方法也可能不一样。

这样对程序而言产生信息不对称的HashMap有什么应用？

如果键值只需要缓存，弱引用就是十分合适的方法：

private static WeakHashMap<Object,Object> cacheMap = new WeakHashMap<>();
    public void cache(Object key,Object value){
        cacheMap.put(key,value);
    }
    public void releaseStorage(){
        System.gc();
    }
    public static void main(String[] args) {
        Object KeyOfBigDate = new Object();
        Object bigData = new Object();
        //需要缓存一下bigData
        cacheMap.put(KeyOfBigDate,bigData);
        //缓存后操作
        //...
        //缓存结束，希望主动释放该资源
        KeyOfBigDate = null;//key无引用，value变为弱引用
        //主动回收value
        System.gc();
    }

这样便实现了简易的数据缓存机制。

IdentityHashMap 避免引用覆盖的Id哈希表

在HashMap解析、以及问题“为什么重写equals时，一定要重写HashCode()”,都描述了put的过程，当同义对象存入后，会发生同义对象的引用覆盖HashMap中的对应对象的引用，如果数据集有对引用分组的需求，就可以使用IdentityHashMap。

为什么IdentityHashMap可以实现上述需求？

除了一些初始化、组织数据的方式不同，整体上还是保留着HashMap特征，不同的点在于：同义判断时，HashMap利用的是对象内部的equals方法判断，而IdentityHashMap使用的是 == 引用地址判断，这就实现了堆内存不同引用的存入。

一些相关的问题探究(持续补充)

为什么类重写equals时，一定要重写HashCode()?

为了解决这个问题，我们需要回顾一下HashMap的put()过程：

调用对象的HashCode()方法获取hashcode

->hashcode mol 容量计算出hashcode映射在数组上的索引值 index

->判断是否哈希冲突，如果没有，直接实例化一个单链表节点Node，并存入数组对应的index;如果冲突，再进行同义判断，判断是否已存入过同义的节点，这需要调用对象的equals()方法，如果没有同义节点，则将Node链接在单链尾部或存入红黑树，如果是同义节点，则新的引用覆盖旧的引用。

(红黑树已在HashMap详解过，这里对问题的讨论影响不大，不讲)

然后我们讨论4个情况：

没有重写HashCode()，equals()

所有对象继承Object类，在计算hashcode时应用的是Object中默认的HashCode()方法（利用引用指向的地址计算出hashcode），默认的equals()方法(比较引用指向的地址是否相同)。在此情况下，实例化两个同类对象，所有字段均相同，逻辑上两个对象属于同义，但hashcode不同（因为实例在堆内存首地址不同），这就导致同义对象都可以插入HashMap。根据集合的外延公理，这是浪费资源且无意义的操作，HashMap不应该出现重复的同义节点。

重写了HashCode()，没有重写equals()

所有对象继承Object类，在计算hashcode时根据重写的HashCode()（实现同义对象hashcode相同），默认的equals()方法(比较引用指向的地址是否相同)。在此情况下，实例化两个同类对象，所有字段均相同，逻辑上两个对象属于同义，hashcode相同，hashcode相同导致了哈希冲突，后存入的节点判断同义性时，因为equals返回false，判断为非同义，将Node链接在单链尾部或存入红黑树。根据集合的外延公理，这是浪费资源且无意义的操作，HashMap不应该出现重复的同义节点。

重写了equals()，没有重写HashCode()

所有对象继承Object类，在计算hashcode时应用的是Object中默认的HashCode()方法（利用引用指向的地址计算出hashcode），重写的equals()方法（实现同义对象返回true）。在此情况下，实例化两个同类对象，所有字段均相同，逻辑上两个对象属于同义，但hashcode不同（因为实例在堆内存首地址不同），这就导致同义对象都可以插入HashMap。根据集合的外延公理，这是浪费资源且无意义的操作，HashMap不应该出现重复的同义节点。

重写了HashCode()，equals()

所有对象继承Object类，在计算hashcode时根据重写的HashCode()（实现同义对象hashcode相同），重写的equals()方法（实现同义对象返回true）。在此情况下，实例化两个同类对象，所有字段均相同，逻辑上两个对象属于同义，hashcode相同，hashcode相同导致了哈希冲突，后存入的节点判断同义性时，因为equals返回true，判断为同义，新的引用覆盖旧的引用。避免了浪费资源且无意义的操作。

综上所述，只有类同时重写HashCode()，equals()才可以确保对象的同义性。

因此为了保证类在任何集合中的同义性务必将HashCode()，equals()同时实现。

阅读自此，结束了Java集合框架的分析，如果有任何疑论，请不吝评论。

这篇关于Java基础深究----集合框架数学原理的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！