vlambda博客
学习文章列表

//默认初始容量 16 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16/** *最大容量，如果在构造函数中指定大于该值，会使用该值作为容量大小，2^30 */static final int MAXIMUM_CAPACITY = 1 << 30;/** * 默认加载因子75%，好比地铁满载率，受疫情影响地铁满载率不超过30% * 1,加载因子设置较大，随着数组中元素装的越多，发生的冲突的概率越大，即对应的链表 * 越长，影响查找效率。 * 2，加载因子设置较小，元素很容易达到设定的阈值，发生扩容操作，数组空间还有很大部分  * 没有利用上，造成空间浪费。 * 因此在时间与空间上的权衡考虑 */static final float DEFAULT_LOAD_FACTOR = 0.75f;
/** * 树化阈值：在链表元素超过8个了，将链表转化为红黑数结果，提高查找效率 */static final int TREEIFY_THRESHOLD = 8;
/** * 取消树化阈值：在红黑树中节点数量小于6个，将其转化为链表结构 */static final int UNTREEIFY_THRESHOLD = 6;/** * 最小树化容量,容易忽视 * 链表树化红黑树条件： * 1，链表中元素数量超过(>)8个; * 2, 满足map中元素个数(size)大于等于64否则会先扩容，扩容对解决hash冲突更有效。 */static final int MIN_TREEIFY_CAPACITY = 64;

//传有初始容量和加载因子1.HashMap(int initialCapacity, float loadFactor)//有初始容量，加载因子默认2.HashMap(int initialCapacity)//初始容量, 加载因子默认3.HashMap()//传递的一个Map子集4.HashMap(Map<? extends K, ? extends V> m)

//实现Map集合的Entry类static class Node<K,V> implements Map.Entry<K,V> { //记录当前节点key的hash 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; } //重写了hashcode  public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); }
 public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } //重写了equals 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; }}

// 继承LinkedHashMap.Entry 继承>> HashMap.Nodestatic final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree linksTreeNode<K,V> left;TreeNode<K,V> right;TreeNode<K,V> prev; // needed to unlink next upon deletion//颜色是否为红色boolean red;

public V put(K key, V value) { return putVal(hash(key), key, value, false, true);}

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

 (h = key.hashCode()) ^ (h >>> 16)

1101 10000001 11101000 ^ 0000 00000000 00001101 ---------------------- 1101 10000001 11100101

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) //1，数组为空，初始化操作，此处resize() 待解析1 n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) /**2,通过key的计算出的hash值与数组长度-1与运算，算出在数组下标位置 * 若该位置为空则创建新节点封装元素值，放在该位置 */ tab[i] = newNode(hash, key, value, null); else { // 若数组下标位置已经有值 Node<K,V> e; K k; //3,首先判断数组位置两个key是否相同，e用来指向存在相同key的节点。 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) //4，key不相同的情况下，判断数组该下标位置连接的是链表还是树节点 //若是树结构，就将该值放入树中(放入树中操作，也会遍历树判断是否存在相同的key的节点，若无相同会以新节点插入树中) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { //数组该下标位置只有1个节点或者链表：这里统一为链表形式 for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { //5，没有找到相同key的元素，在链表后插入新节点 p.next = newNode(hash, key, value, null); /**此处为什么要>=7,因为bincount从0开始递增，当bincount=7时， *此时for循环执行了7次，加上新增加的节点，以及数组下标位置节点 *共7+1+1= 9了，即该数组下标位置链表长度大于8了,需要转化为红黑树 */ if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } //遍历链表比较判断是否存在两个key相同元素 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; //有上面 e= p.next,这里 p有重新被赋值为e，即继续遍历链表下一个元素  p = e; } } // 存在相同的key的元素，可能在数组、链表、树上  if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) //6，覆盖旧值，返回旧值，也可设置仅仅当旧value存在，不为null情况才覆盖原值 e.value = value; afterNodeAccess(e); return oldValue; } } //修改次数+1 ++modCount; //7,判断整个map中元素个数是否大于阈值，大于则扩容，由此可见是先插入元素再判断容量大小是否扩容，区别1.7先扩容再插入新值 if (++size > threshold) resize(); //该方法为空，不用理会 afterNodeInsertion(evict); return null;}

