Java并发编程HashMap（四）

/**默认的HashMap容器初始化大小16&＃xff08;1右移4位&＃xff09; &＃xff0c;必须是2的幂次方**/
DEFAULT_INITIAL_CAPACITY &＃61; 1 <<4/**最大的容器大小&＃xff08;2的30次方&＃xff09;**/
MAXIMUM_CAPACITY &＃61; 1 <<30/**默认的加载因子&＃xff0c;当HashMap的容量大小超过初始化容量的75%后&＃xff0c;会自动进行扩容操作**/
DEFAULT_LOAD_FACTOR &＃61; 0.75f/**阈值&＃xff0c;当节点数超过8个会自动转化为红黑树**/
TREEIFY_THRESHOLD &＃61; 8/**阈值&＃xff0c;当节点数低于6个时会转化为链表**/
UNTREEIFY_THRESHOLD &＃61; 6/**容器树化的最小表容量大小&＃xff0c;如果没有达到该值&＃xff0c;容器中有太多节点执行resize操作&＃xff0c;MIN_TREEIFY_CAPACITY至少应该是TREEIFY_THRESHOLD的4倍&＃xff0c;
以防止resizing与树化阈值之间的冲突**/
MIN_TREEIFY_CAPACITY &＃61; 64

/**前三个构造函数都不会去初始化hashMap操作&＃xff08;生成node节点&＃xff09;&＃xff0c;在后续的put操作中会去则执行resize操作生成容量为16的hashMap对象&＃xff0c;
第四个构造函数会根据传入的map对象大小生成一个hashMap对象**//**最简单的构造函数&＃xff0c;没有任何参数&＃xff0c;只会设置默认的阈值因子**/
public HashMap() {this.loadFactor &＃61; DEFAULT_LOAD_FACTOR; // all other fields defaulted
}/**自定义初始化容量大小&＃xff0c;默认的阈值因子是系统默认的0.75**/
public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);
}/**自定义初始化容量大小以及阈值因子参数&＃xff0c;构造函数中会进行判断**/
public HashMap(int initialCapacity, float loadFactor) {if (initialCapacity <0)throw new IllegalArgumentException("Illegal initial capacity: " &＃43; initialCapacity);if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity &＃61; MAXIMUM_CAPACITY;if (loadFactor <&＃61; 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " &＃43; loadFactor);this.loadFactor &＃61; loadFactor;this.threshold &＃61; tableSizeFor(initialCapacity);
}
/**传递Map参数来构造hashMap, **/
public HashMap(Mapextends K, ? extends V> m) {this.loadFactor &＃61; DEFAULT_LOAD_FACTOR;putMapEntries(m, false);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {Node[] tab; Node p; int n, i;/**如果table为空&＃xff0c;初始化table对象, 默认生成大小为16&＃xff0c;扩容因子为0.75的hashMap对象**/if ((tab &＃61; table) &＃61;&＃61; null || (n &＃61; tab.length) &＃61;&＃61; 0)n &＃61; (tab &＃61; resize()).length;/**根据key的hashCode计算在table中存放key/value键值对的位置&＃xff08;前提是该位置没有存放其他键值对&＃xff09;**/if ((p &＃61; tab[i &＃61; (n - 1) & hash]) &＃61;&＃61; null)tab[i] &＃61; newNode(hash, key, value, null);/**计算位置已存在键值对时执行**/else {Node e; K k;/**hash值以及key值是否相同**/if (p.hash &＃61;&＃61; hash &&((k &＃61; p.key) &＃61;&＃61; key || (key !&＃61; null && key.equals(k))))e &＃61; p;/**是否是红黑树节点**/else if (p instanceof TreeNode)e &＃61; ((TreeNode)p).putTreeVal(this, tab, hash, key, value);else {/**链表形式将node节点插入到链表的后面&＃xff08;jdk1.7中是将Entry插入到链表的表头&＃xff09;**/for (int binCount &＃61; 0; ; &＃43;&＃43;binCount) {if ((e &＃61; p.next) &＃61;&＃61; null) {p.next &＃61; newNode(hash, key, value, null);/**判断是否超过8个&＃xff0c;超过会转化为红黑树**/if (binCount >&＃61; TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);break;}if (e.hash &＃61;&＃61; hash &&((k &＃61; e.key) &＃61;&＃61; key || (key !&＃61; null && key.equals(k))))break;p &＃61; e;}}/**如果存放新键值对的位置已存在值&＃xff0c;且key值与新键值对相同&＃xff0c;替换value值**/if (e !&＃61; null) { // existing mapping for keyV oldValue &＃61; e.value;if (!onlyIfAbsent || oldValue &＃61;&＃61; null)e.value &＃61; value;afterNodeAccess(e);return oldValue;}}&＃43;&＃43;modCount;/**判断是否需要扩容**/if (&＃43;&＃43;size > threshold)resize();afterNodeInsertion(evict);return null;
}

final Node[] resize() {Node[] oldTab &＃61; table;int oldCap &＃61; (oldTab &＃61;&＃61; null) ? 0 : oldTab.length;int oldThr &＃61; threshold;int newCap, newThr &＃61; 0;/**进行扩容操作**/if (oldCap > 0) {/**如果hashMap容量大小已超过最大值&＃xff08;2^30&＃xff09;&＃xff0c;不在进行扩容&＃xff0c;阈值大小设置为&＃xff08;2^31-1&＃xff09;&＃xff0c;后续都不会在扩容**/if (oldCap >&＃61; MAXIMUM_CAPACITY) {threshold &＃61; Integer.MAX_VALUE;return oldTab;}/**扩容变成原容量的2倍&＃xff0c;阈值也变成2倍**/else if ((newCap &＃61; oldCap <<1) oldCap >&＃61; DEFAULT_INITIAL_CAPACITY)newThr &＃61; oldThr <<1; // double threshold
}/**对应HashMap(int initialCapacity)第一次put操作初始化的时候调用**/else if (oldThr > 0) // initial capacity was placed in thresholdnewCap &＃61; oldThr;/**对应HashMap()第一次put操作初始化的时候调用**/else { // zero initial threshold signifies using defaultsnewCap &＃61; DEFAULT_INITIAL_CAPACITY;newThr &＃61; (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}/**设置阈值**/if (newThr &＃61;&＃61; 0) {float ft &＃61; (float)newCap * loadFactor;newThr &＃61; (newCap float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold &＃61; newThr;&＃64;SuppressWarnings({"rawtypes","unchecked"})/**对于没有初始化的初始化操作&＃xff0c;在调用构造函数是都不会初始化&＃xff0c;只有在put时才会初始化&＃xff08;以map为参数的构造函数除外&＃xff0c;其实也是执行put时初始化&＃xff09;**/Node[] newTab &＃61; (Node[])new Node[newCap];table &＃61; newTab;if (oldTab !&＃61; null) {for (int j &＃61; 0; j j) {Node e;if ((e &＃61; oldTab[j]) !&＃61; null) {oldTab[j] &＃61; null;/**如果没有链表&＃xff0c;直接赋值**/if (e.next &＃61;&＃61; null)newTab[e.hash & (newCap - 1)] &＃61; e;else if (e instanceof TreeNode)((TreeNode)e).split(this, newTab, j, oldCap);else { // preserve order/**数据迁移部分对比&＃xff1a;* 1.jdk1.8中将链表拆分为两个部分&＃xff0c;一个是保存在原位置不变&＃xff0c;一个是扩充前位置&＃43;oldCap的位置&＃xff0c;扩容数据迁移后链表的顺序没有改变&＃xff1b;(1.8的效率更高&＃xff09;* 2.jdk1.7中是通过双重循环遍历&＃xff0c;使用node.hash & &＃xff08;newCapacity - 1&＃xff09;计算扩容后节点的位置&＃xff0c;新节点的加入是存放到链表头&＃xff0c;数据迁移后链表的顺序相反;**//**扩容后依然在扩容前位置的链表节点**/Node loHead &＃61; null, loTail &＃61; null;/**扩容后在扩容前位置&＃43;oldCap位置的链表节点**/Node hiHead &＃61; null, hiTail &＃61; null;Node next;do {next &＃61; e.next;if ((e.hash & oldCap) &＃61;&＃61; 0) {if (loTail &＃61;&＃61; null)loHead &＃61; e;elseloTail.next &＃61; e;loTail &＃61; e;}else {if (hiTail &＃61;&＃61; null)hiHead &＃61; e;elsehiTail.next &＃61; e;hiTail &＃61; e;}} while ((e &＃61; next) !&＃61; null);/**向扩容后的map中存放链表**/if (loTail !&＃61; null) {loTail.next &＃61; null;newTab[j] &＃61; loHead;}if (hiTail !&＃61; null) {hiTail.next &＃61; null;newTab[j &＃43; oldCap] &＃61; hiHead;}}}}}return newTab;
}

final Node getNode(int hash, Object key) {Node[] tab; Node first, e; int n; K k;/**判断table是否为空&＃xff0c;根据传递的key值获取的tab是否为空&＃xff0c;此时获取的是链表的链表头结点**/if ((tab &＃61; table) !&＃61; null && (n &＃61; tab.length) > 0 &&(first &＃61; tab[(n - 1) & hash]) !&＃61; null) {/**判断表头节点是否是获取的对象**/if (first.hash &＃61;&＃61; hash && // always check first node((k &＃61; first.key) &＃61;&＃61; key || (key !&＃61; null && key.equals(k))))return first;/**遍历链表获取节点**/if ((e &＃61; first.next) !&＃61; null) {if (first instanceof TreeNode)return ((TreeNode)first).getTreeNode(hash, key);do {if (e.hash &＃61;&＃61; hash &&((k &＃61; e.key) &＃61;&＃61; key || (key !&＃61; null && key.equals(k))))return e;} while ((e &＃61; e.next) !&＃61; null);}}return null;
}

final Node removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {Node[] tab; Node p; int n, index;/**判断table是否为空以及删除的key在table中是否存在**/if ((tab &＃61; table) !&＃61; null && (n &＃61; tab.length) > 0 &&(p &＃61; tab[index &＃61; (n - 1) & hash]) !&＃61; null) {Node node &＃61; null, e; K k; V v;/**删除节点是链表头节点**/if (p.hash &＃61;&＃61; hash &&((k &＃61; p.key) &＃61;&＃61; key || (key !&＃61; null && key.equals(k))))node &＃61; p;else if ((e &＃61; p.next) !&＃61; null) {if (p instanceof TreeNode)node &＃61; ((TreeNode)p).getTreeNode(hash, key);else {/**删除节点非链表头的节点**/do {if (e.hash &＃61;&＃61; hash &&((k &＃61; e.key) &＃61;&＃61; key ||(key !&＃61; null && key.equals(k)))) {node &＃61; e;break;}p &＃61; e;} while ((e &＃61; e.next) !&＃61; null);}}/**执行删除操作&＃xff0c;区分是否在表头**/if (node !&＃61; null && (!matchValue || (v &＃61; node.value) &＃61;&＃61; value ||(value !&＃61; null && value.equals(v)))) {if (node instanceof TreeNode)((TreeNode)node).removeTreeNode(this, tab, movable);/**链表头结点的删除**/else if (node &＃61;&＃61; p)tab[index] &＃61; node.next;/**非链表头结点的删除**/elsep.next &＃61; node.next;&＃43;&＃43;modCount;--size;afterNodeRemoval(node);return node;}}return null;
}