JDK7说过的东西,本篇文章不再讲解
数据结构 红黑树 在JDK8中,优化了HashMap的数据结构,引入了红黑树。即HashMap的数据结构:数组+链表+红黑树。HashMap变成了这样。
为什么要引入红黑树 1、主要是为了提高HashMap的性能,即解决发生hash冲突后,因为链表过长而导致索引效率慢的问题
2、链表的索引速度是O(n),而利用了红黑树快速增删改查的特点,时间复杂度就是O(logn)。
Node类 HashMap
中的数组元素,链表节点均采用Node
类 实现,与 JDK 1.7
的对比(Entry
类),仅仅只是换了名字。
就是一些常规的方法
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; } public final K getKey () { return key; } public final V getValue () { return value; } public final String toString () { return key + "=" + value; } public final V setValue (V newValue) { V oldValue = value; value = newValue; return oldValue; } public final int hashCode () { return Objects.hashCode(key) ^ Objects.hashCode(value); } public final boolean equals (Object o) { if (o == this ) return true ; if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true ; } return false ; } }
TreeNode类 static final class TreeNode <K ,V > extends LinkedHashMap .Entry <K ,V > { TreeNode<K,V> parent; TreeNode<K,V> left; TreeNode<K,V> right; TreeNode<K,V> prev; boolean red; TreeNode(int hash, K key, V val, Node<K,V> next) { super (hash, key, val, next); } final TreeNode<K,V> root () { for (TreeNode<K,V> r = this , p;;) { if ((p = r.parent) == null ) return r; r = p; } }
重要参数
JDK7里讲过的就不再讲了
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4 ; static final int MAXIMUM_CAPACITY = 1 << 30 ; final float loadFactor; static final float DEFAULT_LOAD_FACTOR = 0.75f ; int threshold; transient Node<K,V>[] table; transient int size; static final int TREEIFY_THRESHOLD = 8 ; static final int UNTREEIFY_THRESHOLD = 6 ; static final int MIN_TREEIFY_CAPACITY = 64 ;
构造函数源码 public class HashMap <K ,V > extends AbstractMap <K ,V > implements Map <K ,V >, Cloneable , Serializable { public HashMap () { this .loadFactor = DEFAULT_LOAD_FACTOR; } public HashMap (int initialCapacity) { this (initialCapacity, DEFAULT_LOAD_FACTOR); } 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 (Map<? extends K, ? extends V> m) { this .loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false ); } }
tableSizeFor() static final int tableSizeFor (int cap) { int n = cap - 1 ; n |= n >>> 1 ; n |= n >>> 2 ; n |= n >>> 4 ; n |= n >>> 8 ; n |= n >>> 16 ; return (n < 0 ) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1 ; }
public class test { public static void main (String[] args) { int n = 65538 ; System.out.println("开始:" + Integer.toBinaryString(n)); int res = tableSizeFor(n); System.out.println("最终结果:" + res); } static final int MAXIMUM_CAPACITY = 1 << 30 ; static final int tableSizeFor (int cap) { int n = cap - 1 ; n |= n >>> 1 ; System.out.println(Integer.toBinaryString(n)); n |= n >>> 2 ; System.out.println(Integer.toBinaryString(n)); n |= n >>> 4 ; System.out.println(Integer.toBinaryString(n)); n |= n >>> 8 ; System.out.println(Integer.toBinaryString(n)); n |= n >>> 16 ; System.out.println(Integer.toBinaryString(n)); return (n < 0 ) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1 ; } }
输出结果:
开始:10000000000000010 11000000000000001 11110000000000001 11111111000000001 11111111111111111 11111111111111111 最终结果:131072 Process finished with exit code 0
第一次运行: 10000000000000010 n >>> 1; 01000000000000000 进行|运算 11000000000000001 分析: 把最大位的1,通过位移后移一位,并且通过|运算,组合起来
第二次运行: 11000000000000001 n >>> 2; 00110000000000000 进行|运算 11110000000000001 分析: 把最大的两位,已经变成1的,往后移动两位,并且通过|运算,组合起来
第三次运行: 11110000000000001 n >>> 4; 00001111000000000 进行|运算 11111111000000001 分析: 把最大4位,已经变成1的,往后移动4位,并且通过|运算,组合起来
第四次运行: 11111111000000001 n >>> 8; 00000000111111110 进行|运算 11111111111111111 分析: 把最大的8位,已经变成1的,往后移动8位,并且通过|运算,组合起来
第五次运算: 同上。因为我的数据,最大只到17位,所有第五次没有效果。可以用32位来进行运算,第五次是通过前16位已经变成1的数据,往后移动16位,然后通过或运算,最后的结果是32位都变成1。
原理就是,保证造成一个所有位都为1的数据。并且通过最后的+1。变成2^N次方的数据。
put源码 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; if ((tab = table) == null || (n = tab.length) == 0 ) 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)))) e = p; else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this , tab, hash, key, value); else { for (int binCount = 0 ; ; ++binCount) { if ((e = p.next) == null ) { p.next = newNode(hash, key, value, null ); if (binCount >= TREEIFY_THRESHOLD - 1 ) treeifyBin(tab, hash); break ; } 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; if (++size > threshold) resize(); afterNodeInsertion(evict); return null ; }
hash() static final int hash (int h) { h ^= k.hashCode(); h ^= (h >>> 20 ) ^ (h >>> 12 ); return h ^ (h >>> 7 ) ^ (h >>> 4 ); } static final int hash (Object key) { int h; return (key == null ) ? 0 : (h = key.hashCode()) ^ (h >>> 16 ); }
JDK8 hash的运算原理:高位参与低位运算,使得hash更加均匀。
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; } else if ((newCap = oldCap << 1 ) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1 ; } else if (oldThr > 0 ) newCap = oldThr; else { newCap = 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 ; 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 { 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 ); if (loTail != null ) { loTail.next = null ; newTab[j] = loHead; } if (hiTail != null ) { hiTail.next = null ; newTab[j + oldCap] = hiHead; } } } } } return newTab; }
JDK8扩容时,数据在数组下标的计算方式
JDK8
根据此结论作出的新元素存储位置计算规则非常简单,提高了扩容效率。
这与 JDK7
在计算新元素的存储位置有很大区别:JDK7
在扩容后,都需按照原来方法进行rehash,效率不高。
get源码 public V get (Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } 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 && ((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 ; }
—下面是常见面试题— HashMap在JDK7和8中区别? 1、hash冲突时:JDK7用的是头插法,而JDK1.8及之后使用的都是尾插法。JDK7是用单链表进行的纵向延伸,当采用头插法时会容易出现逆序且环形链表死循环问题。但是在JDK8之后是使用尾插法,能够避免出现逆序且链表死循环的问题。
2、扩容时:JDK7需要重新进行rehash。JDK8则直接时判断hash值新参与的位是0还是1,0就是原位置,1就是原位置+就容量
3、引入了红黑树(原因前面说过)
4、hash的计算:JDK7是9次扰动(4次位运算 + 5次异或运算),JDK8时是2次扰动(1次位运算 + 1次异或运算)。
5、JDK7是先扩容再插入k-v,JDK8时是插入后一起扩容。
为什么不直接用hash码作为数组table的下标? 1、哈希码一般是int型,范围是-(2^31) – 2^31 - 1。容易出现哈希码与数组大小范围不匹配的情况,即计算出来的哈希码可能不在数组大小范围内,从而导致无法匹配存储位置。
2、常见解决办法就是hash值与数组长度取模。
为什么容量要求为2的幂? 一般来说散列表容量的常规设计思路是容量取素数,因为素数导致冲突的概率 < 合数。比如Hashtable初始化容量就是11(不过扩容后不能保证是素数)
hashmap这样设计的原因是
1、保证哈希码的均匀性。首先容量可为奇数,也可为偶数。假设数组长度为奇数,那么二进制最后一位是1。假设数组长度为偶数,那么二进制最后一位是0。如果是奇数 hash&(length - 1) 铁定是偶数,就会导致浪费了数组的一半位置(奇数索引无法被放数据,hash冲突概率高)。如果是2的幂这种偶数,length - 1就是奇数,那么最终的hash&(length-1)计算出来的索引位置取决于hash值,也就是说可以是偶数索引,也可以是奇数索引,均匀分布。
2、length是2的幂时 hash&(length - 1)等价于hash % length。但是&效率更高,而只有length是2的幂,这两个才等价。
二次扰动的好处 高位充分参与低位运算,加大哈希码低位的随机性,使得分布更均匀,从而提高对应数组存储下标位置的随机性 & 均匀性,最终减少Hash冲突
什么样类型的数据适合做hashmap的key? 像Integer这种,内部属性value被final修饰,保证了Hash值的不可更改性,有效的减少了hash冲突
为什么选择8作为树化阈值? * Because TreeNodes are about twice the size of regular nodes, we * use them only when bins contain enough nodes to warrant use * (see TREEIFY_THRESHOLD). And when they become too small (due to * removal or resizing) they are converted back to plain bins. In * usages with well-distributed user hashCodes, tree bins are * rarely used. Ideally, under random hashCodes, the frequency of * nodes in bins follows a Poisson distribution * (http://en.wikipedia.org/wiki/Poisson_distribution) with a * parameter of about 0.5 on average for the default resizing * threshold of 0.75, although with a large variance because of * resizing granularity. Ignoring variance, the expected * occurrences of list size k are (exp(-0.5 ) * pow (0.5 , k) / * factorial (k) ). The first values are: * * 0: 0.60653066 * 1: 0.30326533 * 2: 0.07581633 * 3: 0.01263606 * 4: 0.00157952 * 5: 0.00015795 * 6: 0.00001316 * 7: 0.00000094 * 8: 0.00000006 * more: less than 1 in ten million
由于treenodes的大小大约是常规节点的两倍,因此我们仅在容器包含足够的节点以保证使用时才使用它们,当它们变得太小(由于移除或调整大小)时,它们会被转换回普通的node节点,容器中节点分布在hash桶中的频率遵循泊松分布,桶的长度超过8的概率非常非常小,作者是根据概率统计而选择了8作为阀值。
为什么选择6和8作为链表化和树化的阈值? 1、首先就是遵循泊松分布概率选了6和8
2、其次:如果选择6和8(如果链表小于等于6树还原转为链表,大于等于8转为树),中间有个差值7可以有效防止链表和树频繁转换。假设一下,如果设计成链表个数超过8则链表转换成树结构,链表个数小于8则树结构转换成链表,如果一个HashMap不停的插入、删除元素,链表个数在8左右徘徊,就会频繁的发生树转链表、链表转树,效率会很低。