Shulou(Shulou.com)06/02 Report--

In this issue, Xiaobian will bring you about how to interpret Java HashMap core source code. The article is rich in content and analyzed and described from a professional perspective. After reading this article, I hope you can gain something.

HashMap implementation of the source code for a simple analysis. The version information of the HashMap source code used is as follows:

/** @(#)HashMap.java 1.73 07/03/13** Copyright 2006 Sun Microsystems, Inc. All rights reserved.* SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.*/

I. overview

In Java, every object has a hash code, which can be obtained by hashCode() method. The value of hashCode() is closely related to the equals method of the object and is the basis for whether the values of the two objects are equal, so when we override the equals method of a class, we must also override the hashCode method.

For example, the hashCode method for String is:

public int hashCode() {int h = hash;if (h == 0) {int off = offset;char val[] = value;int len = count;for (int i = 0; i

< len; i++) {h = 31*h + val[off++];}hash = h;}return h;} 可以看得出，一个字符串的哈希值为s[0]31n-1 + s[1]31n-2 + … + s[n-1]，是一个整数。也就是说所有的字符串可以通过hashCode()将其映射到整数的区间中，由于在java中整数的个数是有限的（四个字节有正负，***位为符号位-231 ~ 231 -1），当s[0]31n-1 + s[1]31n-2 + … + s[n-1]足够大的时候可能会溢出，导致其变成负值。从上面的情况我们可以看出两个不同的字符串可能会被映射到同一个整数，发生冲突。因此java的开 发人员选择了31这个乘数因子，尽量使得各个字符串映射的结果在整个java的整数域内均匀分布。 谈完java对象的哈希码，我们来看看今天的主角HashMap，HashMap可以看作是Java实现的哈希表。HashMap中存放的是 key-value对，对应的类型为java.util.HashMap.Entry，所以在HashMap中数据都存放在一个Entry引用类型的数组 table中。这里key是一个对象，为了把对象映射到table中的一个位置，我们可以通过求余法来，所以我们可以使用 [key的hashCode % table的长度]来计算位置（当然在实际操作的时候由于需要考虑table上的key的均匀分布可能需要对key的hashCode做一些处理）。 二.源码解析 相关属性 首先肯定是需要一个数组table，作为数据结构的骨干。 transient Entry[] table; 这边定义了一个Entry数组的引用。 继续介绍几个概念把 capacity容量 是指数组table的长度 loadFactor 装载因子，是实际存放量/capacity容量 的一个比值，在代码中这个属性是描述了装载因子的***值，默认大小为0.75 threshold（阈值）代表hashmap存放内容数量的一个临界点，当存放量大于这个值的时候，就需要将table进行夸张，也就是新建一个两倍大的数组，并将老的元素转移过去。threshold = (int)(capacity * loadFactor); put方法详解 public V put(K key, V value) { if (key == null) return putForNullKey(value); int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); for (Entry e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(hash, key, value, i); return null; } 在HashMap中我们的key可以为null，所以***步就处理了key为null的情况。 当key为非null的时候，你也许会认为：恩，直接和table长度相除取模吧，但是这里没有，而是又好像做了一次哈希，这是为什么呢？这个还得先看indexFor(hash, table.length)方法，这个方法是决定存放位置的 static int indexFor(int h, int length) { return h & (length-1); } 明眼的都可以发现，因为在HashMap中table的长度为2n (我们把运算都换成二进制进行考虑)，所以h & (length-1)就等价于h%length，这也就是说，如果对原本的hashCode不做变换的话，其除去低length-1位后的部分不会对 key在table中的位置产生任何影响，这样只要保持低length-1位不变，不管高位如何都会冲突，所以就想办法使得高位对其结果也产生影响，于是 就对hashCode又做了一次哈希 static int hash(int h) { // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >

>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); }

When the position corresponding to the key is found, traverse the linked list of Entry at the corresponding position, and if there is a key, update the corresponding value and return the old value. If it is a new key, add it. modCount is used to record the number of changes to the hashmap structure, which is required in the fail-fast mechanism of hashmap (when a thread obtains the cursor of the map and another thread makes structural modifications to the map, then the thread that was originally prepared to traverse will throw an exception). Add Entry as follows

void addEntry(int hash, K key, V value, int bucketIndex) { Entry e = table[bucketIndex]; table[bucketIndex] = new Entry(hash, key, value, e); if (size++ >= threshold) resize(2 * table.length); }

get method

public V get(Object key) { if (key == null) return getForNullKey(); int hash = hash(key.hashCode()); for (Entry e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) return e.value; } return null; }

The get method actually calculates the position of the key in the table in the same way as put, and then traverses the linked list at the position to find the Entry with the hash value and key equal and return the value.

The above is how to interpret Java HashMap core source code shared by Xiaobian for everyone. If there is a similar doubt, please refer to the above analysis for understanding. If you want to know more about it, please pay attention to the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.