红黑树红色和黑色的来源及HashMap源码分析

哈希表：

又称为散列表，是一个使用关键码值就可以直接映射到相应位置的数据结构，在不发生哈希冲突的情况下，哈希表不需要经过任何的对关键字的比较就能一次定位到数据的位置效率非常的高，其时间复杂度是O（1）。哈希表和数组很像将数据存储在一个带有索引标识的数据空间中，当然你也可以理解它为一个数组，但是它和hasmap一样也有键值对<key,value>，利用哈希函数将key关键词转为一个int类型的整数也就是哈希值，然后对数组的长度取余，得到的结果就是就是数组的索引下标，该value值就存储在该索引值下标的数组位置中。

哈希碰撞：

哈希表维护的关系就是：index=f(key)，index就是key的哈希值（整数），也是存储位置的记录，f就是哈希函数，在理想状态下通过这个关系，哈希表每次都会得到一个不一样的哈希值，但是现实总是不理想的，有时不同的key会得到一样的哈希值时，这个情况就叫做哈希冲突也叫做哈希碰撞，由于哈希算法的原理就是将大范围的区域映射到小范围内，在空间有限的情况下再好的算法也避免不了冲突。

在java中两个不同的对象通过hashCode()计算的值可能相等,使用hashCode()比较两个对象是否相等时有可能出现true，但是使用equals()比较两个不同的对象一定为false,但是hashCode()的效率比equals()高，通过hashCode()计算出两个不同的值的情况下使用equals()一定是false,所以在比较两个对象是否相等时可以先使用hashCode()，如果计算出两个不同的值那一定是两个不同的对象，如果是得出相同的值，在使用equals()比较

链地址法：

解决冲突的方法由很多，其中一个就是链地址法，HashMap就是采用了链地址法，链地址法结构就是数组+链表，通过链表把数组的同一位置冲突元素一个个连接起来 链地址法

各个数据结构时间复杂度对比：

数组：

指定下标的查找，时间复杂度为O(1)；通过给定值进行查找，需要遍历数组，逐一比对给定关键字和数组元素，时间复杂度为O(n)，当然，对于有序数组，则可采用二分查找，插值查找，斐波那契查找等方式，可将查找复杂度提高为O(logn)；对于一般的插入删除操作，涉及到数组元素的移动，其平均复杂度也为O(n)

线性链表：

对于链表的新增，删除等操作（在找到指定操作位置后），仅需处理结点间的引用即可，时间复杂度为O(1)，而查找操作需要遍历链表逐一进行比对，复杂度为O(n)

哈希表：

相比上述几种数据结构，在哈希表中进行添加，删除，查找等操作，性能十分之高，不考虑哈希冲突的情况下，仅需一次定位即可完成，时间复杂度为O(1)

二叉树：

对一棵相对平衡的有序二叉树，对其进行插入，查找，删除等操作，平均复杂度均为O(logn)。

红黑树：

红黑树也是二叉查找树的一种，二叉查找树是一种相对简单的数据结构，当二叉查找树处于平衡状态时，保持使用二分查找法，其查询效率会很高，但是如果二叉查找树在某些特殊情况下进行了按序插入的话，就会退化成为一个链表结构，这样就丧失了二分查找法的高效查询，查询的效率就会大大减低 平衡二叉树 退化为链表

例如上图利用平衡的二叉树查找4节点，从根节点3出发，查找节点大于当前节点，根据二叉查找树的特性，左子树的节点比右子树的节点小，所以从3节点的右边出发到了5节点，查找节点比5小，然后5节点的右边出发，然后找到4节点，就完成任务，中间只比较了三次，而从链表顺序找却要5次，可以对比出保持二叉树的平衡可以大大的提升查找效率

平衡二叉树：

为了使二叉树保持平衡，我们可以对二叉树的构成限定规则：二叉树任意节点的左右子树深度差不能超过1。例如上图的退化成链表的二叉树，左子树深度为0，右子树深度为4，相差达到了4，所以是一个不平衡的二叉树。

