首页 > 代码库 > HashMap源码分析 (JDK1.7)
HashMap源码分析 (JDK1.7)
看HashMap源码有一段时间了，但是一直没有写点什么，这几天趁着要换实习公司，没什么事做，就把自己对HashMap的理解写下来，边写边整理自己的思路。
这是借用别人画的理解HashMap的图，简单理解就是它结合了数组查找快和链表插入删除快的优势。
下面直接分析源码：
先从构造函数说起:
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: "
+ initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: "
+ loadFactor);
// 找到一个大于initialCapacity的且是2的幂的最小数
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
//因为loadFactor可以是大于1的数，这里防止threshold 超出最大容量
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
init();
}虽然另外还有几个重载的构造函数，但都是通过this关键字来调用这个构造方法。
所以其实HashMap中用来存储的数据结构就是一个Entry[],说白了就是个数组，那么我们来看看Entry这个类，这是一个静态内部类，注释都写了，有些没讲的源码就没贴上去，可以自己去看，比如equals()。下面把这个类的源码贴出来：
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;//保存的key，final关键字定义后一旦赋值就不能修改了，所以也没有setKey方法
V value;//保存的value
Entry<K,V> next;//指向下一个Entry的引用
int hash;//保存的hash值
Entry(int h, K k, V v, Entry<K,V> n) {
value = http://www.mamicode.com/v;next = n;key = k;hash = h;>在讲最常用的put()方法之前先科普下：Hash，一般翻译做"散列"，也有直接音译为"哈希"的，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。
Put()
//将特定的key与特定的value相关联，如果map中先存在一个key的映射，oldvalue将被替换
public V put(K key, V value) {
//如果key为null，则调用putForNullKey方法
if (key == null)
return putForNullKey(value);
//根据key计算出hash值
int hash = hash(key);
//根据hash值和数组大小，计算出数组下标
int i = indexFor(hash, table.length);
//注释1
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 = http://www.mamicode.com/e.value;>注释1：
根据下标索引到e，如果e不为空，则对key和e中的key进行hash值判断。怎么判断呢？
1.先判断hash值，如果hash值不相同，那肯定不是同一个对象(反之不成立)，没必要浪费时间了。
2.如果hash值相同，则进一步判断与e中的key是否为同一个，通过两种方式: “==”引用判断和.equals()值判断(可自己重写)，如果真的那么巧是同一个，就将old value返回并覆盖，并调用前面所说的recordAccess()方法。
找到位置i后，addEntry()实现加入一个Entry：
void addEntry(int hash, K key, V value, int bucketIndex) {
//如果entry数量大于阀值并且当前位置i已经存在元素，则调用resize()方法并传入一个两倍于当前数组大小的参数。
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
//创建一个新的Entry
createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}这个方法比较巧妙，创建一个Entry引用e指向原有Entry，然后将数组i位置的引用指向e（Entry的构造方法中这样实现的），使得新创建的Entry位于链表最前端，有点像栈的FIFO。最后将size++。
看一下其中的resize()方法：
void resize(int newCapacity) {
Entry[] oldTable = table;
//获得数组大小,如果大于最大容量，则将阀值设为Integer.MAX_VALUE，则以后不会再触发resize()操作，一了百了
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
//下面就看不懂了，1.6中没有rehash这个参数
boolean oldAltHashing = useAltHashing;
useAltHashing |= sun.misc.VM.isBooted() &&
(newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean rehash = oldAltHashing ^ useAltHashing;
//重点在这，在transfer()中可以看到，将table中所有的Entry转移到newTable中
transfer(newTable, rehash);
//改变table指向的数组，并重新设定阀值
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}重点看transfer()：
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
//根据数组中每个链表开头的Entry e,获得它的下一个next，如果key不为null(有的key确实为null),则更新hash值。根据新hash值计算在新数组中下标，然后指向那个位置。最后
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;
}
}
}最后三行代码比较需要花功夫理解，
第一行：e.next指向newTable[i]，不再指向所属链表中下一个元素，但next引用保存了改元素
第二行：newTable[i]指向e，newTable[i]本来是null,现在指向了e所属链表中头一个元素
第三行：e指向next，意味着e不再指向链表中头一个元素，而指向了它的下一个元素
如果看不懂那也正常，多看两遍一定能明白，我也看了好几遍。
举个例子就好比开枪射击，每执行一次while，table中某一条链表的头一个元素e好像一粒子弹，射向newTable相应位置，e指向了被射击的元素(e.next = newTable[i]),那里被射了一个坑，原有的位置被e取代(newTable[i] = e),然后用next补上了e的空缺(e = next)，像自动填装弹药一样。(想了很久才明白，这就是数据结构不好的后果)
还剩一个
private V putForNullKey(V value) {
//所有key为null的Entry保存在数组下标为0的链表上
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
//找到不为null的Entry e(这个判断有必要吗)
if (e.key == null) {
V oldValue = http://www.mamicode.com/e.value;>put()方法讲差不多了，其实与之对应的另一个常用方法get()也类似，大家有兴趣可以自己阅读。
我们来看看删除操作：
remove()
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}removeEntryForKey()返回一个要被移除的e,若e==null，则返回null，否则返回e中的value
final Entry<K,V> removeEntryForKey(Object key) {
//这两行在put()中都见过
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
while (e != null) {
Entry<K,V> next = e.next;
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
//如果删除头节点(table[i])
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
//对象引用向后移动，像C中指针向后移动
prev = e;
e = next;
}
return e;
}上面的操作就跟删除链表节点一样(我数据结构学得不好，看起来比较吃力)，不同点在于如果删除的是头节点(table[i])就有不同。
同样是删除的还有
public void clear() {
modCount++;
Entry[] tab = table;
for (int i = 0; i < tab.length; i++)
tab[i] = null;
size = 0;
}可见它是将每个指向链表头的引用table[i]都设为null,这样垃圾回收机制会在合适的时间把他们收集并释放空间。
HashMap源码分析 (JDK1.7)