HashMap 1.8
1、构造函数:赋值负载因子0.75,当负载因子大于0.75时就会发送扩容
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted }
2、put方法,可以看到我们要看的时putVal方法
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }
3、先看hash(key)方法,也就是HashMap使用的hash算法
>>>是无符号右移,为什么要右移动16位,首先hashcode返回的是int, java里面是32位。
再看看取模算法,可以看后面的代码,它使用的是 (总容量 & hash),这样会导致高位失效,也就是只有地位参与运算。
比如容量为7,那么hash = 1111(二进制) = 15 和 hash = 11111(二进制) =31 最终的运算结果都是0。
右移动16位后hash的生成,低16位参与了一次高16位于低16位的运算,高16位不变。减少冲突的可能性,虽然我上面的那个例子没有解决。
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
4、接着看putVal方法
/** * hash : 生成的hash * key :key * value :值 * onlyIfAbsent : true时,存在时不替换 * evict: false时,这里我也没看懂,hashMap里面没有用这个参数 * 返回:很少用,原来的值 */ 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; // 当前节点key是一样的 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) // -1 for 1st //转成红黑树 treeifyBin(tab, hash); break; } //如果key 相关,判断逻辑和上面一样的 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } // 如果存在相同的key if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; // 触发节点访问后动作,linkhashMap有 afterNodeAccess(e); return oldValue; } } // ++modCount; // 如果大小大于标准容量后,进行rehash if (++size > threshold) resize(); // 触发节点插入后动作,linkhashMap有 afterNodeInsertion(evict); return null; }
5、看看里面几个重要的方法。
5.1 初始化hash,和rehash都是下面这个。
这里容量扩充到2倍,很巧秒,减少了很多的计算,见下面的注释分析。
final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; // 容量大于0 if (oldCap > 0) { //大于最大容量,直接扩充到Int最大值 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } // 新容量 = 2 * 老容量 ,新容量小于最大容量,老容量大于初始容量 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) 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; 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"}) //构建新的table 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 { // preserve order Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; //结果只能为1或者0,表示高位为0,不影响,位置不变 if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } // 高位为1,影响,并在对应位置为+原始容量 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; }
插入树
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v) { Class<?> kc = null; boolean searched = false; // 找到根节点 TreeNode<K,V> root = (parent != null) ? root() : this; for (TreeNode<K,V> p = root;;) { int dir, ph; K pk; //大于 if ((ph = p.hash) > h) dir = -1; // 小于 else if (ph < h) dir = 1; // key相同,hashcode相同,直接返回 else if ((pk = p.key) == k || (k != null && k.equals(pk))) return p; // hashcode相同,key不相同,如果没有实现compara,或者实现了,并且compara相同 else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0) { if (!searched) { TreeNode<K,V> q, ch; searched = true; if (((ch = p.left) != null && (q = ch.find(h, k, kc)) != null) || ((ch = p.right) != null && (q = ch.find(h, k, kc)) != null)) return q; } dir = tieBreakOrder(k, pk); } TreeNode<K,V> xp = p; // 到叶子节点插入 if ((p = (dir <= 0) ? p.left : p.right) == null) { Node<K,V> xpn = xp.next; TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn); if (dir <= 0) xp.left = x; else xp.right = x; xp.next = x; x.parent = x.prev = xp; if (xpn != null) ((TreeNode<K,V>)xpn).prev = x; moveRootToFront(tab, balanceInsertion(root, x)); return null; } } }
标签:分析,Node,hash,HashMap,int,else,源码,key,null From: https://www.cnblogs.com/minblog/p/16656351.html