Java HashMap使用源码分析

这篇文章主要讲解了“JavaHashMap使用源码分析”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“JavaHashMap使用源码分析”吧！首先我们先看一下 HashMap 有哪些成员变量下面还有一个 Node 类，这个类就是 HashMap 存储元素的容器，其实很简单没有多少复杂的内容，类似于链表的Node节点，key、value、next，因为大量的地方都需要用到对象的 hash 值，所以又记录了下 key 的 hash 值。继续往下看也没什么好说的，就是通过对象的 hashCode 计算出一个 int 值。下面有个 comparableClassFor 方法，这个方法的主要是判断入参 x 是否实现了 Comparable 接口。不过写的格式有点紧凑，我们需要展开以下。举个例子:这个方法就结束了，如果还是不能理解，可以将代码复制出来，打个断点跑一下。继续往下看。这个方法有意思，注释是说，如果 x 是 kc 的类型，返回 k.compareTo(x) （k 是筛选过的比较类）。如果你查找下这个方法的使用地方就会发现，kc 这个参数就是上面 comparableClassFor 返回的类型。这么一看是不是就清晰了？ comparableClassFor(x) 拿到类型，然后传入 compareComparables(kc,k,x) 去比较。下面又是一个方法：这个方法也很有意思，看着很复杂，其实功能很简单，返回第一个大于等于 cap 的 2 的幂值。还是那句话， main 方法试试就知道了。不多说。再往下就是一些变量了。其中最核心的变量就是 table通过注释我们就可以知道这个是存储 HashMap 元素的数组，在第一次使用时被初始化，并且根据需要调整大小，长度适中是 2 的幂。table 数组就是存储 HashMap 元素的底层结构，具体怎么存储我们后面再看。不过需要注意的是这个变量使用了一个 transient 修饰符，这在我们平常的编码中是很少见到的。这个修饰符的作用是在序列化时跳过该属性。是跟 Serializable 相对应的。其实就是当一个 HashMap 对象被序列化到文件中时，其中的元素是没有写到文件里的。所以通过反序列化也是拿不到元素的。我们知道了它的功能，但是 HashMap 为什么要这么做呢？其实这个是跟 HashMap 的 put 方法有关系，我们稍后再说。继续往下看。下面还有一些其他的属性，其中有两个比较重要。threshold 是下次扩容时 HashMap 的容量。 loadFactor 是加载因子，当 HashMap 的容量达到总容量的一定比例就会触发扩容。这两个字段都跟扩容有关，等看到扩容时再说。再往下就是几个构造方法了，前面三个构造方法都只是在确定 thresho免费云主机域名ld、loadFactor 这两个属性的默认值。没有什么好说的threshold 如果初始化时没有传值就是 0 ，loadFactor 默认值是 DEFAULT_LOAD_FACTOR = 0.75f。也就是说，如果 HashMap 的当前容量达到总容量的 75% 就会触发扩容。后面还有一个构造方法是传入了一个 Map 集合，它会把入参中集合里的元素 put 到当前的 HashMap 集合中。这个构造方法首先初始化了 loadFactor 属性，然后调了putMapEntries 方法，这个方法就在下面。同样格式有点乱，没关系，我们先调整下格式。如果 map 里没有元素，直接结束。因为我们是构造方法进入到这个方法里的，所以 table 一定为 null，然后计算了一下 ft ，表示放入 m 个元素后，HashMap 的最大容量，（如果 s = 75,那 ft = 101）。然后计算了一下 t 就是 map 需要的最大容量。并且判断一下是否超限。然后判断了一下是否要更新 threshold ，因为我们是构造方法进来的，所以一定是需要更新的。更新结束后就是 for 循环依次调用 putVal 将元素放入到当前的 HashMap 里。然后我们跳到 putVal 方法。这个方法的格式依然不太好阅读，我们需要修改下。首先判断了 table 是否进行了初始化，没有的话进行 resize， 这个方法我们一会再看。它的作用就是返回一个 Node 数组，数组的长度就是 threshold。初始化好之后就是判断下这个数组的(n - 1) & hash 位置是否有值，没有值的话直接创建一个 Node 存到数组里就结束了。其实 (n - 1) & hash 相当于 hash % (n-1) 的作用，但是与操作的效率比取模的效率高。二者达到的效果是一样的。如果有值，并且 key 相等，说明是同一个元素，这个时候 e 就是 HashMap 里的元素，后面对 e 的判断就会直接返回 e 对应的 value。如果 key 不相等，说明发生了 hash 冲突。两个 hash 值不一样的元素应该存储到数组的同一个位置。这个时候判断了一下 Node 的类型。如果是 TreeNode 那么调用 putTreeVal 方法。如果不是，则依次遍历当前位置节点的 next 指针，直到为空，插入新节点。其实就是讲新节点挂到了已当前节点为表头的链表尾部。插入成功之后判断了一下链表的长度，如果需要则进行树化。将当前链表转成一个红黑树。这个主要是解决链表太长，查询效率低的问题。而且在遍历链表期间依然判断了 key 是否相等，相等则直接返回旧元素的 value。好像也不是很难，这个就是 HashMap 最核心的方法之一了。从这个方法中也可以知道，HashMap 的底层存储结构是一个数组。如果发生 hash 冲突后，会采用链表的方式存储，当链表长度过长时，会将链表转成红黑树结构，提高查询效率。下面我们看一下resize() 方法resize() 方法的主要作用就是当 table 数组中的元素超过一定的数量后，对 table 数组进行扩容，以便减少 hash 碰撞发生的概率。 最前面一大串的 if 、else 判断主要是为了确定两个变量的值 newCap 和 newThr 。newCap 是指扩容后新的 table 数组的长度。newThr 是指新数组的元素超过多少时需要扩容。计算的方式分几种场景。第一种 oldCap > 0: 这种是正常扩容，oldTable 已经有元素了，而且元素的数量也达到了扩容的数量。这时 newCap 和 newThr 是原来数值的 2 倍（ 是右移操作） 而且判断了下是否超过了最大值。如果 oldCap 已经大于等于最大值了，那直接把下次扩容的阈值调整到最大就结束了，因为 table 数组已经无法扩容了。(newCap = oldCap 这一行代码很有意思它的执行逻辑是，先将 oldCap 右移一位后的数值赋值给 newCap，然后判断 newCap 是否超过了 MAXIMUM_CAPACITY 。有意思的点在于，它没有关注 newCap 的溢出情况！！这个其实也是 HashMap 的的容量永远都是 2 的整数次幂的原因。因为，把一个2 的整数次幂的数值右移一位后，依然是一个2 的整数次幂，而 MAXIMUM_CAPACITY 就是允许的最大的 2的整数次幂。因为之前已经判断过是否等于 MAXIMUM_CAPACITY 了。所以，oldCap 右移后，最大只能是等于 MAXIMUM_CAPACITY ，不会溢出。而且，当 newCap 等于 MAXIMUM_CAPACITY 是没有对 newThr 赋值的，对 newThr 赋值的逻辑是在下面的 if (newThr == 0) 的地方。第二个场景 else if (oldThr > 0) 执行到这个 if 里的情况是，初始化的时候传了 initialCapacity 这个参数。还记得之前初始化时 threshold 的赋值逻辑么？this.threshold = tableSizeFor(initialCapacity)当初始时传了 initialCapacity 参数，在第一次 put 操作时，就会触发首次扩容（或者说初始化 table 数组）。这里有个小知识点：我们在平时写代码使用到 HashMap 时，为了提高效率，不让 HashMap 触发扩容，都会指定 HashMap 的容量，比如：这个时候我们往 Map 里放 5 个元素，应该是只扩容一次即初始化 table 那次。好像没有什么问题。这时因为在第一次初始化时 tableSizeFor 这个参数返回的是大于等于 initialCapacity 的最小的 2 的整数幂的值。比如你传 50，初始化的结果是 64 。而默认的 loadFactor 是 0.75，也就是在元素达到 48 时才会触发扩容。但是，如果你给的值是 48 以上的呢? 或者说恰好是 64 的时候。这个时候就会在插入第 49 个元素时再次触发一次扩容。所以，如果你明确的知道元素的容量的话，可以初始化 2 倍元素容量的 HashMap ，这样就不会触发两次扩容了。继续往下说，计算好 newCap 和 newThr 的值后，就创建了一个 newTab，然后就是遍历 oldTab 不断的将元素转移到 newTab 里去。首先将 oldTab 的引用置为 null，避免内存泄露。然后当前元素会有三种情况： 第一种 e.next == null 就是当前位置只有这一个元素，没有发生 hash 冲突。这种最简单，直接放到 newTab 里就可以了。 第二种 e instanceof TreeNode，就是发生了 hash 冲突，且已经把链表转成了红黑树的结构了（还记的 putVal 方法么？）。这种就需要按照红黑树的操作，把 e 这个节点从 oldTab 上摘下来，挂到 newTab 上去（有点复杂，已经超过了本文的内容。需要了解的可以搜一下红黑树）。 第三种，就是发生了 hash 冲突，但是存储结构还是链表的情况。这种情况如果按照正常的思路的话，无非就是遍历链表，依次将链表的元素放入到 newTab 就好了。但是这样就会有一个问题，就是链表上的元素依然有可能出现 hash 冲突，如果在遍历链表期间多个元素发生了 hash 冲突怎么办呢？很显然，从代码上来看，并没有按照我们的思路来。代码逻辑是根据元素的 hash 值将一个链表分成了两个链表。loHead 和 hiHead。等拆分完成后，直接将链表的表头保存到了 newTab 的两个元素里。是不是很神奇？？就好像是在说，扩容前发生了 hash 冲突的元素，那么扩容后也有可能发生 hash 冲突，并且这些元素一定应该放到 newTab[j] 或者是 newTab[j+oldCap] 这两个位置。事实就是这样！！其实，你可以写代验证下，扩容前发生 hash 冲突的元素，如果 (e.hash & oldCap) == 0 那么它一定会落在 newTab[j]上，否则一定落在 newTab[j+oldCap] 上。数学就是这么完美~~好了，resize()方法到这里就结束了。我们回到 putMapEntries() 方法这里继续往下看。再往下，szie() 和 isEmpty() 都没有什么好说的，下面是 get(Object key) 方法，这个是 HashMap 最常用的方法之一。好像也没有特别复杂，计算 key 的 hash 值，然后通过 getNode 方法获取 node 对象，找不到就返回 null，找到了就返回对应的 value。getNode()方法就在下面。如果你对 putVal() 方法已经非常熟悉了，其实 getNode() 就非常清晰了。首先判断了 table 是否为空，不为空的话就通过 hash 找对应位置的元，如果对应的位置有值，就判断 key 是否相等。相等直接返回。如果不相等，则判断当前位置是否有其他元素，如果是 TreeNode 则从红黑树里找，如果是链表则遍历链表找。这里需要注意下，还记得之前我们说过 table 这个变量加了 transient 修饰符么，就是为了不让 table 元素进行序列化。其实是跟hash(key) 这个方法有关系。你可以翻看下hash() 这个方法，里面有这样一段 h = key.hashCode()。这里的 hashCode() 你找到它的定义会发现是下面这样的,这是一个本地方法。这个方法在不同的 JVM 上可能会有不同的实现，所以，就有可能出现，序列化前和序列化后的对象 hashCode() 方法返回的值不同。但是在序列化后，HashMap 保存在 table 中的位置没有变，就会出现找不到的情况，这就是 HashMap 中的一些元素不能序列化的原因。继续往下就没有什么好说的了，剩下的除了像 clear()、remove() 这种比较简单的方法外，就剩一个最复杂的treeify和untreeify。这个是 HashMap 里最复杂的部分，都是 TreeNode 里的方法，已经超出了本文的内容。感谢各位的阅读，以上就是“JavaHashMap使用源码分析”的内容了，经过本文的学习后，相信大家对JavaHashMap使用源码分析这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是百云主机，小编将为大家推送更多相关知识点的文章，欢迎关注！

相关推荐: c++类函数作为模板参数实现的方法是什么

今天小编给大家分享一下c++类函数作为模板参数实现的方法是什么的相关知识点，内容详细，逻辑清晰，相信大部分人都还太了解这方面的知识，所以分享这篇文章给大家参考一下，希望大家阅读完这篇文章后有所收获，下面我们一起来了解一下吧。DB操作有四种基本操作：Insert…