哪家做网站公司好,广东省网站建设网站,温州建设局网站首页,什么叫网站appHashMap的底层结构
HashMap是基于分离链表法解决散列冲突的动态散列表。
1、在jdk7中#xff0c;使用的是“数组 链表”#xff0c;发生散列冲突的时候键值对会用头插法添加到单链表中#xff1b;
2、在jdk8中#xff0c;使用的是“数组 链表 红黑树”#xff0c;发…HashMap的底层结构
HashMap是基于分离链表法解决散列冲突的动态散列表。
1、在jdk7中使用的是“数组 链表”发生散列冲突的时候键值对会用头插法添加到单链表中
2、在jdk8中使用的是“数组 链表 红黑树”发生散列冲突的时候会使用尾插法添加到单链表中。如果链表的长度大于8且散列表容量大于64的时候会将链表树化为红黑树。在扩容再散列时如果红黑树的长度低于6则会还原为链表。 1HashMap的数组长度保证是2的整数次幂且默认数组容量是16默认装载因子是0.75扩容阈值是12树化阈值是8当一个桶中的元素个数大于等于8时进行树化还原阈值是6当一个桶中的元素个数小于等于6时把树转化为链表。2hashmap的 key 和 value 都支持nullkey为null的键值对会直接映射到数组下表为0的桶中因为null的hash值是0取余映射到数组下标后也是table[0]的桶。3首次加入数据如果数组为空则扩容默认数组容量是16数组容量到达阈值12-24...会扩容至原来容量2倍链表长度大于8且数组容量小于64时同样会扩容至原来容量2倍数组容量到64时则会树化。 源码分析
1、putVal 存放数据
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {HashMap.NodeK, V[] tab;HashMap.NodeK, V p;int n, i;if ((tab table) null || (n tab.length) 0)// 如果数组为null或长度为0则进行扩容首次扩容数组长度为16阈值为12n (tab resize()).length;if ((p tab[i (n - 1) hash]) null)// 如果数组 tab[i]位置上是null则将加入的 key-value 放入此数组节点tab[i] newNode(hash, key, value, null);else {// 数组 tab[i]位置上有值即 pHashMap.NodeK, V e;K k;if (p.hash hash ((k p.key) key || (key ! null key.equals(k))))// tab[i]上元素的hash值和key值 和 新加入元素的hash值 key值都相同; 则 p保存到e中用于后续修改value值e p;else if (p instanceof TreeNode) // 红黑树节点情况e ((HashMap.TreeNodeK, V) p).putTreeVal(this, tab, hash, key, value);else { // 单链表情况尾插for (int binCount 0; ; binCount) {if ((e p.next) null) { // p的下一节点是空的则尾插新元素p.next newNode(hash, key, value, null);if (binCount TREEIFY_THRESHOLD - 1)// 链表上大于8个元素了树化数组长度大于64后才开始树化否则仅扩容16-32-64treeifyBin(tab, hash);break;}if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))// 新加入的元素 和 单链表上元素 hash、key值都相同break;p e; // 前有e p.next,即 p指向p的下一个节点}}if (e ! null) { // e不为空则新加入的元素 hash、key 都重复了则新值替换旧值V oldValue e.value;if (!onlyIfAbsent || oldValue null)e.value value;// 访问节点回调用于 LinkedHashMap默认为空实现afterNodeAccess(e);return oldValue;}}modCount;if (size threshold)// hashmap的元素个数大于阈值12-24....时则进行扩容, 扩容后长度是原来长度的两倍resize();afterNodeInsertion(evict);return null;}2、扩容
final NodeK,V[] resize() {// 定义 旧数组 变量NodeK,V[] oldTab table;// 如果数组为 null 则旧容量置为0// 如数组不为 null 则旧容量为置为 数组的长度划重点数组的长度int oldCap (oldTab null) ? 0 : oldTab.length;// 定义 旧扩容阈值 变量int oldThr threshold;// 定义 新容量 新扩容阈值 变量为 0int newCap, newThr 0;// 1、第一步// 如果旧容量 0表示不是第一次添加元素数组里面有元素if (oldCap 0) {// 极端情况// 如果旧容量 最大容量则此时无法扩容将扩容阈值设置为整数最大值直接返回旧容量// static final int MAXIMUM_CAPACITY 1 30;if (oldCap MAXIMUM_CAPACITY) {threshold Integer.MAX_VALUE;return oldTab;}// 普通情况// oldCap 1 旧容量扩容为原来的两倍// 新容量 最大容量 且 旧容量 默认容量else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY)// 扩容阈值扩大为原来的两倍newThr oldThr 1; // double threshold}// 使用非无参构造方法创建的map第一次插入元素会走到这里else if (oldThr 0)// 初始化容量 置为 扩容阈值newCap oldThr;// 调用无参构造方法创建的map第一次插入元素会走到这里else {// static final int DEFAULT_INITIAL_CAPACITY 1 4; // aka 16// 新容量 默认为 16newCap 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;// 2、第二步// 使用新容量 创建新数组NodeK,V[] newTab (NodeK,V[])new Node[newCap];table newTab;// 如果旧数组不等于 null则将旧数组上的键值对 再散列到新数组上if (oldTab ! null) {// 遍历旧数组上的每个桶for (int j 0; j oldCap; j) {NodeK,V e;// 如果此下标处的桶不为nullif ((e oldTab[j]) ! null) {// 传递给 e 后置为空oldTab[j] null;// 如果这个桶中只有一个元素if (e.next null)// 则计算它在新桶中的位置并把它搬移到新桶中也就是 直接再散列newTab[e.hash (newCap - 1)] e;// 如果是红黑树else if (e instanceof TreeNode)// 以红黑树的方式再散列((TreeNodeK,V)e).split(this, newTab, j, oldCap);// 以链表的形式再散列else { // preserve orderNodeK,V loHead null, loTail null;NodeK,V hiHead null, hiTail null;NodeK,V next;do {next e.next;// 如果元素的哈希值与旧数组长度的按位与运算结果为0将元素添加到低位链表中。// 如果低位链表为空将该元素作为链表的头节点否则将该元素添加到低位链表的尾部。if ((e.hash oldCap) 0) {if (loTail null)loHead e;elseloTail.next e;loTail e;}// 如果元素的哈希值与旧数组长度的按位与运算结果不为0将元素添加到高位链表中。// 如果高位链表为空将该元素作为链表的头节点否则将该元素添加到高位链表的尾部。else {if (hiTail null)hiHead e;elsehiTail.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;}