我们在来观察这两个二叉树是否平衡，左边的二叉树3节点右子树深度是2，左子树深度是零，所以也不是一个平衡二叉树，转化成右边才平衡。 image.png

平衡二叉树的方法有两种左旋和右旋：

左旋：

左旋
右旋： 右旋

红黑树：

红黑树也是一个二叉查找树，它是23树的表现，保持黑树的绝对平衡性，牺牲了红树的平衡，也就是说红黑树牺牲了一部分的查询效率，但是却提升了插入和删除效率，在查询和修改之间做了择中，以下是构成红黑树几点：

• 1、根节点必须是黑色的

• 2、各个节点只能由黑色和红色构成

• 3、每个叶子节点（NIL）都是黑色的空节点

• 4、红色节点的子节点必须是黑色的

• 5、任意节点的左右子树到叶子节点的途中遇到的黑色节点的数量必须是一样的

红黑树

有些人会疑问，既然平衡二叉树的都已经保持平衡了为什么还要引进红黑树呢，原因就是因为平衡二叉树太注重平衡，必须让得把自己折腾成一个绝对完美的平衡二叉树，其频繁的旋转调整会使平衡树的性能大打折扣，而且其复杂度是要比红黑树要高的多的，实现起来很麻烦，而红黑树就避开了平衡二叉树的这些问题，由于红黑树在增删中不会频繁的破坏红黑树的规则，所以红黑树不必要频繁的做出调整，但是如果比起查询性能还是平衡树的比较高，红黑树在性能消耗和速度方面做出了平衡，红黑树就算是一个不完美的平衡树

红黑树为什么是红色和黑色的？红色和黑色都代表着什么意思？

红黑树是等价于一种绝对平衡的数据结构23树，不懂23树的同学自己去补课，23树规定的是一个节点最多可以存放两个数据，节点的连线是节点数据量加一，也就是存放两个数据的节点有三条腿称之为3节点，存放一个数据的节点最多有两条腿称之为二节点，如图：存放42的是二节点，它最多有两条腿，而存放17和33的是三节点，它最多有三条腿。 23树 在向23树添加数据时不可以向空节点添加，只能由一个节点如果变成了四节点（也就是节点数据有3个的时候）就会分裂，可以向下分裂成新的节点，也可以向上合并节点然后继续分裂，下图就是节点变成四节点的时候就会向下分裂， image.png 下图继续添加元素，满四节点就分裂，分裂成下图的第三个树时，这时候显然不是绝对平衡的树，然后就会向上合并，变成下图的第四颗树 image.png 继续添加元素，添加4元素的时候形成了下图的第二棵树，由于变成了四节点然后就会向下分裂又形成了一颗不平衡的树，下面其实画少了一棵不平衡的树，然后既然不平衡就得向上融合，然后就变成了下图的第三课树，显然第三棵树有节点变成了四节点然后就得向下分裂，变成了下图的第四颗树，这样就无论怎么添加，这个23树都是绝对的平衡的 image.png 红黑树其实就是一种23树的体现，在红黑树中红色代表了和他的父亲节点是融合在一起的，在23树的节点中如果是个三节点那么最大的就是另外那个数据的父亲，如果是四节点那个在中间的就是父亲，下图就是红黑树对应的23树的结构图，分别是2节点和3节点对应的红黑树的结构 image.png 如下图红黑树的这种情况就对应着四节点 image.png

下图是一个完整的23树类比红黑树的结构，左边转成红黑树就是如右边所示：

image.png

由于红黑树中有一条超级重要的定义就是：任意节点的左右子树到叶子节点的途中遇到的黑色节点的数量必须是一样的

