Java容器类浅析二-----HashMap的存取原理

上一节我们说到HashMap底层的数据结构是顺序表+链表的“拉链式数组”(该数组的元素是每个链表的头结点)，且数据存储是无序的(不按照我们插入的顺序进行存储))，下面我们来分析一下HashMap的源码(JDK1.7)，深入了解其实现原理。

一、继承与实现

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

HashMap继承了AbstractMap抽象类，实现了Map接口，同时实现了 Cloneable和Serializable这两个声明性接口，表示HashMap的对象可以被克隆和序列化。

二、成员变量

`static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16“`
默认的初始化容积(桶的个数)，该值必须是2的N次方
static final int MAXIMUM_CAPACITY = 1 << 30;
桶的最大个数为2的30次方，第32位为符号位
static final float DEFAULT_LOAD_FACTOR = 0.75f;
默认的加载因子，阈值threshold=CAPACITYLOAD_FACTOR，当size(即map中的元素个数)>=threshold时，桶的个数要翻倍。
static final Entry<?,?>[] EMPTY_TABLE = {};
静态的空数组，为初始化table做准备。
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
table是map里存放key-value键值对的桶的数组，transient关键字表示对象在序列化时忽略掉该字段。
transient int size;
size是对key-value键值对的对象entry的计数，而非桶。
int threshold;
size的阈值
final float loadFactor;
加载因子
transient int modCount;
HashMap非线程安全的，因此如果在使用迭代器的过程中有其他线程修改了map，那么将抛出ConcurrentModificationException，这就是所谓fail-fast策略。具体实现，在后面说明。

10.static class Entry<K,V> implements Map.Entry<K,V> 静态内部类Entry

Entry类是HashMap中的基本存储单位，可以认为是Node节点，Entry中有key,value,key的hash值，和下一个Entry对象的引用next这四个元素。可以看到Entry类中的所有实现方法都是final的，即表明该方法不可被重写。

三、构造函数

public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

默认构造函数，会使用Default的值来初始化变量。


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);

this.loadFactor = loadFactor;
      threshold = initialCapacity;
      init();//钩子函数
  }

桶的个数最大为2^30；使用默认构造函数初始化时，loadFactory=0.75f,threshold=16；在第一次调用put方法时才会对capacity进行初始化，并更改threshold的值。

四、put()函数分析

HashMap的put()方法：
首先计算key的hashCode（具体的Hash实现我还没看懂），然后根据得到的hashCode计算出所在的数组索引（hashCode），然后检查该索引的链表中是否存在相同的key值，如果有则替换掉value；最后插入到该索引位置的链表的头部(HashMap的链表每次插入到头结点位置)。

public V put(K key, V value) {
if (table == EMPTY_TABLE) {
        inflateTable(threshold);//在第一次调用put方法时，才会对成员变量table、capacity、hashSeed进行初始化，并给threshold重新赋值
    }
if (key == null)
return putForNullKey(value); //key=null的元素都存放在table[0]的位置
int hash = hash(key);            //计算hashCode
int i = indexFor(hash, table.length); //hashCode % table.length 作为该key在table[]中的索引
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))) {//如果该链表中的某个元素的key值相同（hashCode相同且key值相同），则替换掉Value，并返回
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
return oldValue;
        }
    }
/*Fail-Fast策略：在迭代过程中，判断modCount跟expectedModCount是否相等，如果不相等就表示已经有其他线程修改了Map：
注意到modCount声明为volatile，保证线程之间修改的可见性。（volatile之所以线程安全是因为被volatile修饰的变量不保存缓存，
直接在内存中修改，因此能够保证线程之间修改的可见性）。*/
    modCount++;
    addEntry(hash, key, value, i);//addEntry方法较复杂，下面详细分析
return null;//可以根据put方法的返回值来判断，HashMap中是否有相同的key值。
}

初始化HashMap存储结构的方法：

private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize);//开始时，toSize=threshold=16，故capacity=16

    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);//threshold=min(16*3/4,16)=12
    table = new Entry[capacity];//一开始，table的容量(即桶的个数)为16
    initHashSeedAsNeeded(capacity);//初始化hash方法的seed
}

为什么说当key=null时，该元素会存储在table[0]的位置，看此方法：

private V putForNullKey(V value) {
//遍历table[0]的头结点所在的链表，替换key=null的元素的value，由此可见key=null的元素在HashMap中只有一个，且在table[0]的链表中
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;
        }
    }
    modCount++;
    addEntry(0, null, value, 0);
return null;
}

计算hashCode的索引值，indexFor(hash, table.length)：

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);
}

因为length是2的次方的值，所以实际上h&(length-1)相当于h%(length-1)，为什么要用&，而非%呢，因为&的速度快于%。

计算出index之后，并非万事大吉了，还有考虑大当前元素个数是否达到了阈值，如果达到了阈值，如何进行扩容等。

void addEntry(int hash, K key, V value, int bucketIndex) {
//如果此时HashMap中的元素个数size达到了阈值，而且当前索引的桶中有元素的话，就需要将桶的个数翻倍，以减少散列的碰撞几率。
if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;//扩容之后，hashSeed发生了变化，所以要重新计算hashCode
        bucketIndex = indexFor(hash, table.length);//对新的hashCode重新计算索引
    }

    createEntry(hash, key, value, bucketIndex);//将键值对对象Entry，插入索引指定的链表的头部。
}

从下面的代码中可以看出，桶的个数最大为2^30，阈值的最大值为2^31-1，size最大值也为2^31-1（size的限制体现在其数据类型为int上）。在JDK8中，HashMap的实现方法大改，当有某个链表中的元素个数超过6个时，就将存储结构由“拉链数组”修改为“红黑树”，用来提高插入和查找的效率

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];
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

五、get（）方法分析

其实了解了put方法之后，get方法就很好理解了。
计算key的hashCode，根据hashCode计算索引index，得到table[index]的entry，遍历该头结点对应的链表，拿到key相等的entry，返回entry.value。


public V get(Object key) {
if (key == null)
return getForNullKey();
    Entry<K,V> entry = getEntry(key);

return null == entry ? null : entry.getValue();
}

final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
    }

int hash = (key == null) ? 0 : 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是最常用的数据结构之一，用来存储键值对模型非常方便。它通过一个内置的hash方法对要存储的对象的key进行散列，散列到一个顺序表中(Entry的数组)。遇到冲突时，HashMap有两种解决方案，1.在数组元素下面拉出来一个链表，存放具有相同hashCode的对象；2.将容积扩大，减少冲突发生的几率。

因为HashMap同时具有顺序表和链表的特性，所以其既方便查找，又方便插入和删除。
同时，由于插入的数据的位置是由散列函数来确定的，所以元素的位置和插入顺序没有关系。
那么问题来了，当我们从数据库中读取数据存储在Map中而且要求保证数据读取的顺序时，该怎么办呢？
请看Java容器类浅析三—–保证顺序的HashMap–LinkedHashMap的存取原理

秒客网