HashMap源码分析（JDK1.7）

发表于 | 更新于 | 分类于 | 阅读次数：

前言

和分析JDK1.8的HashMap源码一样，本文也是通过构造方法、增删改查等基本操作来分析JDK1.7的源码。

源码分析

用到的实例常量

1
2
3
4
5
6
7
8
9
10
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 	//默认初始容量：2^4 = 16

static final float DEFAULT_LOAD_FACTOR = 0.75f;		//默认加载因子：0.75

static final int MAXIMUM_CAPACITY = 1 << 30;		//最大容量：2^30

/**
 * An empty table instance to share when the table is not inflated.
 */
static final Entry<?,?>[] EMPTY_TABLE = {};     //一个空的哈希桶

用到的实例变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int threshold;		//扩容阀值

final float loadFactor;		//加载因子

/**
 * The table, resized as necessary. Length MUST Always be a power of two.
 */
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;  //哈希桶

transient int modCount;     //HashMap修改次数

transient int size;         //当前的键值对数量

transient int hashSeed = 0;     //用于判断hash是否需要更新，若为0则禁止替换hash值

Entry（链表节点）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
  static class Entry<K,V> implements Map.Entry<K,V> {
      final K key;
      V value;
      Entry<K,V> next;    //下一节点
      int hash;

      /**
       * Creates new entry.
       */
      Entry(int h, K k, V v, Entry<K,V> n) {
          value = v;
          next = n;
          key = k;
          hash = h;
      }

      public final K getKey() {
          return key;
      }

      public final V getValue() {
          return value;
      }

      public final V setValue(V newValue) {
          V oldValue = value;
          value = newValue;
          return oldValue;
      }

//只有两者的key和value通过equals比较后都返回true才为true
      public final boolean equals(Object o) {
          if (!(o instanceof Map.Entry))
              return false;
          Map.Entry e = (Map.Entry)o;
          Object k1 = getKey();
          Object k2 = e.getKey();
          if (k1 == k2 || (k1 != null && k1.equals(k2))) {
              Object v1 = getValue();
              Object v2 = e.getValue();
              if (v1 == v2 || (v1 != null && v1.equals(v2)))
                  return true;
          }
          return false;
      }

//将key和value的hashCode值进行异或操作即得到hashCode
      public final int hashCode() {
          return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
      }

      public final String toString() {
          return getKey() + "=" + getValue();
      }

      //...
  }

需要用到的方法

inflateTable

初始化哈希桶，保证哈希桶的容量是2的n次幂。

1
2
3
4
5
6
7
8
9
  private void inflateTable(int toSize) {
      //获取初始容量：大于等于toSize的最小的2^n	
      int capacity = roundUpToPowerOf2(toSize);
//指定新的扩容阀值
      threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
//初始化哈希桶
      table = new Entry[capacity];
      initHashSeedAsNeeded(capacity);
  }

resize

传入新桶容量，进行扩容操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
  void resize(int newCapacity) {
      Entry[] oldTable = table;
      int oldCapacity = oldTable.length;
//如果原哈希桶的长度等于最大容量，直接返回
      if (oldCapacity == MAXIMUM_CAPACITY) {
          threshold = Integer.MAX_VALUE;
          return;
      }

//根据新的容量创建新的哈希桶
      Entry[] newTable = new Entry[newCapacity];
//将旧桶中的所有元素放入新桶
      transfer(newTable, initHashSeedAsNeeded(newCapacity));
//更新哈希桶
      table = newTable;
//更新扩容阀值
      threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
  }

transfer

将旧桶中的所有元素转移到新桶中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
  void transfer(Entry[] newTable, boolean rehash) {
      int newCapacity = newTable.length;
//将旧桶中的所有元素转移到新桶中
      for (Entry<K,V> e : table) {
          while(null != e) {
              Entry<K,V> next = e.next;
              if (rehash) {	//如果需要重新计算哈希值
                  e.hash = null == e.key ? 0 : hash(e.key);
              }
		//i为节点e在新桶中的位置
              int i = indexFor(e.hash, newCapacity);
		//节点e成为第i个桶的头结点
              e.next = newTable[i];
              newTable[i] = e;
		//e赋值为下一节点
              e = next;
          }
      }
  }

hash

根据传入的key计算其hash值

1
2
3
4
5
6
7
8
9
10
11
  final int hash(Object k) {
      int h = hashSeed;
//如果hashSeed不等于0且key为String类型，使用另一个优化后的hash函数
      if (0 != h && k instanceof String) {	
          return sun.misc.Hashing.stringHash32((String) k);
      }

      h ^= k.hashCode();
      h ^= (h >>> 20) ^ (h >>> 12);
      return h ^ (h >>> 7) ^ (h >>> 4);	
  }

