Java集合系列之HashMap源码分析

//默认初始容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

//默认最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;

//默认加载因子, 指哈希表可以达到多满的尺度
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//空的哈希表
static final Entry<?,?>[] EMPTY_TABLE = {};

//实际使用的哈希表
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

//HashMap大小, 即HashMap存储的键值对数量
transient int size;

//键值对的阈值, 用于判断是否需要扩增哈希表容量
int threshold;

//加载因子
final float loadFactor;

//修改次数, 用于fail-fast机制
transient int modCount;

//使用替代哈希的默认阀值
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;

//随机的哈希种子, 有助于减少哈希碰撞的次数
transient int hashSeed = 0;

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

//构造器, 传入初始化容量和加载因子
public HashMap(int initialCapacity, float loadFactor) {
  if (initialCapacity < 0) {
    throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
  }
  //如果初始化容量大于最大容量, 就把它设为最大容量
  if (initialCapacity > MAXIMUM_CAPACITY) {
    initialCapacity = MAXIMUM_CAPACITY;
  }
  //如果加载因子小于0或者加载因子不是浮点数, 则抛出异常
  if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
    throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
  }
  //设置加载因子
  this.loadFactor = loadFactor;
  //阈值为初始化容量
  threshold = initialCapacity;
  init();
}

void init() {}

//放置key-value键值对到HashMap中
public V put(K key, V value) {
  //如果哈希表没有初始化就进行初始化
  if (table == EMPTY_TABLE) {
    //初始化哈希表
    inflateTable(threshold);
  }
  if (key == null) {
    return putForNullKey(value);
  }
  //计算key的hash码
  int hash = hash(key);
  //根据hash码定位在哈希表的位置
  int i = indexFor(hash, table.length);
  for (Entry<K,V> e = table[i]; e != null; e = e.next) {
    Object k;
    //如果对应的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;
    }
  }
  modCount++;
  //如果没有对应的key就添加Entry到HashMap中
  addEntry(hash, key, value, i);
  //添加成功返回null
  return null;
}

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

//添加Entry方法, 先判断是否要扩容
void addEntry(int hash, K key, V value, int bucketIndex) {
  //如果HashMap的大小大于阀值并且哈希表对应槽位的值不为空
  if ((size >= threshold) && (null != table[bucketIndex])) {
    //因为HashMap的大小大于阀值, 表明即将发生哈希冲突, 所以进行扩容
    resize(2 * table.length);
    hash = (null != key) ? hash(key) : 0;
    bucketIndex = indexFor(hash, table.length);
  }
  //在这里表明HashMap的大小没有超过阀值, 所以不需要扩容
  createEntry(hash, key, value, bucketIndex);
}

//对哈希表进行扩容
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);
}

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

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