大概是因为世界杯让我有借口去偷懒的原因吧，最近一段时间在公司也在做java的事情，所以没有太多的心思去写文章。万恶始于世界杯，也终于世界杯，以后就没有偷懒的借口了，心碎。。。
好吧，我来说说今天要讲的内容，源于一个大学的大神，突然来问我一个很简单的算法，然后就引起了自己的一些思考，下面我们来看看这个算法：
image
很简单，我们创建了两个Set，都知道Set是保存不重复的属性，然后第一个创建了100000个10000之内的随机数，第二个Set创建了190002个1999-11999之间的随机数。
看上去很拗口，但是问题很简单。就是算出两个Set里面相同的数总共多少个。
拿到问题了大家估计都会想，哇，这个问题很简单，两个for循环就完事了：
Random random = new Random();
int z = 0;
Set<Integer> list1 = new HashSet<>();
for (int i = 0; i < 100000; i++) {
list1.add(random.nextInt(10000));
}
Set<Integer> list2 = new HashSet<>();
for (int i = 9998; i < 200000; i++) {
list2.add(random.nextInt(10000) + 1999);
}
for (int str : list1) {
for(int str1 : list2){
if(str == str1){
z++;
}
}
}
System.out.println(z);
看上去很简单，好吧，我们用Junit试试运行的结果：
image
625ms看上去也没什么问题，但是，我的同学看到就开始调侃我了，你怎么那么菜，#￥%￥&……%#￥%￥……￥%……%￥%%￥%，此处省略1000字被调侃的话。然后他就给我看了他的运行结果：
image
我看到之后，有点惊呆了的意思，27ms跟625ms差了二十多倍的速度。这个时候不是我惊讶的时候，我知道，我要做的是去跪舔。。。去试探点口风。想不到这位同学竟然告诉我这是我每天都会用的东西，就能达到这个效果-----HashMap
那我赶紧去试试，确实：
Random random = new Random();
int z = 0;
Set<Integer> list1 = new HashSet<>();
for (int i = 0; i < 100000; i++) {
list1.add(random.nextInt(10000));
}
Set<Integer> list2 = new HashSet<>();
for (int i = 9998; i < 200000; i++) {
list2.add(random.nextInt(10000) + 1999);
}
HashMap<Integer,Integer> hashMap=new HashMap();
for (int str : list1) {
hashMap.put(str,str);
}
for(int str : list2){
if(hashMap.get(str) != null){
z++;
}
}
System.out.println(z);
很神奇的是，直接用Hashmap直接就能得到这样一个结果。然后我亲爱的同学又来一顿调侃，hashmap的原理都不懂你就！￥%￥……%￥@%#@%￥%@%￥。然后我就只好认怂的看一下总结了一下hashmap的原理。
关于hashmap，我们首先得说说哈希表的基本概念，我还去翻了一下自己的大学课本，以下是官方的回答：
哈希表的基本概念
哈希表又称散列表，是除了顺序表存储结构、链表存储结构和索引表存储结构之外的又一种存储线性表的存储结构。哈希表存储的基本思路是：设要存储的对象个数为n，设置一个长度为m（m>=n）的连续空间以线性表中每个对象的关键字K下标i（0<=i<=n-1）为自变量，通过一个称为哈希函数的函数h(K下标i)，把K下标i映射为内存单元的地址h(K下标i)，并把该对象存储在这个内存单元中。h(K下标i)也称为哈希地址（又称为散列地址）。把如此构造的线性表存储结构称为哈希表。
那下面我用一幅图概括上面的一大堆文字：
image
这就很简单明了了吧~
看懂了哈希表的基本概念，那下面我们就要讲讲用它的概念做出来的伟大作品HashMap了：
HashMap是什么：
HashMap是Java常用的用来储存键值对的数据结构，它是线程不安全的，可以储存null键值。
HashMap实现原理：
其实HashMap主干是一个数组叫Note：
transient Node<K,V>[] table;
而Node是HashMap里面的一个静态类：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;//对key的hashcode值进行hash运算后得到的值，存储在Note，避免重复计算
final K key;
V value;
Node<K,V> next;//存储指向下一个Entry的引用，单链表结构
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
...
}
看到上面代码Node里面的next，是一个单链表结构，而结合table是一个Node数组，可以判断出HashMap是一个数组加链表的结构。下面我总结一下HashMap的结构图：
image
好吧，我们每天都用的HashMap大概就是上图数组+链表的结构。那突然我想到个问题，为什么HashMap偏偏采用的是数组+链表的结构呢？
哈希冲突
答案其实很简单，那就是哈希冲突，因为上面说到哈希函数h(K)，里面是一个算法，当两个不同的元素，通过哈希函数的算法算出的实际存储地址是相同的时候，就会出现冲突，这个冲突就称为哈希冲突。所以，当实际存储地址相同（可以看做HashMap存储的数组）的时候，就需要链表来存储拥有相同实际地址但几个不同的元素。这种称为链地址法，也就是数组+链表的方式，可以很好的解决哈希冲突。
除此之外，我们也可以明白为什么HashMap效率能这么高了，对于查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度为O(n)，首先遍历链表，存在即覆盖，否则新增；对于查找操作来讲，仍需遍历链表，然后通过key对象的equals方法逐一比对查找。当然，HashMap中的链表出现越少，也就是哈希冲突出现越少的话，性能才会越好。
源码剖析
下面我们继续分析HashMap的源码：
//存储的key-value键值对的个数
transient int size;
//负载因子，代表了table的填充度有多少，默认是0.75
final float loadFactor;
//阈值，当table == {}时，该值为初始容量（初始容量默认为16）；当table被填充了，也就是为table分配内存空间后，threshold一般为 capacity*loadFactory。
int threshold;
HashMap的容量是否需要扩充，看的就是threshold，capacity和loadFactory这三个值。举个例子，如果初识容量是16（即capacity为16，且loadFactory为0.75）的时候：
threshold = capacity * loadFactory
= 12
也就是说当前HashMap的容量阀值为12，当我们实际的容量超过12的时候，HashMap会进行扩容，从16会变成下个2的n次幂，也即32.
下面我们来分析下几个方法：
put
public V put(K key, V value) {
//(1)
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//(2)判断table是否为空，是就执行resize()方法
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//如果在数组里面没找到相应的位置则需要新建一个位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//否则，在数组里面找到位置若找到相同值，则覆盖；若是不同的值
//则需要在链表上新建一个结点。
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
代码很长，但我们主需要捉住关键代码分析即可
注意点（1）：首先我们看看hash()方法做了什么事：
//通过这个方法来获取元素要存储的位置
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
下面我们看看注意点（2）：resize()方法做了什么：
//HashMap可设置的最大容量为2的30次幂
static final int MAXIMUM_CAPACITY = 1 << 30;
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
//当容量大于等于可设置的最大容量时，取原来的值
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//当原来的容量大于等于原来默认容量值时，容量翻倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using
...
}
return newTab;
}
我们可以看到resize()就是一个对容量进行计算扩充的方法。
每次当原来的值不够用的时候，容量就会翻倍。
有人会问，为什么扩充的容量一定是要2的n次幂呢？
下面我就讲讲这个运算，大家是否还记得putVal()方法中有这么一段
(n - 1) & hash，是一个与运算。
关于这个运算，其实就是确定得到最终数组索引位置。
我们用同样的二进制数去做分别跟31，和另一个2的n次幂数做运算
（1）
1 0 1 0 1
&
1 1 1 1 0 = 1 0 1 0 0
（2）
1 0 1 0 0
&
1 1 1 1 0 = 1 0 1 0 0
（3）
1 0 1 0 1
&
1 1 1 1 1 = 1 0 1 0 1
结果很明显，分别从（1）（2）（3）看出，当与运算为2的n次幂做与运算时，得到的结果会变得更多。得到的结果更多意味着最终数组索引位置变化也会更多，最后得到的哈希冲突就会变少。所以这里大家就明白为什么扩容的大小一定要是2的n次幂了吧
还有一个问题，有人会问为什么用与运算可以确定得到最终数组索引位置呢？好吧，我再来举个例子，我们用一个很大的数和很小的数分别跟2的5次幂做与运算：
比32要大的数：
1 1 1 1 1 1 1 1 1
&
0 0 0 0 1 1 1 1 1 = 1 1 1 1 1
比32要小的数：
0 0 0 0 0 0 0 1 1
&
0 0 0 0 1 1 1 1 1 = 0 0 0 1 1
上面的结果就看到，无论多大或者多小的数跟32做与运算，得出的结果都是小于等于32的，那由此大家就知道当我们的HashMap长度为32的时候，无论hash()方法算出来的数是多少，跟长度做与运算，最后得出的最终位置肯定比HashMap的长度范围内。
get
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//如果数组的第一个值相同，则返回
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//若数组的第一个值没找到，则需要向该数组里的链表逐个结点查找
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
我们从get方法就能看到，如果查询的时候，能第一次查出值，效率是很高的，但是如果有哈希冲突，需要往链表下面查，效率就会变慢。
好了，HashMap的原理大概就是这样了，对于HashMap的原理面试的时候应该也没被少问，所以自己也参考网上的资料，总结了自己的一些自己的看法。其实大神还告诉我，这是一种代码中空间换时间的做法，我们多创建了一个HashMap的空间，却时间少花了二十多倍的运算时间，何乐而不为？代码中或许还有很多很好的例子等着我们去发掘。
很久没写文章，如果有写错的地方，请多多指正，谢谢大家！
我的掘金：
https://juejin.im/user/594e8e9a5188250d7b4cd875/posts
我的简书：
https://www.jianshu.com/u/b538ca57f640
网友评论