一 二叉树

1.1 二叉查找树(BST)

二叉查找树是一种支持数据快速查找的数据结构,结构如下图 查询的效率为O(lgn),但是在极端情况下查询的效率会退化为O(n),如下图所示,二叉查找树已经退化为了链表

1.2 红黑树

二叉查找树存在不平衡的问题,学者提出通过树节点的自动旋转和调整，让二叉树始终保持基本平衡的状态，就能保持二叉查找树的最佳查找性能了 红黑树，这是一颗会自动调整树形态的树结构，比如当二叉树处于一个不平衡状态时，红黑树就会自动左旋右旋节点以及节点变色，调整树的形态，使其保持基本的平衡状态（时间复杂度为 O（logn）），也就保证了查找效率不会明显减低。比如从 1 到 7 升序插入数据节点，如果是普通的二叉查找树则会退化成链表，但是红黑树则会不断调整树的形态，使其保持基本平衡状态，如下图所示。下面这个红黑树下查找 id=7 的所要比较的节点数为 4，依然保持二叉树不错的查找效率。 红黑树顺序插入 1~7 个节点，查找 id=7 时需要计算的节点数为 4。

1.3 红黑树概念

1.3.1 红黑树的概念

红黑树不是一个完美平衡的二叉查找树,根节点P的左子树显然比根节点的右子树高,但是左子树和右子树黑色节点的层数是相等的,也就是任意一个节点到每个叶子节点的路径都包含着相同的数量的黑节点,这种情况叫做黑色完美平衡

1.3.2 红黑树的操作

左旋转 右旋转

1.3.3 红黑树的插入

(1)插入的节点必须是红色的 (2)首先需要找到对应的位置,进行插入 (3) 动态调整红黑树 红黑树

二 JDK8中的HashMap

2.1 原理概述

2.1.1 Node属性分析

(1)hash是key对应的hash值 (2)key是存储的key (3)value是存储的value (4)next是指向下一个Node的指针

2.1.2 底层存储结构

(1)创建的时候,默认Node数组大小为16 (2)链表长度达到了9个,并且表中的全部元素超过64个时候,该链表会升级为红黑树

2.1.3 为什么需要扩容

(1)减少hash碰撞,增加查询的效率

三 HashMap的源代码

3.1 常量的含义

3.2 put()方法

(1)hash()方法 异或算法: 相同则返回0,不同就返回1 将hash值的低16位和高16位进行异或运算,得到的值作为hashCode的返回值,这样做的好处是可以将高16的数据也参与到hashCode的生成中. (2)put()方法

初始化散列表 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length;

(1) HashMap在创建的时候,只是赋值了负载因子的大小(0.75),在调用put()方法的时候再去创建散列表

索引位置无数据,直接插入 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null);

如果tab[i]对应的值是null,则生成一个Node放入到table对应的下标

插入尾节点和树化操作 Node<K,V> e; K k; // 第一种情况,首节点和插入的节点的key值一样,e更新为首节点 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 第二种情况,首节点是一颗树,进行树的插入 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { // 第三种情况,遍历链表,并且记录链表长度 //如果链表长度大于8,则树化,若是插入key在链表中不存在 //则在链表尾部插入数据,否则记录对应节点e 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; } } 如果链表中有对应的key值,更新后返回 if (e != null) { //找到旧值 V oldValue = e.value; //修改为新值 if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } 更新散列表大小和更新次数 ++modCount; //插入新元素,size自增,如果自增后的值大于扩容值,则进行自增 if (++size > threshold) resize(); afterNodeInsertion(evict); return null;

3.3 resize()扩容方法

3.3.1 hash表为什么需要扩容

减少hash表链化程度,尽可能保证hashMap中的查找时间复杂度为O(1)

3.3.2 扩容的阀值是多少

散列表长度*负载因子(0.75) 最大扩容长度是2^30次方

static final int MAXIMUM_CAPACITY = 1 << 30;

3.3.3 resize()代码分析

(1)首先确认扩容后的HashMap大小和下次的扩容阀值

//oldTab 是旧的table数组 Node<K,V>[] oldTab = table; //oldCap 是旧的table数组的长度 int oldCap = (oldTab == null) ? 0 : oldTab.length; //oldThr 是扩容之前的扩容阀值 int oldThr = threshold; //newCap是新table数组的长度,newThr下次再触发扩容的条件 int newCap, newThr = 0; //情况1 表示这是一次正常的扩容 if (oldCap > 0) { //table数组超过了最大数量,直接返回不再扩容 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } //设置下一次的扩容阀值是当前阀值的倍,新table数组是旧table数组长度的两倍 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } //这是时候oldCap = 0,但是oldThr>0,设置table数组大小等于扩容的阀值 else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; //调用new HashMap()时候oldThr=0,并且oldCap = 0,给HashMap的table长度和阀值设置默认值,分别是16和16*0.75 else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } //如果上述条件没有计算出对应的扩容值,设置为newThr为新table数组的阀值 if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); }

(2)将旧table数组中的数据放入到新table数组中 (1)任何数和1相与,都是其本身,任何数和0相与,都是0. (2)在同一个table[i]下面的链表,和数组长度相&,只会等于0或者1(因为数组长度为偶数,只有一个1,其余都是0) (3)根据2,将节点为分为高节点和低节点,高节点的下标值为当前下标值j+oldCap

threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; //如果原旧table值不是0,表示这是一次扩容行为,而不是初始化行为,进行扩容 if (oldTab != null) { //遍历oldCap的数组 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); // 情况三 散列表对应位置为链表 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; 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); //低节点链表设置到 newTab[j]位置 if (loTail != null) { loTail.next = null; newTab[j] = loHead; } //高节点链表设置到newTab[j + oldCap]位置 if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab;

3.4 get()方法

(1) 判断当前散裂表以及散列表的下标位置是否有数据,没有数据直接返回 (2) 如果首节点是要查找的节点,直接返回 (3) 判断节点类型,如果是树,则查找树,否则在链表中查找

final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; //判断当前散裂表以及散列表的下标位置是否有数据 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; }

三 JDK8和JDK7的修改

3.1 头插入修改为尾部插入

jdk7 rehash过程

void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; for (Entry<K,V> e : table) { //取出链表的第一个节点 while(null != e) { //记录下一个需要转移到新table散列表的链表节点 Entry<K,V> next = e.next; if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); //头插入对应的链表中 e.next = newTable[i]; newTable[i] = e; e = next; } } }

正常情况下的rehash过程

并发情况下的rehash 假设线程1执行到下面红色这一句后，切换到线程二： 等线程二完成后,整体变成下面的 线程1的e这个时候指向了节点3,next指向了节点7,线程1执行以下操作

先是执行 e.next = newTable[i];然后是newTable[i] = e;而下一次循环的e = next, next = e.next导致了导致了e指向了key(7),next指向了key(3) 把key(7)摘下来，放到newTable[i]的第一个，然后把e和next往下移* 环形链接出现 e.next = newTable[i] 导致 key(3).next 指向了 key(7)

3.2 红黑树自平衡

当链表的长度很长的时候,每一次查询的时候,时间复杂度为O(n),升级为红黑树后,查询的时间复杂度稳定在为O(lgn)