HashMap原理详解及常用API介绍

如果你准备面试Java后端方向的工程师，那么HashMap可以说是面试中的重中之重，你去10家公司面试，可能8家公司都会会问道。所以可见HashMap相关的知识点对于我们面试来说有多么重要，接下来就让我们走进HashMap的大门吧！

1.什么是HashMap

HashMap是Java当中一种数据结构，是一个用于存储Key-Value键值对的集合，每一个键值对也叫作Entry实体。
HashMap 数据结构为 数组+链表，其中：链表的节点存储的是一个 Entry 对象，每个Entry 对象存储四个属性（hash，key，value，next）。

2.HashMap存储原理

首先，初始化 HashMap，提供了有参构造和无参构造,具体的关于HashMap的构造函数如下所示，无参构造中，容器默认的数组大小 initialCapacity 为 16，且数组大小只允许为2的整数次幂，默认加载因子loadFactor 为0.75。容器的阈值为 initialCapacity * loadFactor，默认情况下阈值为 16 * 0.75 = 12。当存储在HashMap集合中的Entry数目大于容器的阈值，则容器需要扩容，使其容量变为原来的两倍。

HashMap();//构造一个具有默认 初始容量 (16)  和 默认加载因子 (0.75) 的空 HashMap。
HashMap(int initialCapacity);//构造一个带 指定初始容量 和 默认加载因子 (0.75) 的空 HashMap。
HashMap(int initialCapacity, float loadFactor);//构造一个带指定初始容量和加载因子的空 HashMap。
1
2
3

接下来，我们对HashMap的put方法进行探索！
第一步：通过 HashMap 自己提供的hash 算法算出当前 key 对应的hash 值；

int hash=key.hashCode();
1

第二步：通过计算出的hash 值去调用 indexFor 方法计算当前对象应该存储在数组的几号位置;

static int indexFor(int hash, int length) { 
       // hash 为key 的 hash值；length 是数组长度
       return hash & (length-1);  
}
1
2
3
4

第三步：判断size 是否已经达到了当前阈值，如果没有，继续；如果已经达到阈值，则先进行数组扩容，将数组长度扩容为原来的2倍。
请注意：size 是当前容器中已有 Entry 的数量，不是全部Entry所占数组空间的大小。
第四步：将当前对应的 hash，key，value封装成一个 Entry，去数组中查找当前位置有没有元素，如果没有，放在这个位置上；如果此位置上已经存在链表，那么遍历链表，如果链表上某个节点的 key 与当前key 进行 equals 比较后结果为 true，则把原来节点上的value 返回，将当前新的 value替换掉原来的value，如果遍历完链表，没有找到key 与当前 key equals为 true的，就把刚才封装的新的 Entry插入到对应链表的尾部，即当前链表的最后一个元素。（注意：在JDK1.8之前，是插入到链表的头部，即采用的是头插法）
OK！到目前为止，我们已经将当前的 key-value 存储到了容器中。
在put方法的实现原理中，就出现了一个经典的面试题！
即：为什么 HashMap使用这种方式（hash & (length-1)）计算在数组中位置呢？
在数据结构中，简单的Hash函数只需要取模就可以了。而HashMap用&运算主要是提升计算性能。那么这又会带来一个新的问题，为什么&运算要与length-1呢？回看HashMap初始化容量大小的时候，数组长度length必须是2的整数次幂（如果手动传参为n,HashMap会自动转换长度为距离n最近的2的整数次幂）。只有这样，hash&（length-1）的值才会和hash%length计算的结果保持一致。这就是它的原因所在。采用这种方式，即提升了CPU计算性能，也保证了数据在Hash表中的均匀分布。
读者如果不理解其中的原理，可以自行编写代码测试一下：

public static void main(String[] args) {
	int	length  = 16; //定义数组长度为2的整次幂，2^4
	//定义key，并计算k的hash值
	String k = "China";
	int hash = k.hashCode();
	//分别使用两种方式计算在数组中的位置
	int index1 = hash % length;
	int index2 = hash & (length - 1);
	//验证结果
	System.out.println(index1 == index2);
	//结果为 true
}
1
2
3
4
5
6
7
8
9
10
11
12