可以看到该方法进行了多次移位和异或操作，这样做是为了降低哈希冲突，使得键值对的分布相对均匀

indexFor

该方法传入一个hash值以及哈希桶容量，返回对应哈希桶索引

1
2
3
4
5
  static int indexFor(int h, int length) {
      //由于保证了哈希桶容量length为2的n次幂，所以h与(length-1)进行与操作，
//就相当于对length取模
      return h & (length-1);
  }

构造方法

和1.8版本一样，1.7版本也有四个构造方法。

默认构造方法，使用默认的初始容量和加载因子

1
2
3
public HashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

可以指定初始容量的构造方法

1
2
3
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

前两个方法都是调用该构造方法，该方法可同时指定初始容量和加载因子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  public HashMap(int initialCapacity, float loadFactor) {
      if (initialCapacity < 0)
          throw new IllegalArgumentException("Illegal initial capacity: " +
                                             initialCapacity);
      if (initialCapacity > MAXIMUM_CAPACITY)
          initialCapacity = MAXIMUM_CAPACITY;
      if (loadFactor <= 0 || Float.isNaN(loadFactor))
          throw new IllegalArgumentException("Illegal load factor: " +
                                             loadFactor);
//初始容量不能小于0，也不能超过最大容量；加载因子必须大于0									  

      this.loadFactor = loadFactor;
      threshold = initialCapacity;	//扩容阀值等于初始化容量
      init();		//一个默认的空方法
  }

和1.8版本不同的是，扩容阀值等于初始化容量。

还有个构造方法，根据传入的Map构造HashMap

1
2
3
4
5
6
7
8
9
  public HashMap(Map<? extends K, ? extends V> m) {
//先调用构造方法指定扩容阀值和加载因子
      this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                    DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
//确定初始容量，指定扩容阀值并初始化哈希桶
      inflateTable(threshold);
//将传入Map的所有元素加入到新的HashMap中
      putAllForCreate(m);
  }

put（增、改）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
  public V put(K key, V value) {
//如果哈希桶为空，需先初始化哈希桶
      if (table == EMPTY_TABLE) {	
          inflateTable(threshold);
      }
//如果key为null，需要另行处理
      if (key == null) {
	return putForNullKey(value);
}
          
      int hash = hash(key);	//计算该key的hash值
      int i = indexFor(hash, table.length);	//根据hash值获取其存放位置
//遍历其存放位置的所有节点，看是否存在相同的key
      for (Entry<K,V> e = table[i]; e != null; e = e.next) {
          Object k;	//k存放当前遍历到的节点的key
	//如果找到相同的key，更新value并返回旧的value
          if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
              V oldValue = e.value;
              e.value = value;
              e.recordAccess(this);
              return oldValue;
          }
      }

//如果没找到相同的key，则新增该键值对并返回null
      modCount++;
      addEntry(hash, key, value, i);
      return null;
  }

put方法的基本步骤：

  1. 先判断哈希桶是否为空，为空需先初始化哈希桶。
  2. 判断传入的key是否为null，为null的话需要另行处理：判断第0号哈希桶是否存在key为null的节点，如果存在则更新value并返回旧的value，否则将该键值对放入第0号哈希桶。
  3. 根据该key的hash值获取到对应的哈希桶，遍历该哈希桶中的链表，如果找到相同的key，则更新value并返回旧value。否则，创建该新节点并将其放入对应的哈希桶，成为该哈希桶新的头结点，原头结点成为它的下一节点。然后方法结束，返回null。

putForNullKey

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  private V putForNullKey(V value) {
//查看第0号哈希桶是否存放过null，如果已经放过null就更新value，返回旧value
      for (Entry<K,V> e = table[0]; e != null; e = e.next) {
          if (e.key == null) {
              V oldValue = e.value;
              e.value = value;
              e.recordAccess(this);
              return oldValue;
          }
      }
//如果第0号哈希桶没有存放null，则将其存入第0号哈希桶
      modCount++;
      addEntry(0, null, value, 0);
      return null;
  }

addEntry

1
2
3
4
5
6
7
8
9
10
  void addEntry(int hash, K key, V value, int bucketIndex) {
//如果当前键值对数量到达扩容阀值，并且要添加的键值对所对应的哈希桶不为空
      if ((size >= threshold) && (null != table[bucketIndex])) {
          resize(2 * table.length);	//进行扩容操作，扩容为原来的两倍
          hash = (null != key) ? hash(key) : 0;	//重新计算其hash值
          bucketIndex = indexFor(hash, table.length);	//重新计算其存储位置
      }
//创建新的键值对并将其添加到对应的哈希桶
      createEntry(hash, key, value, bucketIndex);
  }

createEntry

