Map实现之HashMap（结构及原理）

??????? java.util包中的集合类包含 Java 中某些最常用的类。最常用的集合类是 List 和 Map。List 的具体实现包括 ArrayList 和 Vector，它们是可变大小的列表，比较适合构建、存储和操作任何类型对象元素列表。List 适用于按数值索引访问元素的情形。

??????? Map 则提供了一个更通用的元素存储方法。Map 集合类用于存储元素对（称作“键”和“值”），其中每个键映射到一个值。从概念上而言，您可以将 List 看作是具有数值键的 Map。而实际上，除了 List 和 Map 都在定义 java.util 中外，两者并没有直接的联系。

??????? Map接口的实现类有很多，其中HashMap就是比较重要的一个实现，本文就以HashMap为主重点介绍。

??????? HashMap是基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了非同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

??????? HashMap结合了ArrayList与LinkedList两个实现的优点，，虽然HashMap并不会向List的两种实现那样在某项操作上性能较高，但是在基本操作（get 和 put）上具有稳定的性能。

?

??????? 首先从成员变量开始一点点的来了解HashMap和上述几个概念。

?

??????? 1.HashMap的成员变量：

/**
 * 初始默认容量（必须为2的倍数）
 */
static final int DEFAULT_INITIAL_CAPACITY = 16;

/**
 * 最大容量,如果被指定为一个更高的值必须为2的倍数，并且小于1073741824.(1<<30)
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
 * 默认负载因子/负载系数
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
 * 内部实现表, 必要时调整大小，其长度亦为2的倍数
 */
transient Entry[] table;

/**
 * map中添加的元素个数
 */
transient int size;

/**
 * 扩容临界值，当size达到此值时进行扩容 (容量乘以负载因子).
 */
int threshold;

/**
 * 内部实现表的负载因子
 */
final float loadFactor;

/**
 * 操作数，可以理解为map实例被操作的次数，包括添加，删除等等
 */
transient volatile int modCount;

??????? HashMap其内部实现是一个Entry数组table，而Entry就是保存相应键值的实体。table数组默认大小为16，我们也可以在初始化时指定更大的值，但指定值必须为2的倍数。

??????? 通过对ArrayList的学习了解到ArrayList其内部实现也是数组，当被添加的元素超出数组的容纳极限时，ArrayList会对内部数组进行一次“扩容”，从而可以添加新的元素。

??????? 在HashMap中也有类似的概念，HashMap并不会像ArrayList一样直到数组都满了的情况下才去“扩容”，而是根据负载因子（load factor）来进行判断。

??????? 举例来说：HashMap实例中table数组的默认大小为16，负载因子为0.75，当添加元素个数大于等于12（16*0.75）时就会进行扩容。

??????? 所以说容量和负载因子直接影响着table数组是否扩容，什么时机扩容，进而影响这HashMap实例的性能。

?

??????? 2.Entry?元素

??????? 与LinkedList类似，HashMap也是采用Entry内部类来存储实际元素信息，以下是Entry的源代码（省略部分代码）：

static class Entry<K, V> implements Map.Entry<K, V> {
	final K key;
	V value;
	Entry<K, V> next;
	final int hash;
}

??????? Entry中包括4个成员变量，其中key为键，value为值，next指向下一个节点元素，hash为hash值。Entry通过next属性可以寻找到下一个节点的元素，进而通过遍历就可以找到相应key下存储的信息。

?

??????? 3.HashMap设置元素

??????? Map通过put方法来在Map实例中关联指定值与指定键。如果该实例已经包含了一个该键的映射关系，则旧值被替换。

??????? 示例如下：

Map map = new HashMap();
map.put("user1", "小明");
map.put("user2", "小强");
map.put("user3", "小红");
System.out.println("user1:" + map.get("user1"));
System.out.println("user2:" + map.get("user2"));
System.out.println("user3:" + map.get("user3"));
map.put("user2", "小龙");
System.out.println("user1:" + map.get("user1"));
//打印结果
user1:小明
user2:小强
user3:小红
user1:小明

??????? 首先，创建了一个HashMap的实例map，此时map实例中的table数组会默认初始化，创建一个长度为DEFAULT_INITIAL_CAPACITY=16的空数组。

??????? 然后，调用put方法将一对键、值（key,value）保存。当已存在Map实例中已存在指定key的映射时，会将新指定的value覆盖原value。

??????? 与LIst的相关实现add方法一样，HashMap的put方法是设置元素的入口，在put的过程中会进行一系列的判断与操作，所以只有将put方法理解透彻后HashMap的内部结构与机制才会更加清晰。

??????? HashMap进行put操作时按以下步骤执行：

??????? 1）判断key是否为空，如果为空则调用设置null的专有方法。

??????? 2）计算key的hash值。

??????? 3）通过hash与table数组的长度计算出该元素所要放置的数组下标。

??????? 4）遍历该下标下的Entry元素链，如果找到与指定key相同的Entry则直接替换该Entry的value值并返回。

??????? 5）如果未找到则添加一个新元素至该下标下的元素链前端。

??????? 以下是一张官网上对于put操作流程的描述图片，可以作为参考：

??????? 以下是put方法的源代码，其中我已经加入了相关描述便于大家理解：

/**
 * 设置指定值
 */
public V put(K key, V value) {
	//1.首先判断key是否为null
	if (key == null)
		//如果为null则调用putForNullKey方法
		return putForNullKey(value);
	//2.计算key的hash值
	int hash = hash(key.hashCode());
	//3.根据计算后的hash值与table数组长度计算该key应放置到table数组的那个下标位置
	int i = indexFor(hash, table.length);
	//4.遍历该下标下的所有Entry，如果key已存在则覆盖该key所在Entry的value值
	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;
		}
	}

	modCount++;
	//5.如果该key不存在则新添加Entry元素至数组指定位置，并且该Entry作为此下标元素链的头部
	addEntry(hash, key, value, i);
	return null;
}