HashMap的深刻理解
几乎每个Java程序员都知道HashMap，都知道哪里要用HashMap，
知道Hashtable和HashMap之间的区别，
那好，我们以面试题的方式来谈一谈HasnMap!
先来些简单的问题
“你用过HashMap吗？” “什么是HashMap？”
HashMap实现了Map接口，Map接口对键值对进行映射。 Map中不允许重复的键 。
Map接口有两个基本的实现，HashMap和TreeMap。
TreeMap保存了对象的排列次序，而HashMap则不能。
HashMap允许键和值为null。 HashMap是非synchronized的;
简单的说HashMap的存储结构是由 数组和链表 共同完成的
HashMap是Y轴方向是数组，X轴方向就是链表的存储方式
“你知道HashMap的工作原理吗？” “你知道HashMap的get()方法的工作原理吗？”
HashMap是基于hashing的原理，我们使用put(key, value)存储对象到HashMap中，
使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时，
我们先 将 Key 做 Hash 算法，取得 Key 所对应的数据用于找到bucket位置来储存Entry对象。
然后再调用equals方法，来判断他们是不是内容相同，是做覆盖处理还是链表操作；
“当两个对象的hashcode相同怎么储存？”
因为hashcode相同，所以它们的bucket位置相同，‘碰撞’会发生。
因为HashMap使用链表存储对象，
这个Entry(包含有键值对的Map.Entry对象)会存储在链表中。
后面还可以说
String, Interger这样的wrapper类作为HashMap的键是再适合不过了，
而且String最为常用。
因为String是不可变的，也是final的，而且已经重写了equals()和hashCode()方法了
“如果两个键的hashcode相同，你如何获取值对象？”
当我们调用get()方法，HashMap会使用键对象的hashcode找到bucket位置，
找到bucket位置之后，会调用keys.equals()方法去找到链表中正确的节点，
最终找到要找的值对象。
“如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？”
默认的负载因子大小为0.75，也就是说，当一个map填满了75%的bucket时候，
和其它集合类(如ArrayList等)一样，将会创建原来HashMap大小的两倍的bucket数组，
来重新调整map的大小，并将原来的对象放入新的bucket数组中。
这个过程叫作rehashing，因为它调用hash方法找到新的bucket位置。
“你了解重新调整HashMap大小存在什么问题吗？”
当重新调整HashMap大小的时候，存在条件竞争，
因为如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。
在调整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的bucket位置的时候，
HashMap并不会将元素放在链表的尾部，而是放在头部，这是为了避免尾部遍历(tail traversing)。
如果条件竞争发生了，那么就死循环了。
这个时候，你可以质问面试官，为什么这么奇怪，要在多线程的环境下使用HashMap呢？：）
好下面我们简单看看hashMap的源代码吧（jdk1.7）
1 -HashMap的定义
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
{可以看出HashMap集成了AbstractMap抽象类，实现了Map，Cloneable，Serializable接口，
AbstractMap抽象类继承了Map提供了一些基本的实现。
2.底层存储
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable{
// 默认初始容量为16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 最大容量为2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认加载因子为0.75f
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final Entry<?,?>[] EMPTY_TABLE = {};
// 空Entry[]
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
// 已存储元素的数量
transient int size;
// 扩容临界值
int threshold;
// 加载因子
final float loadFactor;可以看出来， 默认初始容量为16， 最大容量为2的30次方，
默认加载因子为0.75f， table是一个空Entry数组
-下面我们来看一下， Entry数组结构
static class Entry<K,V> implements Map.Entry<K,V> {
//key(键)
final K key;
//value(值)
V value;
//指向下一个Entry对象(单向链表)
Entry<K,V> next;
//hash(哈希值)
int hash;
//初始话Entry[]
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}图表的形式
数组 链表的根节点 下一个节点（next）
4.构造方法
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
我们可以看到，调用双参构造器 传入初始容量16，和加载因子0.75
/**
* 构造一个指定初始容量和加载因子的HashMap
*/
public HashMap( int initialCapacity, float loadFactor) {
//【1】 初始容量和加载因子合法校验
if (initialCapacity < 0)
throw new IllegalArgumentException( "Illegal initial capacity: " +
initialCapacity);
//【2】
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException( "Illegal load factor: " +
loadFactor);
//【3】 赋值加载因子
this.loadFactor = loadFactor;
// 赋值扩容临界值
threshold = initialCapacity;
init();
} 【1】 ，首先是判断传入的容量是不是小于0，what? 不是说好传入的是默认容量16吗？
为什么有这个判断？这样判断是不是傻！
no！no！no！
我们退一步，如果我们初始化HashMap调用的不是无参的构造器，而是单参构造器呢
（这货可不是一个构造器）
其实初始化HashMap时，我们可以定义Map的容量
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
} 【2】 ，接下来判断的是定义Map的容量是否超过 1 <<30，这是一个好大的数，不做计算，
有兴趣的小伙伴可以拿出一张纸和一根笔计算一下，
【3】 ，我们可以看到把加载因子 和容量 复制给了属性loadfactor,和threshold，
我们先记住这两个属性
然后没然后了，是的，只是初始化了属性！
5.增加
public V put(K key, V value) {
//【1】 如果key为null，调用putForNullKey方法进行存储
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
//【2】 如果key为null，调用putForNullKey方法进行存储
if (key == null)
return putForNullKey(value);
//【3】 计算key对应的hash值
int hash = hash(key);
// 通过key的hash值查找在数组中的index位置
int i = indexFor(hash, table.length);
//【4】 取出数组index位置的链表，遍历链表找查看是有已经存在相同的key
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
// 通过对比hash值、key判断是否已经存在相同的key
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
// 如果存在，取出当前key对应的value，供返回
V oldValue = e.value;
// 用新value替换之旧的value
e.value = value;
e.recordAccess(this);
// 返回旧value，退出方法
return oldValue;
}
}
// 如果不存在相同的key
// 修改版本+1
modCount++;
//【5】 在数组i位置处添加一个新的链表节点
addEntry(hash, key, value, i);
// 没有相同key的情况，返回null
return null;
}【1】 -首先判断属性table是不是为空，第一次肯定是空（上面的属性已经说了），然后就是初始化Entry数组了
private void inflateTable(int toSize) {
//对容量进行取值，只能是2的倍数，比如如果传入的threshold是15，那么这里取值为16
int capacity = roundUpToPowerOf2(toSize);
// 扩容临界值
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY +1;
//为table赋值了，就是初始化HashMap了（Entry对象数据加单向链表）
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}为什么一定要是2的倍数，我们下面说
接着，就是加载因子的作用了，首先是容量乘以加载因子，这里我们传入的容量是16，乘以加载因子，那么就是12了对吧！，
然后就是在12和1<<30值中取最小值，
所以threshold的值不再是16，而变成了16的0.75倍了！ 好这里分析为什么容量的大小一定要是2的倍数，
如果容量是15.那15的0.75倍是多少？请自行脑补！
【2】 -这里就是hashMap和HashTable的区别之一，hashMap键可以为空值；
【3】 -这个是通过哈希算法得到键的哈希值（有兴趣的小伙伴可以研究一下hash算法）；
接着就是拿得到的哈希值 和容量的大小做与运算（这样得到的值才在容量的大小的范围内），
确定放在Entry数组的哪个位置
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);
}【4】 -遍历当前Entry[],
判断这个键是否在Entry[] 中已经存在，我们可以看到，首先判断的是键的hash值，
讲道理，对于这种算法，我并不知道，键不一样，hash是否可以一样！
我只能拿jdk的hashCode来参考一下！按照jdk的String的hashCode，
即使是不同的字符串也有可能他们的hashCode也相同；下面我们一起来看一下源码
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}其实上面的实现也就是数学表达式的实现：
- s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
s[i]是string的第i个字符，n是String的长度。
举个简单的例子把
- String str = "java";
-
- h = 0
- value.length = 4
-
- val[0] = j
- val[1] = a
- val[2] = v
- val[3] = a
-
- h = 31*0 + j
- = j
-
- h = 31 * (31*0 + j) + a
- = 31 * j + a
-
- h = 31 * (31 * (31*0 + j) + a) + v
- = 31 * (31 * j + a) + v
- = 31 * 31 * j + 31 * a + v
-
- h = 31 * (31 * 31 * j + 31 * a + v) + a
- = 31 * 31 * 31 * a + 31 * 31 * a + 31 * v + a
-
- h = 31 ^ (n-1) * val[0] + 31 ^ (n-2) * val[1] + 31 ^ (n-3) * val[2] + ...+ val[n-1]我们会注意那个狗血的31这个系数为什么总是在里面乘来乘去？为什么不适用32或者其他数字？
大家都知道，计算机的乘法涉及到移位计算。当一个数乘以2时，就直接拿该数左移一位即可！
选择31原因是因为31是一个素数！
所谓素数：
质数又称素数。指在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。
在存储数据计算hash地址的时候，我们希望尽量减少有同样的hash地址，所谓“冲突”。
如果使用相同hash地址的数据过多，那么这些数据所组成的hash链就更长，从而降低了查询效率！
所以在选择系数的时候要选择尽量长(31 = 11111[2])的系数并且让乘法尽量不要溢出
(如果选择大于11111的数，很容易溢出)的系数，因为如果计算出来的hash地址越大，所谓的“冲突”就越少，查找起来效率也会提高。
31可以 由i*31== (i<<5)-1来表示，现在很多虚拟机里面都有做相关优化，
使用31的原因可能是为了更好的分配hash地址，并且31只占用5bits！
在java乘法中如果数字相乘过大会导致溢出的问题，从而导致数据的丢失.
而31则是素数（质数）而且不是很长的数字，最终它被选择为相乘的系数的原因不过与此！
得出的结论是
equals()相等的两个对象，hashcode()一定相等；
equals()方法不相等的两个对象，hashcode()有可能相等。
好好好，现在我们回到判断上，后面判断这个键是否是一块内存地址，再判断值是否内容是相同的
既然上面谈了那么多的hashCode废话，那么我们再谈谈String的equals的废话吧！上源码
public boolean equals(Object anObject) {
if (this == anObject) {
return true;
}
if (anObject instanceof String) {
String anotherString = (String) anObject;
int n = value.length;
if (n == anotherString.value.length) {
char v1[] = value;
char v2[] = anotherString.value;
int i = 0;
while (n-- != 0) {
if (v1[i] != v2[i])
return false;
i++;
}
return true;
}
}
return false;
}把字符传拆成字符数组，然后一个一个比较是否相等！
第【5】步
往Entry[]添加数据了
void addEntry(int hash, K key, V value, int bucketIndex) {
//【5.1】判断当前添加的数量已经超过的threshold(这个值是容量乘以0.75哦)
// 如果超过，马上给Entry[]扩容成现在容量的两倍；
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
//【5.2】 添加数据
createEntry(hash, key, value, bucketIndex);
}【5.2】 添加数据
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【】中计算出的位置中是否已经有数据，如果有的话，那么把他放到链表的下一个节点！
也就是说， 新节点一直插入在最前端，新节点始终是单向列表的头节点；
最后找一段程序试试链表的储存
补充，现在各种存储比如redis，以及阿里的云存储等
从根本上说都是key-value！深刻理解一下吧。
代码读不懂画画图唱唱歌吧，啦啦啦。