概述
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
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内部数组
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次方。
解释之前先说明几个概念：
<< : 按二进制形式把所有的数字向左移动对应的位数，高位移出(舍弃)，低位的空位补零。在数字没有溢出的前提下，对于正数和负数，左移一位都相当于乘以2的1次方，左移n位就相当于乘以2的n次方；
>>: 按二进制形式把所有的数字向右移动对应位移位数，低位移出(舍弃)，高位的空位补符号位，即正数补零，负数补1。右移一位相当于除2，右移n位相当于除以2的n次方。
>>>: 无符号右移，忽略符号位，空位都以0补齐
我们拿数字10做示例，经过(number - 1) << 1 = 18,二进制表示为：10010
i |= (i >> 1) 即：10010 | 01001 = 11011
i |= (i >> 2) 即：11011 | 00110 = 11111
i |= (i >> 4) 即：11111 | 00001 = 11111
……
其实这几步就是把i的最高位1之后的所有位都变成1
然后 i – (i >>> 1) 即：11111-01111=10000(16)
这步是把最高位，之后的都变成0，这样就求出了最接近10的2的N次方（16）
至于为什么要不数组的Size设置为2的N次方，我们后面说。
hash — 计算Key的hash值
02
03
04
05
06
07
08
09
10
11
12
13
14
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
根据上面的注释，我们可以看出，HashMap中使用的hash值，不是Key直接的hashCode，而是经过一系列计算的。
计算hash值的作用就是避免hash碰撞，尽量减少单向链表的产生，因为链表中查找一个元素需要遍历。
indexFor — 计算Key所对应的数组位置
02
03
04
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);
}
第一次看到这个方法很是不理解，不是应该用 h % length吗？其实这里用了一个非常巧妙的方法来取这个余数。
在计算机中CPU做除法运算、取余运算耗费的CPU周期都比较长，一般几十个CPU周期，而位移运算、位运算只用一个CPU周期。
这样对于性能要求高的地方，就可以用位运算代替普通的除法、取余等运算，JDK源码中有很多这样的例子。
为了能够使用位运算求出这个余数，length必须是2的N次方，这也是我们上面初始化数组大小时要求的，然后使用 h & (length-1)，就可以求出余数。具体的算法推导，请自行搜索。
我们用个例子来说明下，如一个Key经过运算的hash为21，length为16：
直接取余运算：21 % 16 = 5
位运算：10101(21) & 01111(16-1) = 00101(5)
哇，这就是计算机运算的魅力，这就是算法的作用。
addEntry — 添加数据
02
03
04
05
06
07
08
09
10
void addEntry(int hash, K key, V value, int bucketIndex) {
//如果size大于等于threshold，且数组的这个位置不为null，则扩容数组
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);
}
threshold：HashMap实际可以存储的Key的个数，如果size大于threshold，说明HashMap已经太饱和了，非常容易发生hash碰撞，导致单向链表的产生。
在inflateTable方法中，我们可以看到
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
所以这个值是由HashMap的capacity 和负载因子（loadFactor默认：0.75）计算出来的。
loadFactor越小，相同的capacity就更频繁地扩容，这样的好处是HashMap会很大，产生hash碰撞的几率就更小，但需要的内存也更多，这就是所谓的空间换时间。
在这里也注意，扩容时会直接将原来容量乘以2，满足了length为2的N次方的条件。
createEntry就不多说了，就是将key、value保存到数组响应的位置。
GET
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
//用和添加时相同的算法求出hash值
int hash = (key == null) ? 0 : hash(key);
//直接从数组的响应位置拿到数据，判断hash相同、key相同，则返回
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
获取时非常简单，也非常迅速，添加时做的所有工作都是为快速获取做的工作。
总结
HashMap是一个非常高效的Key、Value数据结构，GET的时间复杂度为：O(1) ~ O(n)，我们在使用HashMap时需要注意以下几点：
1. 声明HashMap时最好使用带initialCapacity的构造函数，传入数据的最大size，可以避免内部数组resize；
2. 性能要求高的地方，可以将loadFactor设置的小于默认值0.75，使hash值更分散，用空间换取时间；
本文永久更新链接地址：http://www.xuebuyuan.com/Linux/2016-12/138329.htm
以上就上有关JDK1.7HashMap源码分析的相关介绍，要了解更多HashMap源码分析,HashMap,JDK1.7 HashMap 源码分析,编程,Linux编程,Linux Shell,Android,Android教程,JAVA,C语言,Python,HTML5内容请登录学步园。