jdk1.7
数据结构是数组+链表的形式。数组存储每个链表的头结点。
首先来看储存的节点
Entry
static class Entry<K,V> implements Map.Entry<K,V> {final K key;V value;Entry<K,V> next;int hash;Entry(int h, K k, V v, Entry<K,V> n) {value = v;next = n;key = k;hash = h;}。。。}
Entry 是一个很简单的结构，就是存储当前的 key、value、hash 值，以及持有下一个节点的引用。
构造+成员变量
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 Entry<?,?>[] EMPTY_TABLE = {};//默认空数组transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;//存储链表的数组,默认为空数组transient int size;//容量大小int threshold;//判断扩容的临界值final float loadFactor;//用来计算临界值的数字transient int modCount;//该 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;//指定临界值大小，就是初始容量值。threshold = initialCapacity;init();}public HashMap(int initialCapacity) {//可以自定义初始容量大小this(initialCapacity, DEFAULT_LOAD_FACTOR);}public HashMap() {//使用默认的初始大小，默认的负载因子this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);}public HashMap(Map<? extends K, ? extends V> m) {this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);//初始化变量后，进行填充数组inflateTable(threshold);putAllForCreate(m);}void init() {//用来给 LinkedHashMap 作扩展的函数。}
HashMap 有四个构造方法。首先给 threshold 和 loadFactor 赋值。如果我们使用无参构造，那就是默认值。如果传入的有其他 Map，给 threshold 和 loadFactor赋值完后，进行初始化数组，并填充数据。
先调用 inflateTable 后调用 putAllForCreate 。
inflateTable、putAllForCreate
private void inflateTable(int toSize) {// Find a power of 2 >= toSize//根据 toSize 计算出刚好大于等于 toSize 的 2的幂的数。具体怎么计算的可以看参考文献中的引用 HashMap中的1.7中的roundUpToPowerOf2()和1.8中的tableSizeFor()int capacity = roundUpToPowerOf2(toSize);//根据容量大小，重新计算临界值threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);//创建数组table = new Entry[capacity];//是否要重新计算 Hash 因子hashSeed，需要再 JVM 里面进行配置。这里不必细看。initHashSeedAsNeeded(capacity);}final boolean initHashSeedAsNeeded(int capacity) {// hashSeed降低hash碰撞的hash种子，初始值为0boolean currentAltHashing = hashSeed != 0;//ALTERNATIVE_HASHING_THRESHOLD： 当map的capacity容量大于这个值的时候并满足其他条件时候进行重新hashboolean useAltHashing = sun.misc.VM.isBooted() && (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);//TODO 异或操作，二者满足一个条件即可rehashboolean switching = currentAltHashing ^ useAltHashing;if (switching) {// 更新hashseed的值hashSeed = useAltHashing ? sun.misc.Hashing.randomHashSeed(this) : 0;}return switching;}----------------------------------------------------------------------------------------------------------------private void putAllForCreate(Map<? extends K, ? extends V> m) {for (Map.Entry<? extends K, ? extends V> e : m.entrySet())putForCreate(e.getKey(), e.getValue());}private void putForCreate(K key, V value) {//首先计算 hash 值，如果key 为 null，那么 hash 值也为 null。int hash = null == key ? 0 : hash(key);//根据 hash 值和数组的长度计算出这个节点要存放的位置的索引int i = indexFor(hash, table.length);//判断当前索引上是否已经有节点存在，如果有并且存在相同的 hash 值，key 值也一样。那么直接将旧值替换为新值，并结束流程。for (Entry<K,V> e = table[i]; e != null; e = e.next) {Object k;if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k)))) {e.value = value;return;}}//如果不存在，创建新节点createEntry(hash, key, value, i);}
计算容量值roundUpToPowerOf2 的具体分析可以看： HashMap中的1.7中的roundUpToPowerOf2()和1.8中的tableSizeFor()
从上面代码也可知道，首次创建HashMap 的时候，容量值是 2 的幂次方。
填充数据的过程中：计算 Hash，计算对应位置的下标，创建节点。
hash、indexFor、createEntry
final int hash(Object k) {int h = hashSeed;//hashSeed 默认为 0，所以下面这个判断逻辑不会走。if (0 != h && k instanceof String) {return sun.misc.Hashing.stringHash32((String) k);}//0^任何数 都等于它本身，所以这里 h = k.hashCode();h ^= k.hashCode();//这里进行了 2 次 计算，其目的就是让 hash 中的 32 位数更加分散，让更多的数值能够进行 indexFor 的计算。h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);}static int indexFor(int h, int length) {// 与运算，确保计算出来的 索引值不会大于 length-1。return h & (length-1);}//创建新的节点void createEntry(int hash, K key, V value, int bucketIndex) {//先取出当前索引上的节点，有可能为 null。Entry<K,V> e = table[bucketIndex];//然后创建新的节点赋值到当前索引上。原先的节点被赋值到新节点的 next 上。table[bucketIndex] = new Entry<>(hash, key, value, e);size++;}
在 putForCreate 计算 hash 值的时候，我们可以看到 key 为 null 的时候，hash 值为 0，0&任意数都是 0，那么通过 indexFor 计算出的 index 也是为 0 的。所以我们可以看出，这里的所有 key 为 null 的值都放在了 index 为 0 的位置上。
对于 indexFor 的计算，下面一张图可以说明的很清楚，可以将一个很大的值，转换成一个不大于 length-1 的值。
这里有一个小缺陷，如果多个数的高位不等，低位相等，那么计算出的 index 是一样的。所以这里在进行 hash 值计算的时候进行了两次计算，是为了让 hashCode 中的 32 位数更加分散，使更多的数值能够进行 indexFor 中的计算。从而减少 hash 碰撞的几率。
createEntry 创建节点并填充到数组的过程，我们可以看到新添加的节点都是在链表的头部。
put(K key, V value)
public V put(K key, V value) {if (table == EMPTY_TABLE) {//如果默认为空数组，则进行初始化数组inflateTable(threshold);}if (key == null)return putForNullKey(value);int hash = hash(key);int i = indexFor(hash, table.length);//如果该索引处有节点，那么查找这个链表上是否有相同的 key和 Hash， 如果有就直接替换 value，将旧 value 返回出去。for (Entry<K,V> e = table[i]; e != null; e = e.next) {Object k;if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {V oldValue = e.value;e.value = value;e.recordAccess(this);return oldValue;}}modCount++;addEntry(hash, key, value, i);return null;}
put 方法和上面分析的putAllForCreate 方法很像，都是计算 hash 值，然后根据hash 值计算 index，再看该index 对应的位置上是否已经有节点，如果有就判断当前要存入的 key 是否已经存在，如果存在就直接替换值。
在 put 方法中，我们看到了 key 为 null 时调用的处理方法： putForNullKey。
putForNullKey
private V putForNullKey(V value) {for (Entry<K,V> e = table[0]; e != null; e = e.next) {if (e.key == null) {V oldValue = e.value;e.value = value;e.recordAccess(this);return oldValue;}}modCount++;addEntry(0, null, value, 0);return null;}
这里对于 key 为 null 的节点，也是直接放在了索引为 0 的位置上。如果已经有 key 为 null 的节点存在，则替换新值，返回旧值。
在put 的时候无论 key 为 null，还是不为 null，在找不到相同 key 的节点后，都会新添加一个节点。调用的方法就是 addEntry。
addEntry
void addEntry(int hash, K key, V value, int bucketIndex) {//下面的判断为扩容判断//可以看出，如果当前 hashMap 的节点数大于临界值，并且要储存的位置上存在节点，则进行扩容。if ((size >= threshold) && (null != table[bucketIndex])) {//扩容后的长度为 2 倍的当前长度。resize(2 * table.length);//扩容后，重新计算 hash 值和 indexhash = (null != key) ? hash(key) : 0;bucketIndex = indexFor(hash, table.length);}//扩容后，添加新的节点。createEntry(hash, key, value, bucketIndex);}
resize
void resize(int newCapacity) {Entry[] oldTable = table;int oldCapacity = oldTable.length;//如果数量已经超过最大值，则不进行扩容，并将临界值 threshold赋值为 int 最大值。if (oldCapacity == MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return;}//创建新的数组Entry[] newTable = new Entry[newCapacity];//将旧数据复制到新数组中。transfer(newTable, initHashSeedAsNeeded(newCapacity));table = newTable;//计算新的临界值threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);}void transfer(Entry[] newTable, boolean rehash) {int newCapacity = newTable.length;for (Entry<K,V> e : table) {while(null != e) {Entry<K,V> next = e.next;//是否需要重新计算 hash 值，一般不会//这个 rehash 是通过initHashSeedAsNeeded(newCapacity) 的出来的。if (rehash) {e.hash = null == e.key ? 0 : hash(e.key);}//重新计算 index。int i = indexFor(e.hash, newCapacity);//将 e 添加到该索引下的链表中。这里可以看出链表被反转了。e.next = newTable[i];newTable[i] = e;e = next;}}}
这里扩容的时候，直接将原来数组长度扩容到 2 倍。
在扩容复制旧的数据的时候也可以看出，原先一个索引对应的链表顺序被反转了，越往后的数据复制后越在前面。
get、remove 就没什么好说的了，就是通过 key 计算 hash 值，然后再计算 index， 通过对比 key，找到节点，然后继续操作。
总结
- HashMap 的数据结构是数组+链表的形式。
- HashMap 是线程不安全的。
- HashMap 的默认初始值为 16，临界值的负载因子为 0.75，所以默认的临界值大小就是 16*0.75 = 12。
- HashMap 初始化的时候并不会创建数组，只有在第一次添加数据的时候才会创建。
- 创建 HashMap 的时候可以指定初始容量值，第一次创建数组的时候，数组的容量大小调整为是 2 的幂次方。
- HashMap 允许 key 为 null，key 为 null的节点存储在 index 为0 的位置上。
- 当数量达到临界值，并且要存储的位置上已经有了节点，那么就会扩容，每次扩容为原来数组的 2 倍大小。所以容量值一直都是 2 的幂次方。
- 当要存放的位置上已经有了节点，那么新的节点放在头部，旧的链表放在新节点的后面。头插法。
-
jdk1.8
1.8 版本的 HashMap 也是数组+链表的实现。只不过在链表长度达到7 时，就会转换为红黑树。
1.7 版本中数组存储的节点是 Entry，1.8 存储的节点是 Node，这两个的数据结构是一样的。只是类名不同而已Node
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;}......}
构造+成员变量
```java static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16//默认初始容量
static final int MAXIMUM_CAPACITY = 1 << 30;//最大容量值
static final float DEFAULT_LOAD_FACTOR = 0.75f;//默认的临界值的负载因子
static final int TREEIFY_THRESHOLD = 8;//链表长度大于 8 时转换为树
static final int UNTREEIFY_THRESHOLD = 6; //树的大小小于 6 时转换为链表
static final int MIN_TREEIFY_CAPACITY = 64;
transient Node
transient int size;//节点数量
transient int modCount;//操作 HashMap 的次数（增、修、删）。在迭代的时候如果 modCount 发生变化，抛出异常。避免多线程并发出现数据异常。
int threshold;//扩容的临界值
final float loadFactor;//临界值的负载因子
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; this.threshold = tableSizeFor(initialCapacity); }
public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); }
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted }
public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }
和 1.7 类似，构造方法都是指定临界值的负载因子 loadFactor，以及初始容量值 threshold。threshold 在初始化的时候，是作为记录初始容量值存在的。<br />多了几个成员变量 `TREEIFY_THRESHOLD`，`UNTREEIFY_THRESHOLD`，`MIN_TREEIFY_CAPACITY`。<br />1.8 的 HashMap 在构造的时候也可以直接传入一个已有的 HashMap 。```javafinal void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {int s = m.size();if (s > 0) {if (table == null) { // pre-size//如果数组为 null，计算容量大小。float ft = ((float)s / loadFactor) + 1.0F;int t = ((ft < (float)MAXIMUM_CAPACITY) ?(int)ft : MAXIMUM_CAPACITY);if (t > threshold)//如果计算出的数值大于初始容量，则重新计算初始容量，tableSizeFor 计算得出比 t 大并最小的2 的幂次方。threshold = tableSizeFor(t);}else if (s > threshold)//数组不为 null，但是需要的容量大于临界值。则扩容。resize();for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {K key = e.getKey();V value = e.getValue();//添加元素。putVal(hash(key), key, value, false, evict);}}}
resize()
final Node<K,V>[] resize() {Node<K,V>[] oldTab = table;//定义旧长度，旧的临界值。新长度，新临界值变量int oldCap = (oldTab == null) ? 0 : oldTab.length;int oldThr = threshold;int newCap, newThr = 0;if (oldCap > 0) {//原先的数组长度已经达到了最大值。直接返回，不再扩容。if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}//没有达到最大，则直接将原有的长度*2 为新长度。计算出的新长度小于最大值，并旧长度大于默认容量 16，则临界值也*2else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;else { // zero initial threshold signifies using defaults//所有一切都是新创建的，则设置为默认的容量 16，默认的临界值 16*0.75 = 12newCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}if (newThr == 0) {//如果新的临界值还没有计算，则计算。float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}//临界值赋值threshold = newThr;//创建数组@SuppressWarnings({"rawtypes","unchecked"})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;//将原有数组的值置为 nullif (e.next == null)//只有一个节点e，不是链表，则计算出 index = e.hash & (newCap - 1)，这里和 1.7 计算方法一样。//然后继续赋值。newTab[e.hash & (newCap - 1)] = e;else if (e instanceof TreeNode)//节点是树((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else { // preserve order//单链表//扩容后，每个节点都要重新计算下标，其实重新计算出的下标只可能是两个数：1.自己本身 2.本身+oldCapNode<K,V> loHead = null, loTail = null;//低位Node<K,V> hiHead = null, hiTail = null;//高位Node<K,V> next;//将这个单链表拆分为高位链表和低位链表。do {next = e.next;//(e.hash & oldCap) == 0 说明该节点重新计算出的 index 还是 j。具体为什么，下面分析。if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.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;}
从代码中也可以看出，其实数组的初始化操作也在 resize 方法中。
上面的逻辑可以分为三种：
- 原先数组不为空，则进行2 倍的扩容，临界值也会2 倍的扩大。然后进行创建数组，将旧数组中的数值复制到新数组中。
- 数组为空，但是指定过初始容量，临界值 = 初始容量*负载因子。
- 什么都没有指定，则容量为默认值 16，临界值为 16*0.75 = 12。
可以在我们后续添加数据需要扩容的时候，临界值就和负载因子无关了，直接将原有的临界值扩大2倍。
在将原先数组中的数据进行复制的时候，分为三种情况：
- 只有一个节点，直接赋值。
- 原先节点是树，则分隔树
- 原先节点是链表，则将链表分隔为高位和低位链表。
可以看出和 1.7 的直接计算索引然后赋值不同，这里提升了运行性能。
e.hash&(length - 1)
这里分析为什么节点重新计算的索引只可能是原先的索引，或者原先的索引+旧数组长度。
首先，我们知道计算一个节点的索引的公式是：e.hash & (length - 1)
int hash = 73565;//(10001111101011101)//hash 值int oldCap = 32,newCap = 32*2; //原先的长度 32 ，扩容后的长度64.10001111101011101 7356500000000000100000 32 hash & oldCap 运算后的数值：0000000000000000000000000000011111 32-1 hash & oldCap-1 运算后的数值：00000000000011101 原先的索引00000000001000000 64 hash & newCap 运算后的数值：0000000000000000000000000000111111 64-1 hash & newCap-1 运算后的数值：00000000000011101 新的索引从上面可以看出 e.hash & oldCap 的结果只有两个可能，如果hash 值第 6 位的位数为 1，则值为 oldCap；第 6 位位数为 0，则值为 0。对于e.hash&(newCap - 1) 、e.hash&(oldCap - 1) 两者相比较而言，就是看在hash值的第 6 位是否为 1。所以 int oldIndex = e.hash & (oldCap - 1);int newIndex = e.hash&(newCap - 1) = (e.hash&newCap==0)?oldIndex:oldIndex+oldCap。
putVal、newNode
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);}//onlyIfAbsent: 在添加元素的时候，如果有相同的 key，只有这个 key 对应的 value 为 null 的时候新的 value才会被添加进去。//evict 这个字段是给 HashMap 的子类 LinkedHashMap 使用的。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)//如果数组为空，则调用 resize 继续初始化数组。n = (tab = resize()).length;//计算索引，如果该索引上没有节点，直接进行赋值。if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {//该索引上有节点Node<K,V> e; K k;if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))//第一个节点 和要插入节点的 hash 相同，key 相同。直接赋值给 e。e = p;else if (p instanceof TreeNode)//第一个节点不符合，而且该节点是树e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {//第一个节点不符合，而且该节点是链表//遍历寻找是否有相同 hash 和 key，如果有就退出循环，没有就在最后一个节点的尾部创建一个节点。for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {//尾部添加新节点p.next = newNode(hash, key, value, null);//添加节点后，链表长度 不小于 8，则将链表转换为树。if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}if (e != null) { // existing mapping for key//将旧值替换为新值。V oldValue = e.value;//如果 onlyIfAbsent 为 true，那么只有旧的 Value 为 null，新的 value 才会添加。if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;//添加新数据后，数量超过临界值，进行扩容。if (++size > threshold)resize();afterNodeInsertion(evict);return null;}Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {return new Node<>(hash, key, value, next);}
添加新节点时，如果数组还没有创建，则调用 resize 进行初始化数组。
然后计算索引，后面的逻辑分为两种：
- 该索引处没有节点，则直接创建新节点并赋值。
节点有值，又分为三种情况
1.8 的 HashMap 也是数组+链表/红黑树 的形式组成的，出现 Hash 碰撞的时候，最初是按照链表的数据结构进行添加数据的，链表长度大于 8 的时候，将链表转化为红黑树。
- 添加数据的时候，是在链表的尾部进行添加，尾插法。
- 扩容后，在复制原先的链表时，保持了原先链表的相对顺序。
- 扩容后，一般临界值的计算与负载因子无关了，直接扩大 2 倍。
- 允许相同 key 值不进行覆盖，只有不存在这个 key，或者这个 key 对应的 value 为 null 时，新的 value 才会被赋值进去。
在Java8中为什么要使用红黑树来实现的HashMap？
一、前言
在jdk1.8版本后，Java对HashMap做了改进，在链表长度大于8的时候，将后面的数据存在红黑树中，以加快检索速度。二、红黑树回顾
红黑树的英文是“Red-Black Tree”，简称R-B Tree。它是一种不严格的平衡二叉查找树，我前面说了，它的定义是不严格符合平衡二叉查找树的定义的。那红黑树空间是怎么定义的呢？
顾名思义，红黑树中的节点，一类被标记为黑色，一类被标记为红色除此之外，一棵红黑树还需要满足这样几个要求：
- 根节点是黑色的；
- 每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据；
- 任何相邻的节点都不能同时为红色，红色节点是被黑色节点隔开的；
- 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点
1. 红黑树概念和图示
红黑树比较传统的定义是需要满足以下五个特征：
- 每个节点或者是黑色，或者是红色。
- 根节点是黑色。
- 每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
- 如果一个节点是红色的，则它的子节点必须是黑色的。
- 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
其特点在于给数的每一个节点加上了颜色属性，在插入的过程中通过颜色变换和节点旋转调平衡。其实博主不是很喜欢上面的定义，还有一种视角就是将它与二三树比较。
2.红黑树的优势
红黑树是”近似平衡“的。
红黑树相比avl树，在检索的时候效率其实差不多，都是通过平衡来二分查找。但对于插入删除等操作效率提高很多。红黑树不像avl树一样追求绝对的平衡，他允许局部很少的不完全平衡，这样对于效率影响不大，但省去了很多没有必要的调平衡操作，avl树调平衡有时候代价较大，所以效率不如红黑树，在现在很多地方都是底层都是红黑树的天下啦。
红黑树的高度只比高度平衡的AVL树的高度（log2n）仅仅大了一倍，在性能上却好很多。
HashMap在里面就是链表加上红黑树的一种结构，这样利用了链表对内存的使用率以及红黑树的高效检索，是一种很happy的数据结构。
AVL树是一种高度平衡的二叉树，所以查找的非常高，但是，有利就有弊，AVL树为了维持这种高度的平衡，就要付出更多代价。每次插入、删除都要做调整，就比较复杂、耗时。所以，对于有频繁的插入、删除操作的数据集合，使用AVL树的代价就有点高了。
红黑树只是做到了近似平衡，并不严格的平衡，所以在维护的成本上，要比AVL树要低。
所以，红黑树的插入、删除、查找各种操作性能都比较稳定。对于工程应用来说，要面对各种异常情况，为了支撑这种工业级的应用，我们更倾向于这种性能稳定的平衡二叉查找树。
1.8 为什么改为尾插法
HashMap在jdk1.7中采用头插入法，在扩容时会改变链表中元素原本的顺序，以至于在并发场景下导致链表成环的问题。而在jdk1.8中采用尾插入法，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了。
三、总结
java8不是用红黑树来管理hashmap，而是在hash值相同的情况下（且重复数量大于8），用红黑树来管理数据。 红黑树相当于排序数据，可以自动的使用二分法进行定位，性能较高。一般情况下，hash值做的比较好的话基本上用不到红黑树。
红黑树牺牲了一些查找性能 但其本身并不是完全平衡的二叉树。因此插入删除操作效率略高于AVL树。
AVL树用于自平衡的计算牺牲了插入删除性能，但是因为最多只有一层的高度差，查询效率会高一些。
参考文章
若有收获，就点个赞吧
0 人点赞
