html网站支付链接怎么做的,深圳网站建设公司哪里有,阳泉市编办网站三基建设,wordpress seo知乎为什么学习 HashMap 源码#xff1f;作为一名 java 开发#xff0c;基本上最常用的数据结构就是 HashMap 和 List#xff0c;jdk 的 HashMap 设计还是非常值得深入学习的。无论是在面试还是工作中#xff0c;知道原理都对会我们有很大的帮助。本篇的内容较长#xff0c;建… 为什么学习 HashMap 源码作为一名 java 开发基本上最常用的数据结构就是 HashMap 和 Listjdk 的 HashMap 设计还是非常值得深入学习的。无论是在面试还是工作中知道原理都对会我们有很大的帮助。本篇的内容较长建议先收藏再细细品味。不同于网上简单的源码分析更多的是实现背后的设计思想。涉及的内容比较广泛从统计学中的泊松分布到计算机基础的位运算经典的红黑树、链表、数组等数据结构也谈到了 Hash 函数的相关介绍文末也引入了美团对于 HashMap 的源码分析所以整体深度和广度都比较大。思维导图如下思维导图本文是两年前整理的文中不免有疏漏过时的地方欢迎大家提出宝贵的意见。之所以这里拿出来有以下几个目的(1)让读者理解 HashMap 的设计思想知道 rehash 的过程。下一节我们将自己实现一个 HashMap(2)为什么要自己实现 HashMap?最近在手写 redis 框架都说 redis 是一个特性更加强大的 Map自然 HashMap 就是入门基础。Redis 高性能中一个过人之处的设计就是渐进式 rehash和大家一起实现一个渐进式 rehash 的 map更能体会和理解作者设计的巧妙。想把常见的数据结构独立为一个开源工具便于后期使用。比如这次手写 redis循环链表LRU map 等都是从零开始写的不利于复用还容易有 BUG。好了下面就让我们一起开始 HashMap 的源码之旅吧~HashMap 源码HashMap 是平时使用到非常多的一个集合类感觉有必要深入学习一下。首先尝试自己阅读一遍源码。java 版本 $ java -versionjava version 1.8.0_91Java(TM) SE Runtime Environment (build 1.8.0_91-b14)Java HotSpot(TM) 64-Bit Server VM (build 25.91-b14, mixed mode)数据结构 从结构实现来讲HashMap是数组链表红黑树(JDK1.8增加了红黑树部分)实现的。对于当前类的官方说明 基于哈希表实现的映射接口。这个实现提供了所有可选的映射操作并允许空值和空键。(HashMap类大致相当于Hashtable但它是非同步的并且允许为空。)这个类不保证映射的顺序;特别地它不能保证顺序会随时间保持不变。这个实现为基本操作(get和put)提供了恒定时间的性能假设哈希函数将元素适当地分散在各个桶中。对集合视图的迭代需要与HashMap实例的“容量”(桶数)及其大小(键-值映射数)成比例的时间。因此如果迭代性能很重要那么不要将初始容量设置得太高(或者负载系数太低)这是非常重要的。HashMap实例有两个影响其性能的参数: 初始容量和负载因子。容量是哈希表中的桶数初始容量只是创建哈希表时的容量。负载因子是在哈希表的容量自动增加之前哈希表被允许达到的最大容量的度量。当哈希表中的条目数量超过负载因子和当前容量的乘积时哈希表就会被重新哈希(也就是说重新构建内部数据结构)这样哈希表的桶数大约是原来的两倍。一般来说默认的负载因子(0.75)在时间和空间成本之间提供了很好的权衡。较高的值减少了空间开销但增加了查找成本(反映在HashMap类的大多数操作中包括get和put)。在设置映射的初始容量时应该考虑映射中的期望条目数及其负载因子以最小化重哈希操作的数量。如果初始容量大于条目的最大数量除以负载因子就不会发生重哈希操作。如果要将许多映射存储在HashMap实例中那么使用足够大的容量创建映射将使映射存储的效率更高而不是让它根据需要执行自动重哈希以增长表。注意使用具有相同hashCode()的多个键确实可以降低任何散列表的性能。为了改善影响当键具有可比性时这个类可以使用键之间的比较顺序来帮助断开连接。注意这个实现不是同步的。如果多个线程并发地访问散列映射并且至少有一个线程在结构上修改了映射那么它必须在外部同步。(结构修改是添加或删除一个或多个映射的任何操作;仅更改与实例已经包含的键关联的值并不是结构修改。这通常是通过对自然封装映射的对象进行同步来完成的。如果不存在这样的对象则应该使用集合“包装” Collections.synchronizedMap 方法。这最好在创建时完成以防止意外的对映射的非同步访问:Map m Collections.synchronizedMap(new HashMap(...));这个类的所有“集合视图方法”返回的迭代器都是快速失败的:如果在创建迭代器之后的任何时候对映射进行结构上的修改除了通过迭代器自己的remove方法迭代器将抛出ConcurrentModificationException。因此在并发修改的情况下迭代器会快速而干净地失败而不是在未来的不确定时间内冒着任意的、不确定的行为的风险。注意迭代器的快速故障行为不能得到保证因为一般来说在存在非同步并发修改的情况下不可能做出任何硬性保证。快速失败迭代器以最佳的方式抛出ConcurrentModificationException。因此编写依赖于此异常的程序来保证其正确性是错误的:迭代器的快速故障行为应该仅用于检测错误。其他基础信息 这个类是Java集合框架的成员。since 1.2java.util 包下源码初探接口 public class HashMapK,V extends AbstractMapK,Vimplements MapK,V, Cloneable, Serializable {}当前类实现了三个接口我们主要关心 Map 接口即可。继承了一个抽象类 AbstractMap这个暂时放在本节后面学习。常量定义默认初始化容量 /** * The default initial capacity - MUST be a power of two. */static final int DEFAULT_INITIAL_CAPACITY 1 4; // aka 16为什么不直接使用 16看了下 statckoverflow感觉比较靠谱的解释是为了避免使用魔法数字使得常量定义本身就具有自我解释的含义。强调这个数必须是 2 的幂。为什么要是 2 的幂它是这样设计的因为它允许使用快速位和操作将每个键的哈希代码包装到表的容量范围内正如您在访问表的方法中看到的:final Node getNode(int hash, Object key) { Node[] tab; Node first, e; int n; K k;if ((tab table) ! null (n tab.length) 0 (first tab[(n - 1) hash]) ! null) { /// ...最大容量 隐式指定较高值时使用的最大容量。由任何带有参数的构造函数。必须是2的幂且小于 130。/*** The maximum capacity, used if a higher value is implicitly specified* by either of the constructors with arguments.* MUST be a power of two 130.*/static final int MAXIMUM_CAPACITY 1 30;为什么是 1 30当然了 interger 的最大容量为 2^31-1除此之外2**31是20亿每个哈希条目需要一个对象作为条目本身一个对象作为键一个对象作为值。在为应用程序中的其他内容分配空间之前最小对象大小通常为24字节左右因此这将是1440亿字节。可以肯定地说最大容量限制只是理论上的。感觉实际内存也没这么大负载因子 当负载因子较大时去给table数组扩容的可能性就会少所以相对占用内存较少(空间上较少)但是每条entry链上的元素会相对较多查询的时间也会增长(时间上较多)。反之就是负载因子较少的时候给table数组扩容的可能性就高那么内存空间占用就多但是entry链上的元素就会相对较少查出的时间也会减少。所以才有了负载因子是时间和空间上的一种折中的说法。所以设置负载因子的时候要考虑自己追求的是时间还是空间上的少。/** * The load factor used when none specified in constructor. */static final float DEFAULT_LOAD_FACTOR 0.75f;为什么是 0.75不是 0.8 或者 0.6其实 hashmap 源码中有解释。Because TreeNodes are about twice the size of regular nodes, weuse them only when bins contain enough nodes to warrant use(see TREEIFY_THRESHOLD). And when they become too small (due toremoval or resizing) they are converted back to plain bins. Inusages with well-distributed user hashCodes, tree bins arerarely used. Ideally, under random hashCodes, the frequency ofnodes in bins follows a Poisson distribution(http://en.wikipedia.org/wiki/Poisson_distribution) with aparameter of about 0.5 on average for the default resizingthreshold of 0.75, although with a large variance because ofresizing granularity. Ignoring variance, the expectedoccurrences of list size k are (exp(-0.5) * pow(0.5, k) /factorial(k)). The first values are:0: 0.606530661: 0.303265332: 0.075816333: 0.012636064: 0.001579525: 0.000157956: 0.000013167: 0.000000948: 0.00000006more: less than 1 in ten million简单翻译一下就是在理想情况下,使用随机哈希码,节点出现的频率在hash桶中遵循泊松分布同时给出了桶中元素个数和概率的对照表。从上面的表中可以看到当桶中元素到达8个的时候概率已经变得非常小也就是说用0.75作为加载因子每个碰撞位置的链表长度超过个是几乎不可能的。Poisson distribution —— 泊松分布阈值 /** * The bin count threshold for using a tree rather than list for a * bin. Bins are converted to trees when adding an element to a * bin with at least this many nodes. The value must be greater * than 2 and should be at least 8 to mesh with assumptions in * tree removal about conversion back to plain bins upon * shrinkage. */static final int TREEIFY_THRESHOLD 8;/** * The bin count threshold for untreeifying a (split) bin during a * resize operation. Should be less than TREEIFY_THRESHOLD, and at * most 6 to mesh with shrinkage detection under removal. */static final int UNTREEIFY_THRESHOLD 6;/** * The smallest table capacity for which bins may be treeified. * (Otherwise the table is resized if too many nodes in a bin.) * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts * between resizing and treeification thresholds. */static final int MIN_TREEIFY_CAPACITY 64;TREEIFY_THRESHOLD使用红黑树而不是列表的bin count阈值。当向具有至少这么多节点的bin中添加元素时bin被转换为树。这个值必须大于2并且应该至少为8以便与树删除中关于收缩后转换回普通容器的假设相匹配。UNTREEIFY_THRESHOLD在调整大小操作期间取消(分割)存储库的存储计数阈值。应小于TREEIFY_THRESHOLD并最多6个网格与收缩检测下去除。MIN_TREEIFY_CAPACITY最小的表容量可为容器进行树状排列。(否则如果在一个bin中有太多节点表将被调整大小。)至少为 4 * TREEIFY_THRESHOLD以避免调整大小和树化阈值之间的冲突。Node源码 Node.java基础 hash 结点定义。/** * Basic hash bin node, used for most entries. (See below for * TreeNode subclass, and in LinkedHashMap for its Entry subclass.) */static class NodeK,V implements Map.EntryK,V { 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); }public final V setValue(V newValue) { V oldValue value; value newValue;return oldValue; }public final boolean equals(Object o) {// 快速判断if (o this)return true;// 类型判断 if (o instanceof Map.Entry) { Map.Entry,? e (Map.Entry,?)o;if (Objects.equals(key, e.getKey()) Objects.equals(value, e.getValue()))return true; }return false; }}个人理解 四个核心元素final int hash; // hash 值final K key; // keyV value; // value 值Node next; // 下一个元素结点hash 值的算法hash 算法如下。直接 key/value 的异或(^)。Objects.hashCode(key) ^ Objects.hashCode(value);其中 hashCode() 方法如下public static int hashCode(Object o) { return o ! null ? o.hashCode() : 0;}最后还是会调用对象本身的 hashCode() 算法。一般我们自己会定义。静态工具类hash static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16);}为什么这么设计jdk8 自带解释计算key.hashCode()并将(XORs)的高比特位分散到低比特位。因为表使用的是power-of-two掩蔽所以只在当前掩码上方以位为单位变化的哈希总是会发生冲突。(已知的例子中有一组浮点键它们在小表中保存连续的整数。)因此我们应用了一种转换将高比特的影响向下传播。比特传播的速度、效用和质量之间存在权衡。因为许多常见的散列集已经合理分布(所以不要受益于传播),因为我们用树来处理大型的碰撞在垃圾箱,我们只是XOR一些改变以最便宜的方式来减少系统lossage,以及将最高位的影响,否则永远不会因为指数计算中使用的表。知乎的解释这段代码叫扰动函数。HashMap扩容之前的数组初始大小才16。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算得到的余数才能用来访问数组下标。putVal 函数源码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) n (tab resize()).length;if ((p tab[i (n - 1) hash]) null) tab[i] newNode(hash, key, value, null);//... }其中这一句 tab[i (n - 1) hash])这一步就是在寻找桶的过程就是上图总数组根据容量取如果容量是16 对hash值取低16位那么下标范围就在容量大小范围内了。这里也就解释了为什么 hashmap 的大小需要为 2 的正整数幂因为这样(数组长度-1)正好相当于一个“低位掩码”。比如大小 16则 (16-1) 15 00000000 00000000 00001111(二进制); 10100101 11000100 00100101 00000000 00000000 00001111------------------------------- 00000000 00000000 00000101 //高位全部归零只保留末四位但是问题是散列值分布再松散要是只取最后几位的话碰撞也会很严重。扰动函数的价值如下扰动函数的价值右位移16位正好是32bit的一半自己的高半区和低半区做异或就是为了混合原始哈希码的高位和低位以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征这样高位的信息也被变相保留下来。优化哈希的原理介绍comparable class comparableClassFor()获取对象 x 的类如果这个类实现了 class C implements Comparable 接口。ps: 这个方法很有借鉴意义可以做简单的拓展。我们可以获取任意接口泛型中的类型。static Class comparableClassFor(Object x) { if (x instanceof Comparable) { Class c; Type[] ts, as; Type t; ParameterizedType p; if ((c x.getClass()) String.class) // bypass checksreturn c; if ((ts c.getGenericInterfaces()) ! null) { for (int i 0; i if (((t ts[i]) 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() 获取两个可比较对象的比较结果。SuppressWarnings({rawtypes,unchecked}) // for cast to Comparablestatic 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 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;}被调用处public HashMap(int initialCapacity, float loadFactor) { // check... this.loadFactor loadFactor; this.threshold tableSizeFor(initialCapacity);}感想emmm....为什么要这么写性能吗简单分析当在实例化HashMap实例时如果给定了initialCapacity由于HashMap的capacity都是2的幂因此这个方法用于找到大于等于initialCapacity的最小的2的幂(initialCapacity如果就是2的幂则返回的还是这个数)。为什么要 -1int n cap - 1;首先为什么要对cap做减1操作。int n cap - 1; 这是为了防止cap已经是2的幂。如果cap已经是2的幂 又没有执行这个减1操作则执行完后面的几条无符号右移操作之后返回的capacity将是这个cap的2倍。如果不懂要看完后面的几个无符号右移之后再回来看看。下面看看这几个无符号右移操作如果n这时为0了(经过了cap-1之后)则经过后面的几次无符号右移依然是0最后返回的capacity是1(最后有个n1的操作)。这里只讨论n不等于0的情况。第一次位运算n | n 1;由于n不等于0则n的二进制表示中总会有一bit为1这时考虑最高位的1。通过无符号右移1位则将最高位的1右移了1位再做或操作使得n的二进制表示中与最高位的1紧邻的右边一位也为1如000011xxxxxx。其他依次类推实例比如 initialCapacity 10;表达式 二进制------------------------------------------------------ initialCapacity 10;int n 9; 0000 1001------------------------------------------------------ n | n 1; 0000 1001 0000 0100 (右移1位) 或运算 0000 1101------------------------------------------------------ n | n 2; 0000 1101 0000 0011 (右移2位) 或运算 0000 1111------------------------------------------------------ n | n 4; 0000 1111 0000 0000 (右移4位) 或运算 0000 1111------------------------------------------------------ n | n 8; 0000 1111 0000 0000 (右移8位) 或运算 0000 1111------------------------------------------------------ n | n 16; 0000 1111 0000 0000 (右移16位) 或运算 0000 1111------------------------------------------------------ n n1; 0001 0000 结果2^4 16; put() 解释下面的内容出自美团博客 Java 8系列之重新认识HashMap由于写的非常好此处就直接复制过来了。流程图解 HashMap的put方法执行过程可以通过下图来理解自己有兴趣可以去对比源码更清楚地研究学习。输入图片说明①.判断键值对数组table[i]是否为空或为null否则执行resize()进行扩容②.根据键值key计算hash值得到插入的数组索引i如果table[i]null直接新建节点添加转向⑥如果table[i]不为空转向③③.判断table[i]的首个元素是否和key一样如果相同直接覆盖value否则转向④这里的相同指的是hashCode以及equals④.判断table[i] 是否为treeNode即table[i] 是否是红黑树如果是红黑树则直接在树中插入键值对否则转向⑤⑤.遍历table[i]判断链表长度是否大于8大于8的话把链表转换为红黑树在红黑树中执行插入操作否则进行链表的插入操作遍历过程中若发现key已经存在直接覆盖value即可⑥.插入成功后判断实际存在的键值对数量size是否超多了最大容量threshold如果超过进行扩容。方法源码 public V put(K key, V value) { return putVal(hash(key), key, value, false, true);}/** * Implements Map.put and related methods * * param hash hash for key * param key the key * param value the value to put * param onlyIfAbsent if true, dont change existing value * param evict if false, the table is in creation mode. * return previous value, or null if none */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) 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) {if ((e p.next) null) { 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))))break; p e; } }if (e ! null) { // existing mapping for key V oldValue e.value;if (!onlyIfAbsent || oldValue null) e.value value; afterNodeAccess(e);return oldValue; } } modCount;if (size threshold) resize(); afterNodeInsertion(evict);return null;}扩容机制简介 扩容(resize)就是重新计算容量向HashMap对象里不停的添加元素而HashMap对象内部的数组无法装载更多的元素时对象就需要扩大数组的长度以便能装入更多的元素。当然Java里的数组是无法自动扩容的方法是使用一个新的数组代替已有的容量小的数组就像我们用一个小桶装水如果想装更多的水就得换大水桶。JDK7 源码 我们分析下resize()的源码鉴于JDK1.8融入了红黑树较复杂为了便于理解我们仍然使用JDK1.7的代码好理解一些本质上区别不大具体区别后文再说。void resize(int newCapacity) { //传入新的容量 Entry[] oldTable table; //引用扩容前的Entry数组 int oldCapacity oldTable.length; if (oldCapacity MAXIMUM_CAPACITY) { //扩容前的数组大小如果已经达到最大(2^30)了 threshold Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1)这样以后就不会扩容了 return; } Entry[] newTable new Entry[newCapacity]; //初始化一个新的Entry数组 transfer(newTable); //将数据转移到新的Entry数组里 table newTable; //HashMap的table属性引用新的Entry数组 threshold (int)(newCapacity * loadFactor);//修改阈值}这里就是使用一个容量更大的数组来代替已有的容量小的数组transfer() 方法将原有Entry数组的元素拷贝到新的Entry数组里。void transfer(Entry[] newTable) { Entry[] src table; //src引用了旧的Entry数组 int newCapacity newTable.length; for (int j 0; j //遍历旧的Entry数组 Entry e src[j]; //取得旧Entry数组的每个元素if (e ! null) { src[j] null;//释放旧Entry数组的对象引用(for循环后旧的Entry数组不再引用任何对象)do { Entry next e.next;int i indexFor(e.hash, newCapacity); //重新计算每个元素在数组中的位置 e.next newTable[i]; //标记[1] newTable[i] e; //将元素放在数组上 e next; //访问下一个Entry链上的元素 } while (e ! null); } }}newTable[i]的引用赋给了e.next也就是使用了单链表的头插入方式同一位置上新元素总会被放在链表的头部位置这样先放在一个索引上的元素终会被放到Entry链的尾部(如果发生了hash冲突的话)这一点和Jdk1.8有区别下文详解。在旧数组中同一条Entry链上的元素通过重新计算索引位置后有可能被放到了新数组的不同位置上。案例 下面举个例子说明下扩容过程。假设了我们的hash算法就是简单的用key mod 一下表的大小(也就是数组的长度)。其中的哈希桶数组table的size2 所以key 3、7、5put顺序依次为 5、7、3。在mod 2以后都冲突在table[1]这里了。这里假设负载因子 loadFactor1即当键值对的实际大小size 大于 table的实际大小时进行扩容。接下来的三个步骤是哈希桶数组 resize成4然后所有的Node重新rehash的过程。输入图片说明Jdk8 优化 经过观测可以发现我们使用的是2次幂的扩展(指长度扩为原来2倍)所以元素的位置要么是在原位置要么是在原位置再移动2次幂的位置。看下图可以明白这句话的意思n为table的长度图(a)表示扩容前的key1和key2两种key确定索引位置的示例图(b)表示扩容后key1和key2两种key确定索引位置的示例其中hash1是key1对应的哈希与高位运算结果。位运算元素在重新计算hash之后因为n变为2倍那么n-1的mask范围在高位多1bit(红色)因此新的index就会发生这样的变化index因此我们在扩充HashMap的时候不需要像JDK1.7的实现那样重新计算hash只需要看看原来的hash值新增的那个bit是1还是0就好了是0的话索引没变是1的话索引变成“原索引oldCap”可以看看下图为16扩充为32的resize示意图rehash这个设计确实非常的巧妙既省去了重新计算hash值的时间而且同时由于新增的1bit是0还是1可以认为是随机的因此resize的过程均匀的把之前的冲突的节点分散到新的bucket了。这一块就是JDK1.8新增的优化点。有一点注意区别JDK1.7中rehash的时候旧链表迁移新链表的时候如果在新表的数组索引位置相同则链表元素会倒置但是从上图可以看出JDK1.8不会倒置。JDK8 源码 有兴趣的同学可以研究下JDK1.8的resize源码写的很赞:/** * Initializes or doubles table size. If null, allocates in * accord with initial capacity target held in field threshold. * Otherwise, because we are using power-of-two expansion, the * elements from each bin must either stay at same index, or move * with a power of two offset in the new table. * * return the table */final Node[] 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;return oldTab; }else if ((newCap oldCap 1) 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 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 Node 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)e).split(this, newTab, j, oldCap);else { // preserve order 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; } } } } }return newTab;}小结如果你已经通读全文那么你已经非常厉害了。其实第一遍没有彻底理解也没有关系知道 HashMap 有一个 reHash 的过程就行类似于 ArrayList 的 resize。下一节我们将一起学习下自己手写实现一个渐进式 rehash 的 HashMap感兴趣的可以关注一下便于实时接收最新内容。觉得本文对你有帮助的话欢迎点赞评论收藏转发一波。你的鼓励是我最大的动力~不知道你有哪些收获呢或者有其他更多的想法欢迎留言区和我一起讨论期待与你的思考相遇。