于此同时，这里还可以引申出另外一个问题？
即：为什么hashmap的容量是2的幂次方？
1.计算机内&运算速度较快，至少比%速度要快；
2.当length为2的整数次幂时，会满足一个公式:(length-1)&hash=hash%length;
3.采用(n-1)&hash来计算索引位置时，当n为2的幂次方的时候，n-1转换为二进制时可以保证低位全都是1，所以元素存储在哈希表中的位置完全取决于其hash值，而Java中的hashCode()方法能够满足元素的均匀分布，因此就会导致元素索引分布均匀。

3.HashMap和HashTable 的异同

4.HashMap采用的API

package a;
import java.util.HashMap;

import java.util.Map.Entry;
public class Main{
    public static void main(String[] args){
    	HashMap<String,Integer> mp = new HashMap<String,Integer>();
    	mp.put("one",1);	//存放键值对
    	System.out.println(mp.get("one"));	//通过键取值，输出 1
    	System.out.println(mp.get("1"));	//通过键取值，不存在，输出 null
    	System.out.println("====================");
    	
    	System.out.println(mp.containsKey("one"));	//HashMap中是否包含该键，输出true
    	System.out.println(mp.containsKey("two"));	//不包含该键，输出false
    	System.out.println("====================");
    	
    	System.out.println(mp.containsValue(1));	//HashMap中是否包含该值，输出true
    	System.out.println(mp.containsValue(2));	//不包含该值，输出false
    	System.out.println("====================");
    	
    	System.out.println(mp.isEmpty());	//判断是否为空，输出false
    	System.out.println(mp.size()); 		//输出 HasMap 的长度，1
    	System.out.println("====================");
    	
    	mp.remove("one");	//从HashMap中删除该键，值也会被删除
    	System.out.println(mp.get("one"));	//输出null
    	System.out.println(mp.containsKey("one"));	//输出false
    	System.out.println(mp.containsValue(1));	//输出false
    	//也可以通过 mp.remove("one",1); 把键和值一起删掉
    	System.out.println("====================");
    	//重新添加键值对
    	mp.put("one", 1);
    	mp.put("two", 2);
    	mp.put("three", 3);
    	System.out.println(mp.values());//输出所有值，[1, 2, 3]
    	System.out.println(mp.keySet());//输出所有键，[one, two, three]
    	System.out.println(mp.entrySet());//输出所有键和值，[one=1, two=2, three=3]，中括号
    	System.out.println("====================");
    	
    	HashMap<String,Integer> mp2 = new HashMap<String,Integer>();
    	mp2.put("four", 4);
    	mp.putAll(mp2);	//添加同类型另一个HashMap，放进头部
    	System.out.println(mp);	//输出整个HashMap的键和值，{four=4, one=1, two=2, three=3}，大括号
    	System.out.println("====================");
    	
    	mp.replace("one", 5);	//替换键的值，java8才有
    	mp.replace("two", 2 , 6);	//替换键的旧值为新值
    	System.out.println(mp);	//输出{four=4, one=5, two=6, three=3}
    	System.out.println("====================");
    	
    	Object mp3 = mp.clone();	//克隆一个，顺序随机
    	System.out.println(mp3);	//输出{two=6, three=3, four=4, one=5}
    	System.out.println("====================");
    	
    	for(String key:mp.keySet())	//遍历整个HashMap的键
    		System.out.print(key+' ');//输出four one two three 
    	System.out.println();
    	for(Integer values:mp.values())	//遍历整个HashMap的值
    		System.out.print(values+' ');//输出36373835，并不是4 5 6 3 ，说明该方法不能输出值
    	for(Entry<String,Integer> entry:mp.entrySet()) {	//遍历整个HashMap，输出键值
    		String key = entry.getKey();
    		Integer value = entry.getValue();
    		System.out.print(key+'='+value+' ');	//输出four=4 one=5 two=6 three=3 
    	}
    	System.out.println("====================");
    	mp.clear();	//清空数组
    	System.out.println(mp); 	//输出{}
    	System.out.println("====================");
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71