HashMap源码要点整理
0. 先看下支持实现的几个属性
除了modCount，还有
- transient Entry<K,V>[] table;
- transient int size;
- int threshold;
- final float loadFactor;
size和ArrayList一样，是map中实际存入数据的多少，而非数组table的长度。threshold是map需要扩容的限值，loadFactor则是当前hash存储结构的装载因子。table是实现hash存储的主要结构，是一个Entry数组。简单看下（HashMap的）Entry结构
- final K key;
- V value;
- Entry<K,V> next;
- int hash;
其中key和value就不多说了。next是hash发生冲突时，同在一个slot下的entry链表的指向下一个node的指针。hash则是根据key计算出来的散列值。
1. 最基本的操作put()和get()
HashMap对这两个操作的查找过程实际上是一样的。put的key如果已存在，实际是更新value值。
首先，对于key为null的情况，直接映射到table[0]，再通过冲突链表找到key确实是null的Entry。
对于其他大部分情况，查找entry的方式是一致的，以put()源码为例。
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}先对key对象做散列计算，这个版本不同具体计算方法有可能不同。再根据此散列值结合table数组的长度做与运算，取得次entry在表中的位置。后面的循环则是为了解决冲突所做的链表查找。
这个过程需要注意有两点。第一个是entry的hash值是根据key对象的hashCode()计算得出，第二个则是下面寻找entry的对比，用的是&&条件，意思是只要e.hash==hash不满足，则不认为这个entry是要找到的entry。
其中的e.recordAccess()实际上是为继承HashMap的LinkedHashMap维护访问顺序维护列表收集数据，HashMap类本身实现为空。
对于put()方法，如果没有找到key对应的entry，则添加entry。
2. 添加新的Entry对象和扩容
添加新的Entry实际上是addEntry()中调用的createEntry()方法调用的，实现也很简单，就是传给(HashMap的)Entry构造方法四个参数值，并放入table数组指定位置。需要注意的是，如果原Index处的slot已经有entry数据，即发生冲突，则新Entry放在前面，把之前的列表接在新entry的后面。
更需要注意的是HashMap的扩容。在addEntry()方法的开始处，就要进行判断，size值是不是已经等于甚至超过threshold阈值了，如果已达到，则必须扩容处理并全面重新映射。
对于容量，HashMap都是采用2的整数次幂，默认初始容量16，装载因子0.75，即无参构造HashMap对象时，首次最多放12个元素。
扩容时也是一样，都是double扩容，new一个原容量2倍的新Entry数组newTable。更重要的是，此后的Entry数据迁移工作，每个节点要重新做hash映射。这个过程是要把所有entry节点都过一遍。最后，修改threshold阈值。
和用ArrayList需要强调的一样，对于HashMap对象，扩容也是一件成本很高的事情，所以最好在使用前明确容量需求，避免扩容和重新映射。
对于装载因子也要考虑，装载因子太小，过度浪费无用空间，如果装载因子太大，则发生hash冲突的可能性大大增加，冲突发生的情况就是链表查找元素，效率会大大降低。
3. HashSet的实现
HashSet实际上是基于HashMap的keySet实现。而keySet实际上又是对HashSet进行封装后的一个“窗口”而已。
4. LinkedHashMap的实现
java.util.LinkedHashMap类是HashMap的一个子类，即继承于它。
对于LinkedHashMap本身，只是增加了两个属性：（LinkedHashMap的）Entry链表头节点对象和accessOrder的布尔值。前者为HashMap维护了一个顺序相关的节点链表，而后者则根据初始化参数确定是维护插入顺序还是访问顺序。
对于LinkedHashMap的Entry节点类，也是继承于HashMap.Entry，增加了before和after引用，维协助维护双向链表。
至于HashMap的其它细节，其实在初步了解了其结构后，都很容易想明白，就不赘述了。HashMap因为查找效率高，通常是Map的默认选择，也是《Thinking in Java》书中提到的“没有特殊需求之必选”。而使用好HashMap，需要注意的主要是扩容重映射的成本和元素对象（key）的hashCode()的意义以及散列冲突带来的影响。