深圳建站公司兴田德润电话多少,家居网站建设,云速成美站,wordpress怎么换空间1、一些常量的定义
这里针对MIN_TREEIFY_CAPACITY 这个值进行解释一下。
java8里面#xff0c;HashMap 的数据结构是数组 #xff08;链表或者红黑树#xff09;#xff0c;每个数组节点下可能会存在链表和红黑树之间的转换#xff0c;当同一个索引下面的节点超过8个时…1、一些常量的定义
这里针对MIN_TREEIFY_CAPACITY 这个值进行解释一下。
java8里面HashMap 的数据结构是数组 链表或者红黑树每个数组节点下可能会存在链表和红黑树之间的转换当同一个索引下面的节点超过8个时首先会看当前数组长度如果大于64则会发生链表向红黑树的 转换否则不会转换而是扩容。 // 默认的初始化长度 16static final int DEFAULT_INITIAL_CAPACITY 1 4; // aka 16// 默认的最大容量 2^30static final int MAXIMUM_CAPACITY 1 30;// 默认的扩容因子static final float DEFAULT_LOAD_FACTOR 0.75f;// 链表转为树的阈值static final int TREEIFY_THRESHOLD 8;// 树转为链表的阈值static final int UNTREEIFY_THRESHOLD 6;static final int MIN_TREEIFY_CAPACITY 64;// map已存节点的数量transient int size;// 修改次数 transient int modCount;// 扩容阈值 当size达到这个值的时候hashmap开始扩容int threshold;// 加载因子 threshold 容量 * loadFactorfinal float loadFactor; 2、构造器
HashMap提供了三个构造器。 // 无参构造器使用默认加载因子 0.75public HashMap() {this.loadFactor DEFAULT_LOAD_FACTOR; // all other fields defaulted}// 只传入初始化容量也会使用默认加载因子 0.75public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);}// 同时传入初始化容量和加载因子 初始化容量要大于0且不能超过最大容量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;// 初始化的容量先赋值给了threshold 暂存。this.threshold tableSizeFor(initialCapacity);}
注意看使用带参构造器 会调用 tableSizeFor(initialCapacity); 这个方法是干嘛的呢其实就是为了计算初始化容量。HashMap规定其容量必须是2的N次方 不传初始化容量就取默认值16传了初始化容量则初始化容量设置为大于等于该数值的 一个最小的2的N次方 比如传入了7不是2的N次方那么取比他大的最小的2的N次方就是8比如传入了8刚好是2的N次方那就取8比如传入了9不是2的N次方那么取比他大的最小的2的N次方就是16 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;}
或等于操作 a | b 其实就是 a a | b。 无符号右移操作a b 就表示将a向右移动b位左边空出来的用0补充右边的被丢弃 那么 n | n 1 操作得到的结果就是最高位和次高位的结果为1--- n 的前两位为1
n | n 2 操作之后 --- n的前四位为1
.... 一通操作之后得到的值是一个低位全是1的值。然后返回的时候1得到的值就是一个比n大的2的N次方。而开头的 int n cap - 1 是为了解决本身就是2的N次方的场景。 3、插入操作
3.1、插入操作的具体流程 插入前首先判断数组是否为空如果为空就进行初始化计算key的hash值然后和数组长度-1 进行 运算获取在数组中的索引位置 当前位置不存在元素就直接创建新节点放在当前索引位置当前位置元素存在就走后续的逻辑判断当前坐标下头节点的hash值是否和 key的hash相等如果相等就进行替换还要判断一个控参 onlyIfAbsent这个为false的时候才会替换最常用的put操作这个值就是false 如果不相等判断当前是链表还是红黑树 如果是链表遍历链表节点并统计节点个数 如果找到了相同的key就进行覆盖操作如果没有找到相同key就将节点添加到链表最后面并判断是否超过8个节点如果大于等于8就要链表转红黑树操作。如果是红黑树找到红黑树根节点从根节点开始遍历 找到相同的key就进行替换找不到相同的key就放到相应的位置然后进行红黑树插入平衡调整插入完成之后判断当前节点数目是否超过扩容阈值如果超过就进行扩容。 public V put(K key, V value) {/*** 首先计算出了key的hash 值*/return putVal(hash(key), key, value, false, true);
}final V putVal ( int hash, K key, V value,boolean onlyIfAbsent, boolean evict){HashMap.NodeK, V[] tab;HashMap.NodeK, V p;int n, i;/*** 判断数组是否为空为空则进行数组初始化 * --- tab resize() 然后获取数组的长度*/if ((tab table) null || (n tab.length) 0) {n (tab resize()).length;}/*** 计算当前节点要插入数组的索引的位置 --- (n - 1) hash* 如果索引处不存在节点就新创建节点放到索引的位置*/if ((p tab[i (n - 1) hash]) null) {tab[i] newNode(hash, key, value, null);}/*** 如果索引处存在节点走这个逻辑*/else {HashMap.NodeK, V e;K k;if (p.hash hash ((k p.key) key || (key ! null key.equals(k)))) {/*** 进入这个分支说明要插入的节点和头节点的key相同*/e p;} else if (p instanceof HashMap.TreeNode) {/*** 说明头节点是红黑树了要把这个新节点插入到红黑树中涉及到新节点的插入红黑树的平衡调整等*/e ((HashMap.TreeNodeK, V) p).putTreeVal(this, tab, hash, key, value);} else {/*** 说明头节点是链表节点遍历链表*/for (int binCount 0; ; binCount) {if ((e p.next) null) {/*** 遍历到最后了创建新节点插入到尾端* 还要判断节点是否超过8个超过了要转化为红黑树*/p.next newNode(hash, key, value, null);if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1st{treeifyBin(tab, hash);}break;}if (e.hash hash ((k e.key) key || (key ! null key.equals(k)))) {/*** 找到了相同key的value*/break;}p e;}}/*** e不为空说明有key相同的情况替换成新的value然后直接返回旧的节点* 因为节点数目不存在变化因此不需要进行扩容判断*/if (e ! null) { // existing mapping for keyV oldValue e.value;// onlyIfAbsent的判断if (!onlyIfAbsent || oldValue null) {e.value value;}afterNodeAccess(e);return oldValue;}}modCount;/*** 如果当前节点超过了扩容阈值就进行扩容然后返回null*/if (size threshold) {resize();}afterNodeInsertion(evict);return null;
} 3.2、 key的hash值是怎么计算的为什么要这么计算
如果key为空就直接返回0不为空将 key的hashcode 和 hashcode左移16位进行 运算---- 左移16位主要就是为了将hash的高位也参与到hash计算中减少hash冲突。 static final int hash(Object key) {int h;return (key null) ? 0 : (h key.hashCode()) ^ (h 16);} 3.3、resize扩容流程介绍
首先会对老数组进行一系列的校验大致分为 老数组为空就设置一下数组长度和扩容阈值新建数组然后返回老数组不为空校验老数组长度如果长度超过上限扩容阈值修改为int最大值返回否则容量、扩容阈值变为原来的2倍接着开始遍历老数组 当前坐标下没有节点就继续遍历当前坐标只有一个节点计算hash值然后放到新数组对应位置当前坐标是链表走链表逻辑 遍历链表节点计算 e.hash oldCap 这个值如果是0说明扩容后在新数组的坐标和老数组一样如果为1 说明扩容后在新数组的坐标应该是 老数组坐标 扩容长度因此通过计算这个值可以将链表节点分为高位节点和低位节点定义高位和低位两个链表不断将链表节点放在这两个新链表尾端然后低位链表放在新数组的i 坐标位置高位链表放在新数组ioldcap的位置当前坐标是红黑树走红黑树的逻辑 因为维护红黑树的时候也维护了一个双向链表因此通过 e.prev e.next就可以遍历整个树 也就是说遍历链表就等于遍历树同样是将元素分别放在低位链表和高位链表中并计算每个链表的长度低位链表的头节点放在新数组的i坐标位置然后维护链表的红黑树结构维护前会判断高位链表是否有值如果为空说明树结构没有被破坏而是直接迁移到新数组中了这个时候就可以不用重新维护树结构了高位链表头节点放在新数组ioldcap的位置维护树结构同3
注意jdk1.8中hashmap的扩容链表节点处理只遍历了一次而ConcurrentHashMap中遍历了两次。
final HashMap.NodeK, V[] resize() {HashMap.NodeK, V[] oldTab table;// 临时存储老的数组长度和老的扩容阈值int oldCap (oldTab null) ? 0 : oldTab.length;int oldThr threshold;// 定义新的数组长度和新的扩容阈值int newCap, newThr 0;// oldCap 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 defaultsnewCap 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);}// hashmap 初始化的时候是将数组初始化长度赋值给了threshold这里开始才是变成扩容阈值。threshold newThr;// 创建新的数组并将新数组赋值给tableHashMap.NodeK, V[] newTab (HashMap.NodeK, V[]) new HashMap.Node[newCap];table newTab;// 老数组不为空就走扩容逻辑否则就直接返回新创建的数组了if (oldTab ! null) {// 对老数组开始遍历for (int j 0; j oldCap; j) {HashMap.NodeK, V e;// 数组的坐标节点为空说明没数据直接遍历下个坐标if ((e oldTab[j]) ! null) {oldTab[j] null;// 只有个节点直接取出该节点计算hash值放到新数组中if (e.next null) {newTab[e.hash (newCap - 1)] e;}// 当前是红黑树执行红黑树扩容逻辑else if (e instanceof HashMap.TreeNode) {((HashMap.TreeNodeK, V) e).split(this, newTab, j, oldCap);}// 当前是链表执行链表扩容逻辑else { // preserve order// 定义高位链表和低位链表HashMap.NodeK, V loHead null, loTail null;HashMap.NodeK, V hiHead null, hiTail null;HashMap.NodeK, V next;// 遍历链表do {next e.next;// e.hash oldCap 可以计算出当前节点应该放在高位还是低位if ((e.hash oldCap) 0) {// 将遍历到的节点放在loTail尾部// loHead指向低位节点的头节点if (loTail null) {loHead e;} else {loTail.next e;}loTail e;} else {// 将遍历到的节点放在hiTail尾部// hiHead指向高位节点的头节点if (hiTail null) {hiHead e;} else {hiTail.next e;}hiTail e;}} while ((e next) ! null);// 低位链表的头节点放在 新数组的原index中if (loTail ! null) {loTail.next null;newTab[j] loHead;}// 高位链表的头节点放在 新数组的原index oldCap 中if (hiTail ! null) {hiTail.next null;newTab[j oldCap] hiHead;}}}}}return newTab;
}final void split(HashMapK, V map, HashMap.NodeK, V[] tab, int index, int bit) {// ((TreeNodeK,V)e).split(this, newTab, j, oldCap); 这个this 就是数组中取出来的第一个元素也就是树的头节点HashMap.TreeNodeK, V b this;// 设置低位首节点和低位尾节点,高位首节点和高位尾节点HashMap.TreeNodeK, V loHead null, loTail null;HashMap.TreeNodeK, V hiHead null, hiTail null;// 这两个值用于记录低位坐标和高位坐标节点的数目int lc 0, hc 0;// 从根节点开始对整个树进行遍历我们介绍了红黑树其实也维护了双向链表因此通过 e.prev e.next就可以遍历整个树for (HashMap.TreeNodeK, V e b, next; e ! null; e next) {next (HashMap.TreeNodeK, V) e.next;e.next null;// bit传入的就是oldCap,也就是旧数组的长度通过hash 运算就可以判断是放在新数组的低位坐标还是高位坐标if ((e.hash bit) 0) {if ((e.prev loTail) null) {loHead e;} else {loTail.next e;}loTail e;lc;} else {if ((e.prev hiTail) null) {hiHead e;} else {hiTail.next e;}hiTail e;hc;}}// 低位坐标处理逻辑if (loHead ! null) {// 低位节点数目小于等于6就转为链表if (lc UNTREEIFY_THRESHOLD) {tab[index] loHead.untreeify(map);}// 否则还是红黑树结构else {// 链表头节点赋值给 tab[index]tab[index] loHead;if (hiHead ! null)// 对低位的链表维护红黑树结构// 为什么加一个hiHead ! null 判断呢因为如果原来的元素全部都分到了低位节点那说明树结构没有被破坏就不需要维护了{loHead.treeify(tab);}}}// 高位和低位的处理一样if (hiHead ! null) {if (hc UNTREEIFY_THRESHOLD) {tab[index bit] hiHead.untreeify(map);} else {tab[index bit] hiHead;if (loHead ! null) {hiHead.treeify(tab);}}}
} 3.4 链表转红黑树 final void treeifyBin(HashMap.NodeK, V[] tab, int hash) {int n, index;HashMap.NodeK, V e;// 如果数组为空或者数组长度小于64就先尝试扩容因为链表转树的消耗太大了if (tab null || (n tab.length) MIN_TREEIFY_CAPACITY) {resize();} // 先拿到当前坐标下的头节点 赋值给 eelse if ((e tab[index (n - 1) hash]) ! null) {// 定义头节点和尾节点HashMap.TreeNodeK, V hd null, tl null;// 遍历链表do {// 将链表节点转化为红黑树节点HashMap.TreeNodeK, V p replacementTreeNode(e, null);if (tl null) {// 最开始遍历的时候尾节点肯定为空就把跟节点指向当前节点hd p;} else {// 双向链表将前后节点关联起来p.prev tl;tl.next p;}// 当前节点设置为尾节点tl p;} while ((e e.next) ! null);// 截止到目前把链表中所有的node对象转变为了红黑树节点单向链表变成了双向链表// 把转换后的双向链表替换原来位置上的单向链表if ((tab[index] hd) ! null) {// 树化操作hd.treeify(tab);}}
}final void treeify(HashMap.NodeK, V[] tab) {HashMap.TreeNodeK, V root null;// 因为是调用的hd.treeify(tab)因此这里的this就是双向链表的头节点这里先赋值给了临时变量x// 开始循环这个双向链表了x就是循环的元素next就是下一个节点元素for (HashMap.TreeNodeK, V x this, next; x ! null; x next) {next (HashMap.TreeNodeK, V) x.next;// 当前节点左右孩子都设置为空x.left x.right null;if (root null) {// 第一次进来根节点肯定是空将头节点设置为根节点染色黑x.parent null;x.red false;root x;} // 第一次以后的循环都走下面的分支了else {// 定义当前节点的key 和 hashK k x.key;int h x.hash;Class? kc null;// 开始遍历树结构了for (HashMap.TreeNodeK, V p root; ; ) {// ph 和 pk 定义当前树节点的 hash 和 key ,通过hash判断当前节点要放在树的左边还是右边// dir代表 往树左边放还是右边放int dir, ph;K pk p.key;if ((ph p.hash) h) {dir -1;} else if (ph h) {dir 1;} // hash相等的时候继续一系列的判断最终得到direlse if ((kc null (kc comparableClassFor(k)) null)|| (dir compareComparables(kc, k, pk)) 0) {dir tieBreakOrder(k, pk);}HashMap.TreeNodeK, V xp p;// dir 0 说明是在左侧否则是在右侧// 只有保证当前树节点没有对应的左孩子或者右孩子的时候才会将当前节点挂上去否则继续循环遍历树结构if ((p (dir 0) ? p.left : p.right) null) {x.parent xp;if (dir 0) {xp.left x;} else {xp.right x;}// 红黑树平衡操作root balanceInsertion(root, x);// 当前节点已经插入红黑树中了可以跳出当前循环遍历链表的下一个节点break;}}}}// 把root节点放在当前坐标位置moveRootToFront(tab, root);
}/*** 我们要明确红黑树节点不但维护了树结构还维护了双向链表的结构* 这个方法的作用就是* 1、将树的根节点赋值给tab[i]* 2、将这个节点变成双向链表的头节点*/
static K, V void moveRootToFront(HashMap.NodeK, V[] tab, HashMap.TreeNodeK, V root) {int n;if (root ! null tab ! null (n tab.length) 0) {// 通过根节点 hash计算在数组中的索引位置int index (n - 1) root.hash;// 取到当前索引的第一个节点HashMap.TreeNodeK, V first (HashMap.TreeNodeK, V) tab[index];// 如果root节点和 当前索引位置第一个节点不一样就把root节点放在当前坐标位置// 同时要维护双向链表将root节点变成双向链表的第一个节点。if (root ! first) {HashMap.NodeK, V rn;tab[index] root;// 将root节点变成双向链表的第一个节点。HashMap.TreeNodeK, V rp root.prev;if ((rn root.next) ! null) {((HashMap.TreeNodeK, V) rn).prev rp;}if (rp ! null) {rp.next rn;}if (first ! null) {first.prev root;}root.next first;root.prev null;}assert checkInvariants(root);}
}
4、删除操作
数组没有初始化或者对应下标节点为空说明没有该元素直接返回null查找node红黑树或者链表结构删除node红黑树或者链表结构 --- 删除节点的时候即便树的元素小于等于6也不会转为链表在代码里面没看到只在扩容的时候会有转换操作。
/*** 删除方法主要介绍以下两个参数* param matchValue true只有值也相同的时候才删除* param movable true删除后移动节点树结构的时候会用到一般为true*/
final HashMap.NodeK, V removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {HashMap.NodeK, V[] tab;HashMap.NodeK, V p;int n, index;// 组数没有初始化或者对应坐标下面没有元素直接返回null了if ((tab table) ! null (n tab.length) 0 (p tab[index (n - 1) hash]) ! null) {// node记录要删除的元素HashMap.NodeK, V node null, e;K k;V v;// 找要删除的元素赋值给nodeif (p.hash hash ((k p.key) key || (key ! null key.equals(k)))) {node p;} else if ((e p.next) ! null) {if (p instanceof HashMap.TreeNode) {// 从树中查找节点node ((HashMap.TreeNodeK, V) p).getTreeNode(hash, key);} else {// 从链表中查找节点 链表结构时p是node的前置节点do {if (e.hash hash ((k e.key) key || (key ! null key.equals(k)))) {node e;break;}p e;} while ((e e.next) ! null);}}if (node ! null (!matchValue || (v node.value) value || (value ! null value.equals(v)))) {// node不为空的时候删除节点if (node instanceof HashMap.TreeNode) {((HashMap.TreeNodeK, V) node).removeTreeNode(this, tab, movable);} else if (node p) {tab[index] node.next;} else {p.next node.next;}// 修改次数加1size减一返回删除的nodemodCount;--size;afterNodeRemoval(node);return node;}}return null;
}
