-
【Java基础(高级篇)】集合源码剖析
集合源码剖析
1. List接口分析
1.1 ArrayList
-
底层使用数组维护，线程不安全，效率高
-
容量及扩容机制：默认容量0，扩容时先判断旧的数组长度，如果旧的数组长度+1 小于10 则会将数组容量扩大到10，否则则以1.5倍进行扩容；
扩容时会先创建对应容量的数组，再将旧的数组内容复制到新的数组中。
1.2 LinkedList
-
Java中有双链表的实现：LinkedList，它是List接口的实现类。
-
LinkedList是一个
双向链表，如图所示：
- 链表底层的物理结构是链表，因此根据索引访问的效率不高（O(n)），即查找元素慢。但是插入和删除不需要移动元素，只需要修改前后元素的指向关系即可，所以插入、删除元素快。而且链表的添加不会涉及到扩容问题。
2. Map接口分析
2.1 哈希表的物理结构
HashMap和Hashtable底层都是哈希表（也称散列表），其中维护了一个长度为2的幂次方的Entry类型的数组table，数组的每一个索引位置被称为一个桶(bucket)，添加的映射关系(key,value)最终都被封装为一个Map.Entry类型的对象，放到某个table[index]桶中。
使用数组的目的是查询和添加的效率高，可以根据索引直接定位到某个table[index]。
2.2 HashMap中数据添加过程
2.2.1 JDK7中过程分析
// 在底层创建了长度为16的Entry[] table的数组 HashMap map = new HashMap();- 1
- 2
map.put(key1,value1); /* 分析过程如下： 将(key1,value1)添加到当前hashmap的对象中。首先会调用key1所在类的hashCode()方法，计算key1的哈希值1， 此哈希值1再经过某种运算(hash())，得到哈希值2。此哈希值2再经过某种运算(indexFor())，确定在底层table数组中的索引位置i。 （1）如果数组索引为i上的数据为空，则(key1,value1)直接添加成功 ------位置1 （2）如果数组索引为i上的数据不为空，有(key2,value2)，则需要进一步判断： 判断key1的哈希值2与key2的哈希值是否相同： （3） 如果哈希值不同，则(key1,value1)直接添加成功 ------位置2 如果哈希值相同，则需要继续调用key1所在类的equals()方法，将key2放入equals()形参进行判断 （4） equals方法返回false : 则(key1,value1)直接添加成功 ------位置3 equals方法返回true : 默认情况下，value1会覆盖value2。 位置1：直接将(key1,value1)以Entry对象的方式存放到table数组索引i的位置。 位置2、位置3：(key1,value1) 与现有的元素以链表的方式存储在table数组索引i的位置，新添加的元素指向旧添加的元素。 ... 在不断的添加的情况下，满足如下条件的情况下，会进行扩容: if ((size >= threshold) && (null != table[bucketIndex])) : 默认情况下，当要添加的元素个数超过12(即：数组的长度 * loadFactor得到的结果)时，就要考虑扩容。 补充：jdk7源码中定义的： static class Entry- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
map.get(key1); /* ① 计算key1的hash值，用这个方法hash(key1) ② 找index = table.length-1 & hash; ③ 如果table[index]不为空，那么就挨个比较哪个Entry的key与它相同，就返回它的value */- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
map.remove(key1); /* ① 计算key1的hash值，用这个方法hash(key1) ② 找index = table.length-1 & hash; ③ 如果table[index]不为空，那么就挨个比较哪个Entry的key与它相同，就删除它，把它前面的Entry的next的值修改为被删除Entry的next */- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
2.2.2 JDK8中过程分析
下面说明是JDK8相较于JDK7的不同之处：
- 使用HashMap()的构造器创建对象时，并没有在底层初始化长度为16的table数组。
- jdk8中添加的key,value封装到了HashMap.Node类的对象中。而非jdk7中的HashMap.Entry。
- jdk8中新增的元素所在的索引位置如果有其他元素。在经过一系列判断后，如果能添加，则是旧的元素指向新的元素。而非jdk7中的新的元素指向旧的元素。“七上八下”
- jdk7时底层的数据结构是：数组+单向链表。 而jdk8时，底层的数据结构是：数组+单向链表+红黑树。
红黑树出现的时机：当某个索引位置i上的链表的长度达到8，且数组的长度超过64时，此索引位置上的元素要从单向链表改为红黑树。
如果索引i位置是红黑树的结构，当不断删除元素的情况下，当前索引i位置上的元素的个数低于6时，要从红黑树改为单向链表。
2.3 红黑树
红黑树：即Red-Black Tree。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构。红黑树是复杂的，但它的操作有着
良好的最坏情况运行时间，并且在实践中是高效的：它可以在 O(log n)时间内做查找，插入和删除， 这里的 n 是树中元素的数目。红黑树的特性：
-
每个节点是红色或者黑色
-
根节点是黑色
-
每个叶子节点（NIL）是黑色。（注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点）
-
每个红色节点的两个子节点都是黑色的。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
-
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点（确保没有一条路径会比其他路径长出2倍）
当我们插入或删除节点时，可能会破坏已有的红黑树，使得它不满足以上5个要求，那么此时就需要进行处理，使得它继续满足以上的5个要求：
1、
recolor：将某个节点变红或变黑2、
rotation：将红黑树某些结点分支进行旋转（左旋或右旋）
红黑树可以通过红色节点和黑色节点尽可能的保证二叉树的平衡。主要是用它来存储有序的数据，它的时间复杂度是O(logN)，效率非常之高。
2.4 HashMap源码剖析(JDK1.8.0_271)
2.4.1 Node
key-value被封装为HashMap.Node类型或HashMap.TreeNode类型，它俩都直接或间接的实现了Map.Entry接口。
存储到table数组的可能是Node结点对象，也可能是TreeNode结点对象，它们也是Map.Entry接口的实现类。即table[index]下的映射关系可能串起来一个链表或一棵红黑树。
public class HashMap<K,V>{ transient Node<K,V>[] table; //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; } // 其它结构：略 } //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); } } //.... }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
2.4.2 属性
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认的初始容量 16 static final int MAXIMUM_CAPACITY = 1 << 30; //最大容量 1 << 30 static final float DEFAULT_LOAD_FACTOR = 0.75f; //默认加载因子 static final int TREEIFY_THRESHOLD = 8; //默认树化阈值8，当链表的长度达到这个值后，要考虑树化 static final int UNTREEIFY_THRESHOLD = 6;//默认反树化阈值6，当树中结点的个数达到此阈值后，要考虑变为链表 //当单个的链表的结点个数达到8，并且table的长度达到64，才会树化。 //当单个的链表的结点个数达到8，但是table的长度未达到64，会先扩容 static final int MIN_TREEIFY_CAPACITY = 64; //最小树化容量64 transient Node<K,V>[] table; //数组 transient int size; //记录有效映射关系的对数，也是Entry对象的个数 int threshold; //阈值，当size达到阈值时，考虑扩容 final float loadFactor; //加载因子，影响扩容的频率- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
2.4.3 构造器
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted (其他字段都是默认值) }- 1
- 2
- 3
2.4.4 put()方法
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }- 1
- 2
- 3
其中，
static final int hash(Object key) { int h; //如果key是null，hash是0 //如果key非null，用key的hashCode值 与 key的hashCode值高16进行异或 // 即就是用key的hashCode值高16位与低16位进行了异或的干扰运算 /* index = hash & table.length-1 如果用key的原始的hashCode值 与 table.length-1 进行按位与，那么基本上高16没机会用上。 这样就会增加冲突的概率，为了降低冲突的概率，把高16位加入到hash信息中。 */ return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) { Node<K,V>[] tab; //数组 Node<K,V> p; //一个结点 int n, i; //n是数组的长度 i是下标 //tab和table等价 //如果table是空的 if ((tab = table) == null || (n = tab.length) == 0){ n = (tab = resize()).length; /* tab = resize(); n = tab.length;*/ /* 如果table是空的，resize()完成了①创建了一个长度为16的数组②threshold = 12 n = 16 */ } //i = (n - 1) & hash ，下标 = 数组长度-1 & hash //p = tab[i] 第1个结点 //if(p==null) 条件满足的话说明 table[i]还没有元素 if ((p = tab[i = (n - 1) & hash]) == null){ //把新的映射关系直接放入table[i] tab[i] = newNode(hash, key, value, null); //newNode（）方法就创建了一个Node类型的新结点，新结点的next是null }else { Node<K,V> e; K k; //p是table[i]中第一个结点 //if(table[i]的第一个结点与新的映射关系的key重复) if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p;//用e记录这个table[i]的第一个结点 else if (p instanceof TreeNode){ //如果table[i]第一个结点是一个树结点 //单独处理树结点 //如果树结点中，有key重复的，就返回那个重复的结点用e接收，即e!=null //如果树结点中，没有key重复的，就把新结点放到树中，并且返回null，即e=null e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); }else { //table[i]的第一个结点不是树结点，也与新的映射关系的key不重复 //binCount记录了table[i]下面的结点的个数 for (int binCount = 0; ; ++binCount) { //如果p的下一个结点是空的，说明当前的p是最后一个结点 if ((e = p.next) == null) { //把新的结点连接到table[i]的最后 p.next = newNode(hash, key, value, null); //如果binCount>=8-1，达到7个时 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st //要么扩容，要么树化 treeifyBin(tab, hash); break; } //如果key重复了，就跳出for循环，此时e结点记录的就是那个key重复的结点 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e;//下一次循环，e=p.next，就类似于e=e.next，往链表下移动 } } //如果这个e不是null，说明有key重复，就考虑替换原来的value if (e != null) { // existing mapping for key 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; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; //oldTab原来的table //oldCap：原来数组的长度 int oldCap = (oldTab == null) ? 0 : oldTab.length; //oldThr：原来的阈值 int oldThr = threshold;//最开始threshold是0 //newCap，新容量 //newThr：新阈值 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) //newCap = 旧的容量*2 ，新容量<最大数组容量限制 //新容量：32,64，... //oldCap >= 初始容量16 //新阈值重新算 = 24，48 .... newThr = oldThr << 1; // double threshold } else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; //新容量是默认初始化容量16 //新阈值= 默认的加载因子 * 默认的初始化容量 = 0.75*16 = 12 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; //阈值赋值为新阈值12，24.。。。 //创建了一个新数组，长度为newCap，16，32,64.。。 @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; if (oldTab != null) { //原来不是空数组 //把原来的table中映射关系，倒腾到新的table中 for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) {//e是table下面的结点 oldTab[j] = null; //把旧的table[j]位置清空 if (e.next == null) //如果是最后一个结点 newTab[e.hash & (newCap - 1)] = e; //重新计算e的在新table中的存储位置，然后放入 else if (e instanceof TreeNode) //如果e是树结点 //把原来的树拆解，放到新的table ((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; //把原来table[i]下面的整个链表，重新挪到了新的table中 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; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) { //创建一个新结点 return new Node<>(hash, key, value, next); }- 1
- 2
- 3
- 4
final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; //MIN_TREEIFY_CAPACITY：最小树化容量64 //如果table是空的，或者 table的长度没有达到64 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize();//先扩容 else if ((e = tab[index = (n - 1) & hash]) != null) { //用e记录table[index]的结点的地址 TreeNode<K,V> hd = null, tl = null; /* do...while，把table[index]链表的Node结点变为TreeNode类型的结点 */ do { TreeNode<K,V> p = replacementTreeNode(e, null); if (tl == null) hd = p;//hd记录根结点 else { p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) != null); //如果table[index]下面不是空 if ((tab[index] = hd) != null) hd.treeify(tab);//将table[index]下面的链表进行树化 } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
小结：
2.5 LinkedHashMap源码剖析
与HashMap相比，LinkedHashMap底层多维护了一层链表，用来使得Map中元素有序
2.5.1 源码
内部定义的Entry如下：
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); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
LinkedHashMap重写了HashMap中的newNode()方法：
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) { LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e); linkNodeLast(p); return p; }- 1
- 2
- 3
- 4
- 5
- 6
TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) { TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next); linkNodeLast(p); return p; }- 1
- 2
- 3
- 4
- 5
2.5.2 图示
2.6 TreeMap源码剖析
- TreeMap底层使用红黑树实现
- 为何innodb不使用红黑树？对于在内存中的查找结构而言，红黑树的效率已经非常好了(实际上很多实际应用还对RBT进行了优化)。但是如果是数据量非常大的查找呢？将这些数据全部放入内存组织成RBT结构显然是不实际的。在磁盘中组织查找结构，从任何一个结点指向其他结点都有可能读取一次磁盘数据，再将数据写入内存进行比较。频繁的磁盘IO操作，效率是很低下的(机械运动比电子运动要慢不知道多少)。显而易见，所有的二叉树的查找结构在磁盘中都是低效的。红黑树只是二叉树，数据过多的话深度会很深，不够扁平，因此，B+树很好的解决了这一个问题。
3. Set接口分析
3.1 Set集合与Map集合的关系
Set的内部实现其实是一个Map，Set中的元素，存储在HashMap的key中。即HashSet的内部实现是一个HashMap，TreeSet的内部实现是一个TreeMap，LinkedHashSet的内部实现是一个LinkedHashMap。
3.2 源码剖析
HashSet源码：
//构造器 public HashSet() { map = new HashMap<>(); } public HashSet(int initialCapacity, float loadFactor) { map = new HashMap<>(initialCapacity, loadFactor); } public HashSet(int initialCapacity) { map = new HashMap<>(initialCapacity); } //这个构造器是给子类LinkedHashSet调用的 HashSet(int initialCapacity, float loadFactor, boolean dummy) { map = new LinkedHashMap<>(initialCapacity, loadFactor); } //add()方法： public boolean add(E e) { return map.put(e, PRESENT)==null; } //其中， private transient HashMap<E,Object> map; private static final Object PRESENT = new Object(); //iterator()方法： public Iterator<E> iterator() { return map.keySet().iterator(); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
LinkedHashSet源码：
//构造器 public LinkedHashSet() { super(16, .75f, true); } public LinkedHashSet(int initialCapacity) { super(initialCapacity, .75f, true);//调用HashSet的某个构造器 } public LinkedHashSet(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor, true);//调用HashSet的某个构造器 }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
TreeSet源码：
public TreeSet() { this(new TreeMap<E,Object>()); } TreeSet(NavigableMap<E,Object> m) { this.m = m; } //其中， private transient NavigableMap<E,Object> m; //add()方法： public boolean add(E e) { return m.put(e, PRESENT)==null; } //其中， private static final Object PRESENT = new Object();- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
4. HashMap的相关问题
4.1 Entry中的hash属性为什么不直接使用key的hashCode()返回值呢？
不管是JDK1.7还是JDK1.8中，都不是直接用key的hashCode值直接与table.length-1计算求下标的，而是先对key的hashCode值进行了一个运算，JDK1.7和JDK1.8关于hash()的实现代码不一样，但是不管怎么样都是为了提高hash code值与 (table.length-1)的按位与完的结果，尽量的均匀分布。
JDK1.7：
final int hash(Object k) { int h = hashSeed; if (0 != h && k instanceof String) { return sun.misc.Hashing.stringHash32((String) k); } h ^= k.hashCode(); h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
JDK1.8：
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }- 1
- 2
- 3
- 4
虽然算法不同，但是思路都是将hashCode值的高位二进制与低位二进制值进行了异或，让高位二进制参与到index的计算中。
为什么要hashCode值的二进制的高位参与到index计算呢？
因为一个HashMap的table数组一般不会特别大，至少在不断扩容之前，那么table.length-1的大部分高位都是0，直接用hashCode和table.length-1进行&运算的话，就会导致总是只有最低的几位是有效的，那么就算你的hashCode()实现的再好也难以避免发生碰撞，这时让高位参与进来的意义就体现出来了。它对hashcode的低位添加了随机性并且混合了高位的部分特征，显著减少了碰撞冲突的发生。
4.2 HashMap是如何决定某个key-value存在哪个桶的呢？
因为hash值是一个整数，而数组的长度也是一个整数，有两种思路：
①hash 值 % table.length会得到一个[0,table.length-1]范围的值，正好是下标范围，但是用%运算效率没有位运算符&高。
②hash 值 & (table.length-1)，任何数 & (table.length-1)的结果也一定在[0, table.length-1]范围。
JDK1.8：
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) // i = (n - 1) & hash tab[i] = newNode(hash, key, value, null); //....省略大量代码 }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
4.3 为什么要保持table数组一直是2的n次幂呢？
因为如果数组的长度为2的n次幂，那么table.length-1的二进制就是一个高位全是0，低位全是1的数字，这样才能保证每一个下标位置都有机会被用到。
举例1：
hashCode值是 ？ table.length是10 table.length-1是9 ？ ???????? 9 00001001 &_____________ 00000000 [0] 00000001 [1] 00001000 [8] 00001001 [9] 一定[0]~[9]- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
举例2：
hashCode值是 ？ table.length是16 table.length-1是15 ？ ???????? 15 00001111 &_____________ 00000000 [0] 00000001 [1] 00000010 [2] 00000011 [3] ... 00001111 [15] 范围是[0,15]，一定在[0,table.length-1]范围内- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
4.4 解决[index]冲突问题
虽然从设计hashCode()到上面HashMap的hash()函数，都尽量减少冲突，但是仍然存在两个不同的对象返回的hashCode值相同，或者hashCode值就算不同，通过hash()函数计算后，得到的index也会存在大量的相同，因此key分布完全均匀的情况是不存在的。那么发生碰撞冲突时怎么办？
JDK1.8之后使用：数组+链表/红黑树的结构。
即hash相同或hash&(table.lengt-1)的值相同，那么就存入同一个“桶”table[index]中，使用链表或红黑树连接起来。
4.5 为什么JDK1.8会出现红黑树和链表共存呢？
因为当冲突比较严重时，table[index]下面的链表就会很长，那么会导致查找效率大大降低，而如果此时选用二叉树可以大大提高查询效率。
但是二叉树的结构又过于复杂，占用内存也较多，如果结点个数比较少的时候，那么选择链表反而更简单。所以会出现红黑树和链表共存。
4.6 加载因子的值大小有什么关系？
如果太大，threshold就会很大，那么如果冲突比较严重的话，就会导致table[index]下面的结点个数很多，影响效率。
如果太小，threshold就会很小，那么数组扩容的频率就会提高，数组的使用率也会降低，那么会造成空间的浪费。
4.7 什么时候树化？什么时候反树化？
static final int TREEIFY_THRESHOLD = 8;//树化阈值 static final int UNTREEIFY_THRESHOLD = 6;//反树化阈值 static final int MIN_TREEIFY_CAPACITY = 64;//最小树化容量- 1
- 2
- 3
-
当某table[index]下的链表的结点个数达到8，并且table.length>=64，那么如果新Entry对象还添加到该table[index]中，那么就会将table[index]的链表进行树化。
-
当某table[index]下的红黑树结点个数少于6个，此时，
- 当继续删除table[index]下的树结点，最后这个根结点的左右结点有null，或根结点的左结点的左结点为null，会反树化
- 当重新添加新的映射关系到map中，导致了map重新扩容了，这个时候如果table[index]下面还是小于等于6的个数，那么会反树化9、key-value中的key是否可以修改？
key-value存储到HashMap中会存储key的hash值，这样就不用在每次查找时重新计算每一个Entry或Node（TreeNode）的hash值了，因此如果已经put到Map中的key-value，再修改key的属性，而这个属性又参与hashcode值的计算，那么会导致匹配不上。
这个规则也同样适用于LinkedHashMap、HashSet、LinkedHashSet、Hashtable等所有散列存储结构的集合。
4.8 JDK1.7中HashMap的循环链表是怎么回事？如何解决？
避免HashMap发生死循环的常用解决方案：
- 多线程环境下，使用线程安全的ConcurrentHashMap替代HashMap，推荐
- 多线程环境下，使用synchronized或Lock加锁，但会影响性能，不推荐
- 多线程环境下，使用线程安全的Hashtable替代，性能低，不推荐
在JDK1.8中，HashMap改用尾插法，解决了链表死循环的问题，但需注意HashMap线程不安全，多线程情况下会导致map的size不准确，且put的数据会丢失。
头插法：在插入时，新的结点插入到当前链表的表头。
尾插法：在插入时，新的结点插入到当前链表的表尾，为此必须增加一个尾指针
r，使其始终指向当前链表的尾结点。线程不安全示例：
public class Main { public static void main(String[] args) throws InterruptedException { HashMap map = new HashMap<>(); Thread thread1 = new Thread(() -> { for (int i = 0; i < 50; i++) { map.put(i, i); } System.out.println("线程1执行结束"); }); Thread thread2 = new Thread(() -> { for (int i = 50; i < 100; i++) { map.put(i, i); } System.out.println("线程2执行结束"); }); thread1.start(); thread2.start(); Thread.sleep(1000); System.out.println("map.size:" + map.size()); int j = 0; for (int i = 0; i < 100; i++) { if (!map.containsKey(i)) { j++; } } System.out.println("实际缺少key数量：" + j); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
执行结果（多线程执行情况可能会不一样）：
线程2执行结束 线程1执行结束 map.size:92 实际缺少key数量：12- 1
- 2
- 3
- 4
-
-
相关阅读:
《太赫兹雷达成像技术》阅读笔记 1：第一章 概论
【Python】设计模式&异常
Canvas动画
【个人博客系统 × Redis】“最后的升级” · 连接Redis · Redis的基本使用
springboot项目启动失败，不打印报错详细信息(启动打印日记问题)
vue报错信息汇总
lambda表达式，函数式接口和方法引用
SpringBoot自定义注解+异步+观察者模式实现业务日志保存
vscode debug时 stepinto 无法跳进代码
浅析 SQL Server 的 CROSS APPLY 和 OUTER APPLY 查询 - 第二部分
- 原文地址：https://blog.csdn.net/xxx1276063856/article/details/134087436