1
2
3
4
5
6
7
8
  void createEntry(int hash, K key, V value, int bucketIndex) {
//e存储当前头结点
      Entry<K,V> e = table[bucketIndex];	
//新增的键值对成为该位置的头结点，之前的头结点作为其下一节点
      table[bucketIndex] = new Entry<>(hash, key, value, e);
//更新当前键值对数量
      size++;
  }

remove（删）

1
2
3
4
5
  public V remove(Object key) {
      Entry<K,V> e = removeEntryForKey(key);
//如果没有找到该key，返回null，否则返回删除的键值对的value
      return (e == null ? null : e.value);
  }

removeEntryForKey

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
  final Entry<K,V> removeEntryForKey(Object key) {
      if (size == 0) {	//键值对数量为0，直接返回null
          return null;
      }
      int hash = (key == null) ? 0 : hash(key);	//hash为该key的hash值
      int i = indexFor(hash, table.length);		//找到其在哈希桶中的位置
      Entry<K,V> prev = table[i];
      Entry<K,V> e = prev;

//遍历单链表，查找要删除的节点
      while (e != null) {
          Entry<K,V> next = e.next;
          Object k;	//k用于存储当前节点的key
	//若找到要删除的键值对
          if (e.hash == hash &&
              ((k = e.key) == key || (key != null && key.equals(k)))) {
              modCount++;
              size--;
		//删除并返回该键值对
              if (prev == e)
                  table[i] = next;
              else
                  prev.next = next;
              e.recordRemoval(this);
              return e;
          }
          prev = e;
          e = next;
      }

//若没有找到要删除的节点，返回null
      return e;
  }

删除节点的步骤如下：

  1. 如果当前键值对的数量为0，直接返回null
  2. 根据传入的key计算出其hash值，并找到对应的哈希桶。遍历该哈希桶中的链表，如果找到要删除的节点就删除并返回该节点，否则返回null。

get（查）

1
2
3
4
5
6
7
8
9
10
  public V get(Object key) {
//如果要查找的key为null，要另行处理
      if (key == null) {
	return getForNullKey();
}
          
      Entry<K,V> entry = getEntry(key);
//如果找到该key对应的键值对，返回其value，否则返回null
      return null == entry ? null : entry.getValue();
  }

getForNullKey

1
2
3
4
5
6
7
8
9
10
11
12
13
  private V getForNullKey() {
//如果当前键值对数量为0，直接返回null
      if (size == 0) {
          return null;
      }
//遍历第0号哈希桶的单链表，找到key为null的键值对就返回其value
      for (Entry<K,V> e = table[0]; e != null; e = e.next) {
          if (e.key == null)
              return e.value;
      }
//没有找到key为null的键值对，返回null
      return null;
  }

getEntry

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
  final Entry<K,V> getEntry(Object key) {
//如果当前键值对数量为0，直接返回null
      if (size == 0) {
          return null;
      }

//先计算出该key对应的hash值
      int hash = (key == null) ? 0 : hash(key);
//遍历hash值对应的哈希桶中的单链表
      for (Entry<K,V> e = table[indexFor(hash, table.length)];
           e != null;
           e = e.next) {
          Object k;
	//若找到对应的key，返回该键值对
          if (e.hash == hash &&
              ((k = e.key) == key || (key != null && key.equals(k))))
              return e;
      }
//没有找到对应的key，返回null
      return null;
  }

get方法的执行步骤：

  1. 先判断要查找的key是否为null，为null的话另行处理。无论key是否为null，都要先判断当前键值对数量是否为0，为0直接返回null。
  2. 如果key为null，则遍历第0号哈希桶的链表，如果找到key为null的键值对，返回其value，否则返回null。
  3. 如果key不为null，先计算该key的hash值，然后根据该hash值找到相应的哈希桶。遍历该哈希桶的链表，如果找到对应的key，返回该键值对的value，否则返回null。

小结

这里小结一下查看了源码后，对1.7版本HashMap的一些新认识：

  1. 单个键值对存储在Entry类中，利用Entry数组存储多个键值对，利用拉链法来解决哈希冲突，多个冲突的键值对利用链表存储起来。
  2. 一开始的扩容阀值（在构造方法中确定）等于初始容量（该初始容量不一定是2的n次幂），但是在初始化哈希桶数组时，哈希桶数组的长度是大于等于扩容阀值的最小的2的n次幂，也即是最终哈希桶数组的初始长度是大于等于初始容量的最小的2的n次幂（和1.8版本一样）。
  3. key为null的键值对放在第0号哈希桶。
  4. 当键值对数量达到扩容阀值时，进行扩容并重新分配元素的位置，新的容量是原来的两倍。

参考

-------------　　　　本文到此结束　　感谢您的阅读　　　　-------------
0%