HashMap 可以说是我们一个熟悉又陌生的 Java 中常用的存储数据的 API. 说他熟悉, 是因为我们经常使用他, 而说他陌生是因为我们大部分时间是只知道他的使用, 而并不知道他内部的原理, 但是在面试考察的时候又最喜欢去问这个原理. 今天, 我就来从源码的角度, 谈谈对 HashMap 的理解.
HashMap 概述
hashMap 的底层其实是基于一个数组来进行数据的存储和取出. 他继承于 Map 这个接口来实现, 通过 put 和 get 方法来操作数据的存和取. 具体对于 hashMap 的使用, 这里不在具体举例说明, 使用起来并不困难. 不过在谈到 HashMap 的内部原理之前, 我们需要了解一下几个名称的意思.
1.initialCapacity. 这个翻译为初始化容量. 为 hashMap 的存储的初始化空间的大小, 我们可以通过构造方法来指定其大小, 也可以不指定采用 默认大小 16. 这里需要说明一下, 一般来说, 容器的大小为 2 的幂次方. 至于为什么会是 2 的幂次方, 具体原因可以参考这篇文章. 为什么 hashmap 的初始化大小为 2 的幂次方 https://blog.csdn.net/sybnfkn040601/article/details/73194613
2.loadFactor. 加载因子. 当 hashmap 的存储容量达到了一定上限之后, 如果还需要进行数据的存储, 则会利用加载因子对其进行扩容操作. 一般而言, 扩容大小为现在容量的 0.75 倍. 举个例子, 假设现在的 hashMap 的初始化大小为 16, 但是现在由于容量已满又要插入新的元素, 所以先进行扩容操作, 将容量扩充为 16*0.72=12, 也就是说扩大了 12 个容量.
3.threadshold: 扩容阀值. 即扩容阀值 = HashMap 总容量 * 加载因子. 当 hashMap 的容量大于或者等于扩容阀值的时候就会去执行扩容. 扩容的容量为当前 HashMap 总容量的两倍.
这里有一张网上找来的图, 来说明 hashMap 内部存储原理.
源码解析
我们在使用 hashMap 的时候, 一般来说都是用 put 和 get 方法, 所以我们分析源码, 就从这两个方法着手分析内部原理.
- public V put(K key, V value) {
- if (table == EMPTY_TABLE) {
- inflateTable(threshold);
- }
- if (key == null)
- return putForNullKey(value);
- int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
- int i = indexFor(hash, table.length);
- for (HashMapEntry<K,V> 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;
- }
复制代码
我们先来看看 put 方法. 从代码可以看出, put 方法主要做了这么几件事.
1. 当我们在将 key 和 value 添加进入 hashMap 的时候, 首先其会去判断 table 是否为空 (EMPTY_TABLE). 这里需要说明下, 这个 table 其实是一个数组, 我们前面提到过, hashmap 内部其实是一个数组来对数据进行存储, 所以这个 table 其实可以写成 table[ ]. 当判断这个 table 数组为空的时候, 他会去调用 infalteTable() 方法. 而这个方法是做什么的呐, 我们在跳进去看看.
- private void inflateTable(int toSize) {
- // Find a power of 2>= toSize
- int capacity = roundUpToPowerOf2(toSize);
- // Android-changed: Replace usage of Math.min() here because this method is
- // called from the <clinit> of runtime, at which point the native libraries
- // needed by Float.* might not be loaded.
- float thresholdFloat = capacity * loadFactor;
- if (thresholdFloat> MAXIMUM_CAPACITY + 1) {
- thresholdFloat = MAXIMUM_CAPACITY + 1;
- }
- threshold = (int) thresholdFloat;
- table = new HashMapEntry[capacity];
- }
复制代码
可以看到, 其实这个 inflateTable 方法是在对 hashmap 进行初始化容量操作. 其初始化容量为 capacity * loadFacctor. 也就是我们前面说过的 初始化容量 * 加载因子.
2. 之后 hashmap 回去判断你储存的 key 是否为空, if(key == null), 如果为空, 则调用 putForNullKey()方法来进行空 key 的操作. 这里可以说是 hashMap 与 hashTable 的一个最大不同的地方, hashMap 允许 key 为空, 他有相应的处理 key 为空的操作方法, 但是 hashTable 却不能允许 key 为空, 他没有相应的操作方法.
3. 之后对 key 进行一次 hashcode 的计算并且计算其 index. 紧接着遍历整个 table 数组, 判断是否有相同的 key, 如果发现有相同的 key, 则将 key 所携带的新的 value 替换掉之前旧的 value, 从而确保 key 的唯一性. 之后进行 addEntry 方法中.
- void addEntry(int hash, K key, V value, int bucketIndex) {
- if ((size>= threshold) && (null != table[bucketIndex])) {
- resize(2 * table.length);
- hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;
- bucketIndex = indexFor(hash, table.length);
- }
- createEntry(hash, key, value, bucketIndex);
- }
复制代码
我们进入到 addEntry 方法中查看. 发现里面会先对数组需要存储的大小和阀值进行一次比较, 如果发现要存储的已经超过了 threshold 阀值, 那么就要调用 resize 对其进行扩容操作. 扩容的小大为 2*table.length. 之后从新计算 hash, 将结果存储到 bucket 桶里面.
那么 resize()方法中又做了那些操作呐?
- void resize(int newCapacity) {
- HashMapEntry[] oldTable = table;
- int oldCapacity = oldTable.length;
- if (oldCapacity == MAXIMUM_CAPACITY) {
- threshold = Integer.MAX_VALUE;
- return;
- }
- HashMapEntry[] newTable = new HashMapEntry[newCapacity];
- transfer(newTable);
- table = newTable;
- threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
- }
复制代码
我们可以看到 resize 里面仅仅只是初始化了一个新的更大的 table 数组, 并且把老的数据从新添加进入了新的 table 里面去.
最后我们回到 creatEntry 方法中, 查看发现如果在 bucket 桶内发生了 hash 的碰撞, 则将其转化为链表的形式来进行存储, 不过在 Java1.8 之后会将其变为红黑树的形式存储. 在此将 put 方法源码分析完成.
我们再来看下 get()方法.
- public V get(Object key) {
- if (key == null)
- return getForNullKey();
- Entry<K,V> entry = getEntry(key);
- return null == entry ? null : entry.getValue();
- }
复制代码
get 方法一开始和 put 类似, 都是先判断 key 是否为空, 如果为空, 则调用相应的 getForNullKey 方法去进行处理. 不为空, 调用 getEntry 去进行查找. 我们再来看看 getEntry 里面又做了什么操作.
- final Entry<K,V> getEntry(Object key) {
- if (size == 0) {
- return null;
- }
- int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
- for (HashMapEntry<K,V> e = table[indexFor(hash, table.length)];
- e != null;
- e = e.next) {
- Object k;
- if (e.hash == hash &&
- ((k = e.key) == key || (key != null && key.equals(k))))
- return e;
- }
- return null;
- }
复制代码
我们可以看到, 里面也是先对 key 进行了一次 hash 操作, 之后通过这个 hash 值来进行查找, 如果发现 hash 值相等, 则再通过比较 key 的值来进行查找, 最终找到我们想要的 e 将其 return 返回, 不然则返回为空, 代表找不到此元素.
到此 hashMap 的整体原理讲解完毕.
来源: https://juejin.im/post/5b7991fc51882542f25a4e76