Java HashMap用法及知识点总结

/**
 * Hash table based implementation of the <tt>Map</tt> interface. This
 * implementation provides all of the optional map operations, and permits
 * <tt>null</tt> values and the <tt>null</tt> key. (The <tt>HashMap</tt>
 * class is roughly equivalent to <tt>Hashtable</tt>, except that it is
 * unsynchronized and permits nulls.) This class makes no guarantees as to
 * the order of the map; in particular, it does not guarantee that the order
 * will remain constant over time.
 * <p>This implementation provides constant-time performance for the basic
 * operations (<tt>get</tt> and <tt>put</tt>), assuming the hash function
 * disperses the elements properly among the buckets. Iteration over
 * collection views requires time proportional to the "capacity" of the
 * <tt>HashMap</tt> instance (the number of buckets) plus its size (the number
 * of key-value mappings). Thus, it's very important not to set the initial
 * capacity too high (or the load factor too low) if iteration performance is
 * important.
 * <p>An instance of <tt>HashMap</tt> has two parameters that affect its
 * performance: <i>initial capacity</i> and <i>load factor</i>. The
 * <i>capacity</i> is the number of buckets in the hash table, and the initial
 * capacity is simply the capacity at the time the hash table is created. The
 * <i>load factor</i> is a measure of how full the hash table is allowed to
 * get before its capacity is automatically increased. When the number of
 * entries in the hash table exceeds the product of the load factor and the
 * current capacity, the hash table is <i>rehashed</i> (that is, internal data
 * structures are rebuilt) so that the hash table has approximately twice the
 * number of buckets.
 * <p>As a general rule, the default load factor (.75) offers a good
 * tradeoff between time and space costs. Higher values decrease the
 * space overhead but increase the lookup cost (reflected in most of
 * the operations of the <tt>HashMap</tt> class, including
 * <tt>get</tt> and <tt>put</tt>). The expected number of entries in
 * the map and its load factor should be taken into account when
 * setting its initial capacity, so as to minimize the number of
 * rehash operations. If the initial capacity is greater than the
 * maximum number of entries divided by the load factor, no rehash
 * operations will ever occur.
 * <p>If many mappings are to be stored in a <tt>HashMap</tt>
 * instance, creating it with a sufficiently large capacity will allow
 * the mappings to be stored more efficiently than letting it perform
 * automatic rehashing as needed to grow the table. Note that using
 * many keys with the same {@code hashCode()} is a sure way to slow
 * down performance of any hash table. To ameliorate impact, when keys
 * are {@link Comparable}, this class may use comparison order among
 * keys to help break ties.
 * <p><strong>Note that this implementation is not synchronized.</strong>
 * If multiple threads access a hash map concurrently, and at least one of
 * the threads modifies the map structurally, it <i>must</i> be
 * synchronized externally. (A structural modification is any operation
 * that adds or deletes one or more mappings; merely changing the value
 * associated with a key that an instance already contains is not a
 * structural modification.) This is typically accomplished by
 * synchronizing on some object that naturally encapsulates the map.
 * If no such object exists, the map should be "wrapped" using the
 * {@link Collections#synchronizedMap Collections.synchronizedMap}
 * method. This is best done at creation time, to prevent accidental
 * unsynchronized access to the map:<pre>
 *  Map m = Collections.synchronizedMap(new HashMap(...));</pre>
 * <p>The iterators returned by all of this class's "collection view methods"
 * are <i>fail-fast</i>: if the map is structurally modified at any time after
 * the iterator is created, in any way except through the iterator's own
 * <tt>remove</tt> method, the iterator will throw a
 * {@link ConcurrentModificationException}. Thus, in the face of concurrent
 * modification, the iterator fails quickly and cleanly, rather than risking
 * arbitrary, non-deterministic behavior at an undetermined time in the
 * future.
 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
 * as it is, generally speaking, impossible to make any hard guarantees in the
 * presence of unsynchronized concurrent modification. Fail-fast iterators
 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
 * Therefore, it would be wrong to write a program that depended on this
 * exception for its correctness: <i>the fail-fast behavior of iterators
 * should be used only to detect bugs.</i>
 * <p>This class is a member of the
 * <a href="{@docRoot}/../technotes/guides/collections/index.html" rel="external nofollow" >
 * Java Collections Framework</a>.
 * @param <K> the type of keys maintained by this map
 * @param <V> the type of mapped values
 * @author Doug Lea
 * @author Josh Bloch
 * @author Arthur van Hoff
 * @author Neal Gafter
 * @see   Object#hashCode()
 * @see   Collection
 * @see   Map
 * @see   TreeMap
 * @see   Hashtable
 * @since  1.2
 **/

//默认初始容量
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.stringHash32((String) k);
  }
  h ^= k.hashCode();
  //扰动函数
  h ^= (h >>> 20) ^ (h >>> 12);
  return h ^ (h >>> 7) ^ (h >>> 4);
}