HashMap源码解析

2023-12-13 14:01:09

HashMap源码解析

前言

本文是关于HashMap的源码解析
将讲解JDK1.7 & 1.8的HashMap
会将两个版本作为对比来进行解析和学习

源码解析

JDK 1.7

基本参数

// HashMap的初始容量 
static final int DEFAULT_INITIAL_CAPACITY = 1 4; 
// HashMap的最大容量 
static final int MAXIMUM_CAPACITY = 1 30;
// HashMap的扩容因子 
static final float DEFAULT_LOAD_FACTOR = 0.75f; 
// 键值对的个数 
transient int size;

构造函数

/** * initialCapacity 就是初始容量
* loadFactor 就是它的负载因子
*/
public HashMap(int initialCapacity, float loadFactor)
public HashMap(int initialCapacity)
public HashMap(Map<? extends K, ? extends V> m) {
public HashMap()

好了，现在我们把基本的一些参数方法都列了出来，让我们开始分析。我们先一步步来。从我们最开始 Map userMap = new HashMap();点进源码，找到他的构造方法，里面方法体长这个样子：这里面还调用的另一个构造方法，我们继续跟进：在这里，它传入了两个值，initialCapacity是初始容量 loadFactor是负载因子，哦吼，有丶意思，让我们来研究一下。

/** 在这段代码里 
*/ 
public HashMap(int initialCapacity, float loadFactor) {
// 先判断初始容量是不是0, HashMap的最大容量（这里最大容量是2的30次方 
// 如果结果为true的话 就让传进来的输 === 最大容量
  if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; 
// 判断 传进来的负载因子 是否合法 或者>0, 结果为true 就抛错 
if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
this.loadFactor = loadFactor; threshold = initialCapacity; init();
}

这就是构造函数的分析了接下来我们应该看看put方法，看看HashMap到底是怎样存值的

public V put(K key, V value) {
    // 先判断了table是否为空，为空才去初始化
    // 这里有一个知识点，只有table为空的时候在去进行初始化。 所以有的面试官会问：
    // HashMap是不是在new的时候就进行了初始化，这里可以很明显的看到，HashMap在第一个put的时候才去进行的初始化
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    // 大家都知道 HashMap是可以存null值的，null也可以当作键值去存值
    // 这里就是HashMap可以存null值的具体实现了
    // 这段代码详细写了 key==null时
    // 会将value值放入首位
    // 这时候如果再传入null值 会将旧值替换成新值
    if (key == null) return putForNullKey(value);
    // 计算hash
      int hash = hash(key);
      int i = indexFor(hash, table.length);
      for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
        //这里是判断HashMap里是否已经有了这个值，如果有了，则用新值替换掉旧值，这也就是说，为什么 map里的key不能重复
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        modCount++; 
// 将key value传入map addEntry(hash, key, value, i);
        return null;
    }

这里额外讲一下怎么计算索引,也就是value存放的地方在put方法中：计算完哈希后，根据哈希和数组长度去计算对应的索引，也就是这个key应该在数组里哪里存储。我们发现每次put的时候都需要重新计算hash。HashMap的数据结构是数组+链表，数组特点是查询快增删慢，链表的特点是增删快，查询慢。我们用HashMap肯定主要是为了查询的呀。所以从应用的角度考虑，我们肯定希望这些元素能均匀的分布在数组的不同格子里，这样做查询的时候就会快。对于计算出来的Hash值，不管是二进制还是字母还是啥啥啥，反正能转换为二进制就是了，能转成二进制那是否就能转成十进制，反正你是个数字，对吧，每个key的hash不一样，那么对数组长度取余是否就算是平均分了。这时候我们先看一眼计算hash的方法
这里发现好多的左移右移的位运算符。目的是通过各种右移能够让高位也参与运算，最大化的避免高位相同低位不同分到同一个索引。

这里计算索引讲完了，接下来我们讲一下存储。废话不多说，上代码

void addEntry(int hash, K key, V value, int bucketIndex) {
        //当前的元素个数大于等于扩容阈值的时候，并且分配给新元素的这个位置以及有值，则扩容
        if ((size >= threshold) && (null != table[bucketIndex])) {
            //扩容为原来的数组长度乘2
            resize(2 * table.length);
            //如果key=null，则hash为0
            hash = (null != key) ? hash(key) : 0;
            //根据新数组长度重新计算索引
            bucketIndex = indexFor(hash, table.length);
        }
        // 存储
        createEntry(hash, key, value, bucketIndex);
    }

这里需要讲的是，HashMap的初始值为16，这个16是一个经验值，规定HashMap的容量必须为2的n次方，初始太小了要频繁扩容，太大了又浪费，所以为了平衡选择16。
HashMap的第一次扩容发生在容量达到12的时候，16*0.75=12。

JDK1.8 HashMap

1.8相比1.7 在基本属性上多了两个

// 树化阈值
static final int TREEIFY_THRESHOLD = 8;
// 非树化阈值
static final int UNTREEIFY_THRESHOLD = 6;

1.7的数据结构是：数组+链表
1.8的数据结构是：数组+链表+红黑树

HashMap源码解析

码农公寓