所以红黑树保持了绝对的黑平衡，由于红黑树只是保证了黑色的绝对平衡，所以查找数据的速度比平衡二叉树要慢，但是红黑树不用平衡二叉树那样每添加或者删除数据都得耗费时间去保持平衡，所以在频繁的添加删除修改的操作的场景，红黑树是比平衡二叉树更加有效率，所以红黑树是对平衡二叉树的一种查询速度和增删改综合效率的折中优化

HashMap源码解读：

在JDK 1.7中HashMap是一个介于数组加链表的结构，用的就是哈希表的链地址法，其查询性能会跟着哈希碰撞的增加而下降，从O(1)下降到了O(n)，所以为了解决这个问题，JDK1.8中加入了数组+链表+红黑树的结构解决哈希冲突带来的性能问题提，点开JDK1.8中的HashMap看看HashMap的实现源码：

由构造函数我们知道HashMap在new出来时不会立马创建数组，而是在使用时才开始创建，其加载因子是0.75，加载因子的作用主要是为了哈希尽量不冲突，加载因子越大意味着数组的空间使用率就越大，但是相应的会发生哈希冲突的概率就越高，相反如果加载因子变小，空间使用率就会低，哈希冲突就小。如果发生了哈希冲突，会导致数组扩容或者节点转化为链表或者链表转化为红黑树，进而影响性能。所以加载因子默认值我们最好不要改

public HashMap() {
//加载因子0.75
        this.loadFactor = DEFAULT_LOAD_FACTOR;
    }

我们看这几个重要的参数，DEFAULT_LOAD_FACTOR 加载因子0.75，TREEIFY_THRESHOLD =8和MIN_TREEIFY_CAPACITY=64是链表转化成红黑树的两个阈值， 如果一个节点上的链表达到了8并且数组容量到达了64，就会触发链表转化为红黑树，但是如果链表上的节点仅仅只达到了8数组容量还没达到64，就会触发扩容，将容量扩容至原来的两倍然后重新计算各个节点的数组下标，UNTREEIFY_THRESHOLD = 6当某个节点上的红黑树节点小于等于6就会触发红黑树退化为链表，DEFAULT_INITIAL_CAPACITY =1<<4就是数组初始化长度16

//数组初始化长度16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
    static final int MAXIMUM_CAPACITY = 1 << 30;
//加载因子
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
//触发转化红黑树的链表阈值
    static final int TREEIFY_THRESHOLD = 8;
//红黑树退化链表的阈值
    static final int UNTREEIFY_THRESHOLD = 6;
//触发转化红黑树的数组阈值
    static final int MIN_TREEIFY_CAPACITY = 64;

从这两个方法，我们可以看到key是通过这个Set组织的，value是通过Collection组织的，所以key是不可重复的，value可以重复，它们都是允许null值

 public Set<K> keySet() {
        Set<K> ks = keySet;
        if (ks == null) {
            ks = new KeySet();
            keySet = ks;
        }
        return ks;
    }
public Collection<V> values() {
        Collection<V> vs = values;
        if (vs == null) {
            vs = new Values();
            values = vs;
        }
        return vs;
    }

这是内部的装载数据的节点结构，会存放k,v,hash,及转换为链表及树时的指向next，在jdk1.7直接用的是Entry<K,V>，而jdk1.8改成了Node<K,V>，改成node主要是为有必要时转成红黑树

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

这个HashMap计算下标的方法得到一个哈希值，再通过这个(n - 1) & hash计算取模，得到的值都是落到哈希桶长度为n内的

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

