Java集合系列[3]----HashMap源码分析

 1 //默认初始容量
 2 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
 3 
 4 //默认最大容量
 5 static final int MAXIMUM_CAPACITY = 1 << 30;
 6 
 7 //默认加载因子, 指哈希表可以达到多满的尺度
 8 static final float DEFAULT_LOAD_FACTOR = 0.75f;
 9 
10 //空的哈希表
11 static final Entry<?,?>[] EMPTY_TABLE = {};
12 
13 //实际使用的哈希表
14 transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
15 
16 //HashMap大小, 即HashMap存储的键值对数量
17 transient int size;
18 
19 //键值对的阈值, 用于判断是否需要扩增哈希表容量
20 int threshold;
21 
22 //加载因子
23 final float loadFactor;
24 
25 //修改次数, 用于fail-fast机制
26 transient int modCount;
27 
28 //使用替代哈希的默认阀值
29 static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
30 
31 //随机的哈希种子, 有助于减少哈希碰撞的次数
32 transient int hashSeed = 0;

1 static class Entry<K,V> implements Map.Entry<K,V> {
2     final K key;      //键
3     V value;          //值
4     Entry<K,V> next;  //下一个Entry的引用
5     int hash;         //哈希码
6     
7     ...               //省略下面代码
8 }

 1 //构造器, 传入初始化容量和加载因子
 2 public HashMap(int initialCapacity, float loadFactor) {
 3     if (initialCapacity < 0) {
 4         throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
 5     }
 6     //如果初始化容量大于最大容量, 就把它设为最大容量
 7     if (initialCapacity > MAXIMUM_CAPACITY) {
 8         initialCapacity = MAXIMUM_CAPACITY;
 9     }
10     //如果加载因子小于0或者加载因子不是浮点数, 则抛出异常
11     if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
12         throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
13     }
14     //设置加载因子
15     this.loadFactor = loadFactor;
16     //阈值为初始化容量
17     threshold = initialCapacity;
18     init();
19 }
20 
21 void init() {}

 1 //放置key-value键值对到HashMap中
 2 public V put(K key, V value) {
 3     //如果哈希表没有初始化就进行初始化
 4     if (table == EMPTY_TABLE) {
 5         //初始化哈希表
 6         inflateTable(threshold);
 7     }
 8     if (key == null) {
 9         return putForNullKey(value);
10     }
11     //计算key的hash码
12     int hash = hash(key);
13     //根据hash码定位在哈希表的位置
14     int i = indexFor(hash, table.length);
15     for (Entry<K,V> e = table[i]; e != null; e = e.next) {
16         Object k;
17         //如果对应的key已经存在, 就替换它的value值, 并返回原先的value值
18         if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
19             V oldValue = e.value;
20             e.value = value;
21             e.recordAccess(this);
22             return oldValue;
23         }
24     }
25     modCount++;
26     //如果没有对应的key就添加Entry到HashMap中
27     addEntry(hash, key, value, i);
28     //添加成功返回null
29     return null;
30 }

 1 //初始化哈希表, 会对哈希表容量进行膨胀, 因为有可能传入的容量不是2的幂
 2 private void inflateTable(int toSize) {
 3     //哈希表容量必须是2的次幂
 4     int capacity = roundUpToPowerOf2(toSize);
 5     //设置阀值, 这里一般是取capacity*loadFactor
 6     threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
 7     //新建指定容量的哈希表
 8     table = new Entry[capacity];
 9     //初始化哈希种子
10     initHashSeedAsNeeded(capacity);
11 }

 1 //添加Entry方法, 先判断是否要扩容
 2 void addEntry(int hash, K key, V value, int bucketIndex) {
 3     //如果HashMap的大小大于阀值并且哈希表对应槽位的值不为空
 4     if ((size >= threshold) && (null != table[bucketIndex])) {
 5         //因为HashMap的大小大于阀值, 表明即将发生哈希冲突, 所以进行扩容
 6         resize(2 * table.length);
 7         hash = (null != key) ? hash(key) : 0;
 8         bucketIndex = indexFor(hash, table.length);
 9     }
10     //在这里表明HashMap的大小没有超过阀值, 所以不需要扩容
11     createEntry(hash, key, value, bucketIndex);
12 }
13 
14 //对哈希表进行扩容
15 void resize(int newCapacity) {
16     Entry[] oldTable = table;
17     int oldCapacity = oldTable.length;
18     //如果当前已经是最大容量就只能增大阀值了
19     if (oldCapacity == MAXIMUM_CAPACITY) {
20         threshold = Integer.MAX_VALUE;
21         return;
22     }
23     //否则就进行扩容
24     Entry[] newTable = new Entry[newCapacity];
25     //迁移哈希表的方法
26     transfer(newTable, initHashSeedAsNeeded(newCapacity));
27     //将当前哈希表设置为新的哈希表
28     table = newTable;
29     //更新哈希表阈值
30     threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
31 }

1 //返回哈希码对应的数组下标
2 static int indexFor(int h, int length) {
3     return h & (length-1);
4 }

 1 //生成hash码的函数
 2 final int hash(Object k) {
 3     int h = hashSeed;
 4     //key是String类型的就使用另外的哈希算法
 5     if (0 != h && k instanceof String) {
 6         return sun.misc.Hashing.stringHash32((String) k);
 7     }
 8     h ^= k.hashCode();
 9     //扰动函数
10     h ^= (h >>> 20) ^ (h >>> 12);
11     return h ^ (h >>> 7) ^ (h >>> 4);
12 }