摘要:否则,如果中的节点太多,则会调整表的大小。应该至少为,以避免调整大小和树化阈值之间的冲突。
常量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //默认初始容量 (必须是2的幂,用左移动) static final int MAXIMUM_CAPACITY = 1 << 30;//最大容量,如果隐式指定更高的值,则使用该容量(必须是2的幂且小于等于1 << 30) static final float DEFAULT_LOAD_FACTOR = 0.75f;//加载因子(负载系数)(用来衡量HashMap满的程度)(默认0.75f) static final int TREEIFY_THRESHOLD = 8;//(链表转树的阈值) static final int UNTREEIFY_THRESHOLD = 6;//(树转链表的阈值) static final int MIN_TREEIFY_CAPACITY = 64;//容器可以树化的最小容量。 (否则,如果bin中的节点太多,则会调整表的大小。)应该至少为4 * TREEIFY_THRESHOLD,以避免调整大小和树化阈值之间的冲突。基本哈希bin节点Node
static class Node静态工具类(方法) hash(Object key)implements Map.Entry { final int hash;//哈希值 final K key;//存储键 V value;//存储值 Node next;//下一个节点 Node(int hash, K key, V value, Node 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; } public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value);//键值的hash与上存储值的hash,Objects.hashCode()入参为null返回0 } public final V setValue(V newValue) {//设置值并返回旧值 V oldValue = value; value = newValue; return oldValue; } public final boolean equals(Object o) { if (o == this)//内存地址相同直接返回true return true; if (o instanceof Map.Entry) {//如果是Entry 的子类 Map.Entry,?> e = (Map.Entry,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue()))//调用当前节点key值的equal方法和当前节点value值的equal方法,结果与 return true; } return false; } }
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//key的hash值和key的hash值的高16位做异或(>>>左边高位补0)(任何数跟0异或都是其本身)(所以结果是:也就是高十六位+高十六位^低十六位) }
范例
hash(-10) -10.hashCode: 1111111111111111_1111111111110110 -10.hashCode>>>16: 0000000000000000_1111111111111111 return: 1111111111111111_0000000000001001comparableClassFor 如果它的形式为“class C implements Comparable
static Class> comparableClassFor(Object x) { if (x instanceof Comparable) {//如果是比较器子类 Class> c; Type[] ts, as; ParameterizedType p; if ((c = x.getClass()) == String.class) // bypass checks return c;//如果是String返回String类 if ((ts = c.getGenericInterfaces()) != null) {//如果实现了接口 for (Type t : ts) {//循环实现的接口 if ( (t instanceof ParameterizedType) && ((p = (ParameterizedType) t).getRawType() == Comparable.class) && (as = p.getActualTypeArguments()) != null && as.length == 1 && as[0] == c ) // type arg is c return c; } } } return null;//不是比价器子类 }compareComparables() 如果x匹配kc(k的筛选可比类),则返回k.compareTo(x),否则返回0。
@SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable static int compareComparables(Class> kc, Object k, Object x) { return (x == null || x.getClass() != kc ? 0 : ((Comparable)k).compareTo(x)); }tableSizeFor 返回给定目标容量的两个大小的幂(返回能装下传入参数的大小,且为2的次方)
static final int tableSizeFor(int cap) { int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);//Integer.numberOfLeadingZeros返回左边开会连续的0个数 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }
Integer.numberOfLeadingZeros()返回左边最高位开始0的个数
计算范例 tableSizeFor(5)
n = -1 >>> Integer.numberOfLeadingZeros(5-1) -1: 11111111_11111111_11111111_11111111 5-1=4: 00000000_00000000_00000000_00000100 Integer.numberOfLeadingZeros(5-1):29 -1>>>29: 00000000_00000000_00000000_00000111 n=7 n>0 n变量 transient Node构造方法 HashMap()(默认的负载因子是0.75f)[] table;//哈希桶数组(该表在首次使用时初始化) transient Set > entrySet;//保持缓存的entrySet() AbstractMap字段用于keySet()和values() transient int size;//此映射中包含的键 - 值映射的数量 transient int modCount;//此HashMap已被结构修改的次数 int threshold;//下一次需要扩容时的大小(capacity * load factor)(初值为0) final float loadFactor;//哈希表的加载因子 public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // 所有其他属性都是默认的(DEFAULT_LOAD_FACTOR = 0.75f) }HashMap(int initialCapacity)(自定义容量)(通过tableSizeFor来计算2的次方的容量大小)public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR);//(DEFAULT_LOAD_FACTOR = 0.75f) }HashMap(int initialCapacity, float loadFactor)public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0)//容量小于0,抛出异常 throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY)//容量大于最大容量1 << 30 initialCapacity = MAXIMUM_CAPACITY;//则使用最大容量 if (loadFactor <= 0 || Float.isNaN(loadFactor))//如果负载因子小于0或者不是数字,抛出异常 throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor;//赋值负载因子 this.threshold = tableSizeFor(initialCapacity);//计算容量,为2的幂 }HashMap(Map extends K, ? extends V> m)根据一个map构造一个mappublic HashMap(Map extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR;//默认的负载因子 putMapEntries(m, false); }putMapEntries(Map extends K, ? extends V> m, boolean evict)实现Map.putAll和Map构造函数final void putMapEntries(Map extends K, ? extends V> m, boolean evict) { int s = m.size();//获取m映射数量 if (s > 0) {//长度大于0 if (table == null) { //表是空的(没有数据) float ft = ((float)s / loadFactor) + 1.0F;//按照默认负载因子比例计算出的大小+1 int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);//小于最大容量就使用ft计算,大于最大容量使用最大容量计算 if (t > threshold)//如果超过扩容阈值,那么就重新计算扩容阈值 threshold = tableSizeFor(t);//重新计算扩容阈值(2的幂) } else if (s > threshold)//如果表不是空的,且大小大于扩容阈值 resize();//进行扩容 for (Map.Entry extends K, ? extends V> e : m.entrySet()) {//循环插入 K key = e.getKey();//获取key V value = e.getValue();//获取value putVal(hash(key), key, value, false, evict); } } }resize()扩容final NodeputVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) 放置值[] resize() { Node [] oldTab = table;//旧的表 int oldCap = (oldTab == null) ? 0 : oldTab.length;//不为空的话赋值为旧表数据量 int oldThr = threshold;//获取扩容的阈值 int newCap, newThr = 0; if (oldCap > 0) {//如果旧表不为空 if (oldCap >= MAXIMUM_CAPACITY) {//如果旧表数据量大于最大容量 threshold = Integer.MAX_VALUE;//扩容阈值设置成0x7fffffff(1111111111111111111111111111111) return oldTab;//返回旧的数据表 } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY&&oldCap >= DEFAULT_INITIAL_CAPACITY)//否则,两倍大小小于最大容量,且旧的空间大于初始化空间 newThr = oldThr << 1; // 新的阈值为旧的阈值两倍 } else if (oldThr > 0) //旧表为空,且旧表阈值>0 newCap = oldThr;//初始容量被置于阈值 else { //旧表为空,且旧表阈值<0 newCap = DEFAULT_INITIAL_CAPACITY;//默认的空间 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//默认的阈值 }//if (oldCap > 0)结束 if (newThr == 0) {//如果新的阈值等于0 float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr;//重新赋值阈值 @SuppressWarnings({"rawtypes","unchecked"}) Node [] newTab = (Node [])new Node[newCap]; table = newTab; if (oldTab != null) {//有旧的数据 for (int j = 0; j < oldCap; ++j) {// 把每个哈希桶里的值都移动到新的哈希桶中 Node e; if ((e = oldTab[j]) != null) {//哈希桶位不为空 oldTab[j] = null;//原位置空 if (e.next == null)//如果这个桶位只有这一个元素(没有next) newTab[e.hash & (newCap - 1)] = e;//用新的长度取模,数据放置位置 else if (e instanceof TreeNode)//如果是红黑树 ((TreeNode )e).split(this, newTab, j, oldCap); else { //如果是链表 Node loHead = null, loTail = null;//低位头尾 Node hiHead = null, hiTail = null;//高位头尾 Node next; do { next = e.next; 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; } }//(e.next == null)的else结尾 }//if ((e = oldTab[j]) != null)结尾 }// for (int j = 0; j < oldCap; ++j)结尾 }//if (oldTab != null)结尾 return newTab; } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node[] tab; Node p; int n, i; if ((tab = table) == null || (n = tab.length) == 0)//如果桶是空的,或者桶的长度是0 n = (tab = resize()).length;//扩容 if ((p = tab[i = (n - 1) & hash]) == null)//取模桶位是空的 tab[i] = newNode(hash, key, value, null);//直接赋值 else {//存在长链或红黑树 Node e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))//和链表的第一个值同值,进行覆盖 e = p; else if (p instanceof TreeNode)//红黑树 e = ((TreeNode )p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) {//binCount为下标指针循环链表 if ((e = p.next) == null) {//循环到链表的末尾(next为空) p.next = newNode(hash, key, value, null);//把插入的节点作为链表的末尾的下一个节点 if (binCount >= TREEIFY_THRESHOLD - 1) //如果达到树化的阈值,那么转化为树 treeifyBin(tab, hash); break;//结束循环 } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))//插入的节点和链表某一个节点相同,直接跳出 break; p = e;//循环指针p移到下一位 } } if (e != null) { //已存在映射,覆盖 V oldValue = e.value;//获取旧值 if (!onlyIfAbsent || oldValue == null) e.value = value;//赋值 afterNodeAccess(e);//后期回调操作 return oldValue; } } ++modCount; if (++size > threshold)//是否达到扩容阈值 resize(); afterNodeInsertion(evict);//后期回调操作 return null; }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/74959.html
摘要:当链表长度即将超过阀值,会把链表转化为红黑树。然后再判断是链表还是红黑树如果值相同,并且相同表示数组中第一个元素即为相同的将数组中第一个元素赋值给如果当前元素类型为表示为红黑树,返回待存放的。 前提:学习HashMap的底层代码之前,首先要对数据结构要个大致的了解。其中重点了解数组,链表,树的概念和用法。 一.图示分析HashMap的结构 (1)图示为JDK1.8之前的HashMap结...
摘要:为了避免一篇文章的篇幅过长,于是一些比较大的主题就都分成几篇来讲了,这篇文章是笔者所有文章的目录,将会持续更新,以给大家一个查看系列文章的入口。 前言 大家好,笔者是今年才开始写博客的,写作的初衷主要是想记录和分享自己的学习经历。因为写作的时候发现,为了弄懂一个知识,不得不先去了解另外一些知识,这样以来,为了说明一个问题,就要把一系列知识都了解一遍,写出来的文章就特别长。 为了避免一篇...
摘要:底层基于拉链式的散列结构,并在中引入红黑树优化过长链表的问题。在其之上,通过维护一条双向链表,实现了散列数据结构的有序遍历。 原文地址 LinkedHashMap LinkedHashMap继承自HashMap实现了Map接口。基本实现同HashMap一样,不同之处在于LinkedHashMap保证了迭代的有序性。其内部维护了一个双向链表,解决了 HashMap不能随时保持遍历顺序和插...
阅读 2458·2021-11-19 09:40
阅读 3584·2021-11-17 17:08
阅读 3784·2021-09-10 10:50
阅读 2213·2019-08-27 10:56
阅读 1942·2019-08-27 10:55
阅读 2637·2019-08-26 12:14
阅读 994·2019-08-26 11:58
阅读 1493·2019-08-26 10:43