putVal是HashMap核心方法，
非哈希冲突：
1、当数组空时会调用resize()进行初始化，初始化容量默认是16，resize()除了初始化外还有扩容的功能
2、如果通过key的哈希值得到的数组下标在数组找到的是空值，代表数组还未发生哈希冲突则通过newNode直接往数组增加新的值，
3、如果通过key的哈希值得到的数组下标在数组找到的不是空值，则证明很有可能发生了哈希冲突
哈希冲突：
1、判断hash和key是否和集合中的重复，重复则覆盖。判断是否是红黑树，是则直接往红黑树添加节点、不是则添加到链表中
2、调用treeifyBin方法看看是否需要转为红黑树
3、最后添加完数据后判断是否超过扩容阈值而去扩容

  public V put(K key, V value) {
        return putVal(hash(key), key, value, false, 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;
//当数组空时会调用resize()进行初始化
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
//如果通过key的哈希值得到的数组下标在数组找到的p节点是空值，代表数组还未发生哈希冲突则通过newNode直接往数组增加新的值
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
//这里很有可能是发生哈希冲突了
            Node<K,V> e; K k;
//这里是put进去的值如果hash、key和p节点的相等，就判断是重复了，旧值将其覆盖
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
//判断如果p节点是树类型的，就使其插入红黑树
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
//遍历table[i]所对应的链表，直到最后一个节点的next为null或者有重复的key值
                for (int binCount = 0; ; ++binCount) {
//next为null
                    if ((e = p.next) == null) {
//往链表的最后一个节点添加新节点
                        p.next = newNode(hash, key, value, null);
//超过阈值TREEIFY_THRESHOLD -1，其实就是链表长度到达或超过了8
                        if (binCount >= TREEIFY_THRESHOLD - 1) 
//treeifyBin方法主要判断是否有必要转化成红黑树
                            treeifyBin(tab, hash);
                        break;
                    }
//put进去的值如果hash、key和链表上的值有重复值就将其覆盖
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }

//这里主要是预留给子类去实现
            if (e != null) { 
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
//这里是预留给子类去实现的方法
                afterNodeAccess(e);
                return oldValue;
            }
        }
//modCount是记录被修改的次数
        ++modCount;
//哈希桶中节点的数据超过了   加载因子*数组容量   就触发扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

这里的扩容方法也是数组的初始化方法，一般来说数组容量是初始化至16，扩容阈值初始化至12，如果扩容的话会将数组和阈值同时扩容至2倍

  final Node<K,V>[] resize() {
//获取旧的数组
        Node<K,V>[] oldTab = table;
//这里是初始化用的
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
//这个是旧的触发扩容的阈值，初始化时  0.75*16=12
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
//判断旧的数组是否是达到或超过了最大容量，是则扩展到Integer.MAX_VALUE
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
//没有超过最大容量MAXIMUM_CAPACITY，就将数组容量newCap扩大两倍、阈值threshold  （默认是12）也扩大至2倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }

        else if (oldThr > 0) 
//将旧阈值赋值给newCap 
            newCap = oldThr;
        else {            
//这里是初始化时使用的，数组容量初始为16，将newThr 阈值初始化为DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY 默认是12
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
//这里是初始化时使用的，将newThr 阈值初始化为DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY 默认是12
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
//阈值newThr 赋值给threshold 
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
//new出扩容至的新数组
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
//变量数组
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
//重新计算数组下标，并存到新数组中
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
//如果有红黑树，重新移位，将红黑树放到新的节点
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
               //...........................省略
        return newTab;
    }

这里会判断数组长度是否小于64，小于64就不走转红黑树的方法，就调用resize()方法进行扩容，大于64才进行转红黑树

final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
//这里会判断数组长度是否小于64，小于64就不走转红黑树的方法，就调用resize()方法进行扩容
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;
            do {
                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);
        }
    }

这里我们总结一下初始化、扩容、转链表、及转换成红黑树、红黑树退化的条件

• 初始化：哈希桶16，扩容阈值12，加载因子0.75
• 扩容：哈希桶超过扩容阈值时 扩容阈值和哈希桶同时扩容至两倍，链表大于等于8的情况下哈希桶小于64 哈希桶和扩容阈值同时扩容至两倍
• 转链表：发生哈希冲突时转链表
• 转红黑树：链表节点大于8并且哈希桶容量大于等于64
• 红黑树退化：链表节点小于等于6