HashMap继承于AbstractMap，实现了Map接口，同时标记了Cloneable和Serializable接口。
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, SerializableHashMap提供了四个构造函数： (1) HashMap()：构造一个初始容量为16和加载因子为0.75的空HashMap。 (2) HashMap(int initialCapacity)：构造一个带指定初始容量和默认加载因子0.75的空HashMap。 (3) HashMap(int initialCapacity, float loadFactor)：构造一个带指定初始容量和指定加载因子的空HashMap。 (4) HashMap(Map
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); putAllForCreate(m); } PRivate void inflateTable(int toSize) { // Find a power of 2 >= toSize，计算出大于toSize的最小的2的n次方值。 int capacity = roundUpToPowerOf2(toSize); // 设置HashMap的容量极限，当HashMap的容量达到该极限时就会进行扩容操作 threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); // 初始化table数组 table = new Entry[capacity]; // Initialize the hashing mask value. We defer initialization until we really need it. initHashSeedAsNeeded(capacity); }初始容量是创建哈希表时的桶的数量， 加载因子是哈希表容量扩展前可以达到多满的一种尺度，它衡量的是一个散列表的空间的使用程度。负载因子越大，表示散列表的装填程度越高、对空间的利用更充分，后果却是查找效率的降低；而负载因子太小，那么散列表的数据将过于稀疏，对空间的利用存在着浪费。
从构造函数中可以看出，HashMap本质是一个table数组，table数组里的元素是Entry链表。Entry为HashMap的内部类，它包含了键key、值value、下一个节点next以及hash值，正是由于Entry才构成了table数组的项为链表。
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; } // 部分源码略去put(K key, V value)方法的源码如下。基本过程是： 1. 判断key是否为null，若为null，则直接调用putForNullKey方法。 2. key不为空则计算key的hash值，再根据hash值搜索key落在哪个桶上。 3. 对该桶上的Entry链表进行遍历，如果该链表上存在相同的key，则覆盖原来key的value，否则将该元素保存在链头（最先保存的元素放在链尾）。
public V put(K key, V value) { if (table == EMPTY_TABLE) { inflateTable(threshold); } // 当key为null，调用putForNullKey方法，保存null到table的第一个位置，这就是HashMap允许为null的原因 if (key == null) return putForNullKey(value); // 计算key的hash值 int hash = hash(key); // 计算key的hash值在table数组中的位置，即落在哪一个桶上 int i = indexFor(hash, table.length); // 迭代该桶上的Entry链表,找到key保存的位置 for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; // 判断该链表上是否有相同的hash值和相同的key（仅仅判断hash值是否相同是不够的） if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { // 若存在相同，则直接覆盖value，返回旧value V oldValue = e.value; e.value = value; e.recordaccess(this); return oldValue; } } //修改次数增加1 modCount++; // 该链表上不存在相同的hash值和key，则将key、value添加至i位置处 addEntry(hash, key, value, i); return null; }以上的存储机制也解释了HashSet是如何保证元素唯一性的。
这里需要强调下indexFor方法。HashMap就是通过该方法实现均匀分布table数据和充分利用空间的。初始化时，我们保证了capacity是大于初始容量的最小的2的n次方值。当length = 2^n时，不同的hash值发生碰撞的概率比较小，从而数据在table数组中分布较均匀，查询速度也较快。
/** * Returns index for hash code h. */ static int indexFor(int h, int length) { // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2"; return h & (length-1); }最后看一下链的产生和扩容问题。 1. 链的产生：系统总是将新创建的Entry放入bucketIndex索引处。如果bucketIndex处已经有了对象，那么新添加的Entry对象将指向原有的Entry对象，形成一条Entry链；如果bucketIndex处还没有Entry对象，那么新添加的Entry对象将指向null。在table数组未扩容的情况下，两个元素的hash值相同，就意味着它们会在同一个桶上。 2. 扩容问题：当HashMap中元素的数量等于table数组长度*加载因子，就会触发扩容操作。扩容操作需尽量避免，因为它需要重新计算这些元素在新table数组中的位置并进行复制处理。
void addEntry(int hash, K key, V value, int bucketIndex) { // 若HashMap中元素的个数超过极限了，则容量扩大两倍 if ((size >= threshold) && (null != table[bucketIndex])) { resize(2 * table.length); hash = (null != key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); } createEntry(hash, key, value, bucketIndex); } void createEntry(int hash, K key, V value, int bucketIndex) { // 获取bucketIndex处的Entry Entry<K,V> e = table[bucketIndex]; // 将新创建的Entry放入bucketIndex索引处，并让新的Entry指向原来的Entry e table[bucketIndex] = new Entry<>(hash, key, value, e); size++; }新闻热点
疑难解答