final Node<K,V>[] resize() {
 Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; //1,原来数组容量>0情况 if (oldCap > 0) { //如果数组容量已经为最大值了 2^30,那就仅仅是将扩容阈值修改 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) //1.1 如果原来数组容量>=16,且其2倍小于最大容量(oldCap<<1 等价于 oldCap*2^1） // 阈值也扩容为原来2倍  newThr = oldThr << 1; // double threshold } else if (oldThr > 0) // initial capacity was placed in threshold //1.2 什么情况数组容量=0，阈值>0呢？ //创建HashMap，指定了数组初始容量cap，会将其转换为大于等于cap的最小的2的幂次方的数赋值给threshold,这里即将数组容量赋值 newCap = oldThr; else { // zero initial threshold signifies using defaults //1.3原来数组容量和阈值都为0，即常用的无参构造方式，使用默认容量大小 //阈值根据容量和负载因子算出  newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } //2,newThr = 0情况出现在1.1中，没满足条件扩大为原来2倍 if (newThr == 0) { float ft = (float)newCap * loadFactor; //小于最大容量，则用容量和加载因子乘积，否则为 Integer最大值 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; //3,创建新数组对象 @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; //4,原数组对象不为空，需要将原数组元素移到新数组中 if (oldTab != null) { //遍历旧数组 for (int j = 0; j < oldCap; ++j) { Node<K,V> e; //数组下标位置有元素 if ((e = oldTab[j]) != null) { //直接把该下标位置链表(或红黑树)取出来，1个元素也当做链表看待，原数组该位置置空，只要我们拿着链表头节点/树根节点(e)就行 oldTab[j] = null; if (e.next == null) //该位置只有1个元素，直接与新数组长度hash，确定位置放入新数组 newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) //该位置是一颗红黑树，迁移到新数组 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order //5，重点解析：这里将原数组链表拆分为2条链表放入新数组，那它是怎么拆的呢？ // loHead,loTail(lo 理解为low缩写)分别记录放在新数组下标小的那一条链表的头节点和尾结点, // 同理hiHead，hiTail(hi理解为 hight缩写)放在新数组下标大的位置 Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; // e.hash & oldCap 是什么目的呢？ // e.hash & (oldCap-1)求得是数组下标，e.hash & oldCap  // 是为了获取比oldCap-1更高的那位一是0还是1，是0的就留在原位，是1的话需要增加oldCap。这里不易理解，下面详解 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,扩容前位置23&15= 7 0001 0111 &0000 1111---------0000 0111#2,扩容后位置 23&31= 230001 0111 &0001 1111---------0001 0111/**因为每次扩容都是old数组长度的2倍，那么在要计算在扩容后新数组位置，那么只需要关心key的hash值左边新增计算的那位是0还是1，如上未扩容前23与15与运算，只需关心低4位值，高位无论其是否有1，与运算后都会为0; 而扩容后，15变为31，那么key的hash值影响计算结果位由4位变为5位，因此 e.hash & oldCap的结果就是获取新增的位置，000X 0000,即X的值，0或者1；0运算结果不变，放在原位，1与运算结果会增加一个原数组长度。*/

7 & 7=70000 01110000 0111----------23 & 7=70001 01110000 0111----------31 & 7=70001 11110000 0111----------15 & 7=70000 11110000 0111#可见第4位(从右向左)为1的有15，31，扩容后位置：原有下标+原数组长度

public V get(Object key) { Node<K,V> e; //获取节点赋值给e,e！=null, 返回该键值对的value值 return (e = getNode(hash(key), key)) == null ? null : e.value;}

final Node<K,V> getNode(int hash, Object key) { //传入的hash值与put方法一样的方法，相同规则计算key的hash值 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) { //1，获取数组下标位置的第一个节点，first if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null &&  key.equals(k)))) //2，检查是否为相同的key,是直接返回该节点对象；不是则遍历下一个节点 return first; if ((e = first.next) != null) { //3,下一个节点存在，需判断是红黑树，还是链表 if (first instanceof TreeNode) //3.1红黑树则遍历树获取是否存在与该key相同的节点 return ((TreeNode<K,V>)first).getTreeNode(hash, key); do { //3.2 链表则依次遍历，查找相同的key，找到则返回 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } //数组为空，或者没有找到返回空 return null;}