HashMap是Java里基本的存储Key、Value的一个数据类型，了解它的内部实现，可以帮我们编写出更高效的Java代码。
本文主要分析JDK1.7中HashMap实现，JDK1.8中的HashMap已经和这个不一样了，后面会再总结。
正文 HashMap概述HashMap根据键的hashCode值获取存储位置，大多数情况下可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null，允许多条记录的值为null。HashMap非线程安全，即任一时刻可以有多个线程同时写HashMap，可能会导致数据的不一致。如果需要满足线程安全，可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力，或者使用ConcurrentHashMap。
HashMap的存储结构如下图所示：
HashMap根据键的hashCode值和HashMap里数组的大小取余，余数即为该Key存储的数组位置。
如：一个Key的hashCode为15，HashMap的Size为6，15 % 6 = 3，所以该Key存储在数组的第三个位置。
考虑另一种情况，如果一个Key的hashCode为21，那21 % 6 = 3，所以该Key也存储在数组的第三个位置，这样岂不是重复了？
所以对于在同一个位置的Key，HashMap把他们存储在一个单向链表里，新的Key永远在最前面。
如果这个数组里存储的太满，HashMap还有扩容机制。
下面我们分析HashMap的源代码，来看看数据是怎么存储的。
PUT
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
public V put(K key, V value) { //判断如果table为空，则初始化table if (table == EMPTY_TABLE) { inflateTable(threshold); } if (key == null) return putForNullKey(value); //计算key的hash值 int hash = hash(key); //根据key的hash值和table.length计算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; } } //修改的次数加一，用于迭代HashMap时，判断HashMap元素有没有修改 modCount++; //添加key addEntry(hash, key, value, i); return null; }
inflateTable — 初始化HashMap内部数组
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22
private void inflateTable(int toSize) { //根据toSize计算容量，即大于toSize的最小的2的n次方 int capacity = roundUpToPowerOf2(toSize); ……… } private static int roundUpToPowerOf2(int number) { // assert number >= 0 : "number must be non-negative"; return number >= MAXIMUM_CAPACITY ? MAXIMUM_CAPACITY : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1; } public static int highestOneBit(int i) { // HD, Figure 3-1 i |= (i >> 1); i |= (i >> 2); i |= (i >> 4); i |= (i >> 8); i |= (i >> 16); return i - (i >>> 1); }
关键方法Integer.highestOneBit((number - 1) << 1)，这个方法的结果就是求出大于给定数值的，最小的2的N次方。
解释之前先说明几个概念：