HashMap是我们最常用的类之一，它实现了hash算法，虽然使用很简单，但是其实现有很多值得研究的地方。
HashMap存储的是key-value形式的键值对，这个键值对在实现中使用一个静态内部类Entry来表示，它存储了key、value、hash值、以及在hash冲突时链表中下一个元素的引用。
HashMap底层实现使用了一个数组来存储元素。它的初始容量默认是16，而且必须容量必须是2的整数次幂，最大容量是1<<30（10.7亿+），同时还使用一个加载因子（load factor）来控制这个map的这个hash表的扩容，默认为0.75，即当容量达到初始容量3/4时会扩容（当然不只这样，后面会说明）。
在往HashMap中添加元素时，会计算key的hashCode，然后基于这个hashCode和数组大小来确定它在数组中的存储位置，当遇到hash冲突时，会以链表的形式存储在数组中。
下面具体看看源码，首先看构造方法
[java] view plain copy public HashMap(int initialCapacity, float loadFactor) { // 初始容量不能小于0，否则会抛出异常 if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); // 控制初始容量不能大于最大容量1<<30 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方法是留给子类扩展 init(); } 可以看到在创建HashMap时，并不分配内存空间，而是在真正往map中添加数据时才会分配，可以从put方法中看到：
[java] view plain copy public V put(K key, V value) { // 创建时未分配空间，所以检查如果还是空表的话，就分配内存空间 if (table == EMPTY_TABLE) { inflateTable(threshold); } // 对null的key进行的特殊处理 if (key == null) return putForNullKey(value); // 计算key的hashCode int hash = hash(key); // 根据hashCode和当前容量来确定元素在hash表中的位置，即hash桶的位置 int i = indexFor(hash, table.length); // 检查key是否已经存在，如果已经存在，则替换旧值为新值，并返回旧值 for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; // 这里可以看到是根据hashCode和equals方法来判断一个key是否已经存在 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } // 增加map的修改次数，这用于实现fail-fast机制 modCount++; // 真正把元素添加到hash表中指定的索引位置处理（也叫hash桶） addEntry(hash, key, value, i); // 返回null表示key之前不存在 return null; } void addEntry(int hash, K key, V value, int bucketIndex) { // 判断是否需要扩容，当前容量达到阙值，并且产生了hash冲突（指定hash桶已经有元素存在） if ((size >= threshold) && (null != table[bucketIndex])) { // 容量扩展为之前的2倍 resize(2 * table.length); hash = (null != key) ? hash(key) : 0; // 重新计算存储的hash桶位置 bucketIndex = indexFor(hash, table.length); } // 创建Entry并存储到hash表中 createEntry(hash, key, value, bucketIndex); } void createEntry(int hash, K key, V value, int bucketIndex) { // 取出之前已经存在的元素 Entry<K,V> e = table[bucketIndex]; // 把新元素放到链表的开头，即让新元素的next引用指向之前已经存在的元素 table[bucketIndex] = new Entry<>(hash, key, value, e); // 修改元素计数 size++; } 从代码中可以看到， 扩容需要满足以下两个条件 ：
达到加载因子指定的阙值put当前值时发生hash冲突（即当前桶的位置已经存在有元素了）
只是当前容器中key value数量超过阙值是不会进行扩容的。就是说，比如初始容量为16，当达到阙值以前发生大量的hash冲突，而后添加的元素又很少发生hash冲突，那么有可能key value的数量超过16*0.75=12甚至超过16都不进行扩容，所以hash算法必须保证分布均匀，尽量减少hash冲突。
上面是添加元素的实现，这里再看看它是如何初始化并分配内存的：
[java] view plain copy private void inflateTable(int toSize) { // 保证容量是2的整数次幂 int capacity = roundUpToPowerOf2(toSize); // 在初始化的时候就把扩容的阙值计算好并保存，避免每次都重新计算 threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); // 这里才会真正的分配内存 table = new Entry[capacity]; // 初始化hash种子 initHashSeedAsNeeded(capacity); } /** * 保证容量是2的整数次幂，并且不超过最大容量。 * 比如：传入的是15，值变成16，传入的是17，则会变成32， * 即大于当前值且与最接近2的整数次幂的数 */ private static int roundUpToPowerOf2(int number) { // 保证容量是2的整数次幂，并且不超过最大容量 return number >= MAXIMUM_CAPACITY ? MAXIMUM_CAPACITY : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1; } 对null key的特殊处理：
[java] view plain copy private V putForNullKey(V value) { // 如果已经存在，则替换旧值 for (Entry<K,V> e = table[0]; e != null; e = e.next) { if (e.key == null) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } // 增加map的修改次数，这用于实现fail-fast机制 modCount++; // null key的hashCode固定为0，并且桶的位置也固定为0 addEntry(0, null, value, 0); return null; } 再来看如何确定非null key的位置
[java] view plain copy static int indexFor(int h, int length) { return h & (length-1); } h是key的hashCode，length是当前hash表的最大长度，h & (length-1)与h % length等价，只是前者使用位运算，而位运算比取模运算速度更快。这里为什么可以用&运算代替取模运算呢？因为length是2的整数次幂，而它减1，低位正好全是1，与另一个数进行&运算，结果肯定不会超过length，与%运算的效果一样。如果length不是2的整数次幂，那么是不能这样做的，所以这里运用的非常巧妙。
下面看看最核心的生成hashCode的hash方法：
[java] view plain copy final int hash(Object k) { int h = hashSeed; if (0 != h && k instanceof String) { return sun.misc.Hashing.stringHash32((String) k); } // 调用key的hashCode()方法得到hashCode h ^= k.hashCode(); // 对hashCode进行一系列的位移与异或运算并把结果作为hashCode返回 h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } 这里 为什么要进行这一系列的位移与异或运算 呢？主要是经过它这里的运算之后，能够使这个hashCode中的bit 0和1均匀分布，从而减少hash冲突，从而提高整个HashMap的效率。
扩容时的rehash：
[java] view plain copy 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]; // 对已经存在的元素进行重新hash放到新的hash桶中 transfer(newTable, initHashSeedAsNeeded(newCapacity)); table = newTable; // 更新扩容阙值 threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); } void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; for (Entry<K,V> e : table) { while(null != e) { Entry<K,V> next = e.next; if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } } } 由于hash表长度变化了，所以对于已经存在的元素，需要重新计算hashCode并放到新的hash桶中。这是一个比较耗时的操作，所以在创建HashMap时，如果对数据量有个预期值，那么，应该设置更合适的初始容量，以避免添加数据的过程中不断的扩容造成的性能损失。
下面再来看看get操作
[java] view plain copy public V get(Object key) { // null key进行特殊操作 if (key == null) return getForNullKey(); // 获取key对应的Entry Entry<K,V> entry = getEntry(key); // 如果存在则返回key对应的值，不存在则返回null return null == entry ? null : entry.getValue(); } final Entry<K,V> getEntry(Object key) { // size为0表示没有元素，所以直接返回null if (size == 0) { return null; } // 获取key的hashCode int hash = (key == null) ? 0 : hash(key); // 获取key对应的hash桶中的元素，并对链表进行迭代返回相应的value for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; // 根据hashCode和equalse（）方法来确定key if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } // 如果不存在，返回null return null; } 对于加载因子，默认为0.75，这是一个折衷的值， 我们可以通过构造方法来改变这个值，但是需要注意， 加载因子越大，查询数据的开销可能越大 。因为加载因子越大，意味着map中存放的元素越多，所以hash冲突的可能性越大，根据hashCode计算出的hash桶的位置相同，则保存为链表，而链表的查询操作会遍历整个链表，所以查询效率不高。而在get和put时都要查询元素，所以提高查询效率就提高了hashmap的效率。这是一种用空间换取时间的策略。
为什么HashMap很高效呢？HashMap通过以下几点保证了它的效率：
高效的hash算法，使其不易产生hash冲突基于数组存储，实现了元素的快速存取可通过加载因子，使用空间换取时间 转：http://blog.csdn.net/mhmyqn/article/details/48143465#
