下面这个场景，希望在内存中采用一种数据结构，能够快速的通过商品型号查询到商品价格。
这里我们需要一个:
------能够存储多条记录，
------单条记录查询速度快(不用循环遍历)，
的容器
HashMap就是这样一种数据结构！！
让我们通过以下两个方面，来认识一下这种数据结构：
- HashMap是什么？
- java中的HashMap实现
HashMap是什么？
简单说，HashMap是个特殊的数组，每条数据存储的下标是由Hash函数计算得到！
- 首先我们把产品的型号和价格看作是一对key／value
- key通过Hash函数，会得到一个在某一特定范围内唯一的值
- 如果选用数组保存数据，那上面得到的这个值就是数组下标，value就可以保存在下标指示的这个位置
- 数据读取的时候，搜索关键词(型号)也是先通过Hash函数得到一个下标，然后去相应的位置找value
很多聪明的同学这时候就会想到一些特殊的情况：
- 不同型号的商品，通过Hash函数，有没有可能得到同样的位置？
- 两件商品有没有可能型号相同，但是价格不同，这该怎么处理？
第1个问题；
Hash函数会尽可能的保证在一个特定的数值范围内，得到的下标不重复！不过有时候事情总是不那么完美，终归会遇到奇迹，当不同key得到相同下标的时候，称这种情况为冲突。
有没有觉得很像是去医院看病，挂好号之后去分诊台分诊，病人就会被划分到不同医生那里，每个医生都会有好多病人，分诊台会自动为这些病人排队，到你的时候系统会呼叫你的名字。
没错！如果遇到冲突，那就在这个下标处排队，形成链表，这是一种解决冲突的办法。当然还有很多其他的解决办法，可以好好搜索一下。
第2个问题
型号相同，但是价格不同的商品，这就要看实际的情况了，如果是一般的商品，型号应该是唯一的，出现重复有可能是笔误，我们可以用最新的价格覆盖之前已经存在的价格。
可是也有不一样的情况，例如一个班级的学生，学生姓名相同，但是考试成绩不同，这种情况，就不能简单的覆盖了，虽然名字相同，但是完全是两个人啊。
因此在实现Hash函数的时候，我们应该引入对两个对象是否相同的判断，即使key相同，也有可能有不一样的结果。
java中的HashMap实现
- 初始化容量
- Hash函数的作用
- 可以动态扩容
- 冲突解决办法：单独链表法＋红黑树
到这里其实已经知道了HashMap大致原理，那让我们来仔细看看Java中实现HashMap的具体情况，以下是根据个性化特征详细描述。
初始化容量
在详细介绍前，我们先来一个简单的例子，初始化一个容量为5的HashMap，并简单存入一些数据：
public class hashMap {
public void collectionHashMap()
{
HashMap<String,Integer> map = new HashMap<String,Integer>(5);
map.put("beijing", 100);
map.put("shanghai",80);
map.put("guangzhou", 90);
}
}
从代码和配图就可以看出，代码中申请的是容量为5的HashMap，但是实际的空间为8，阀值为6，我们来看看是什么情况？
/*以下是重要的属性*/
//默认初始化容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//负载因子，涉及到什么时候resize
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//存储的数组
transient Node<K,V>[] table;
//数组中实际存储数据大小
transient int size;
//阀值
int threshold;
/*以下是4个不同的初始化函数*/
//指定初始化容量和负载因子
public HashMap(int initialCapacity, float loadFactor)
//指定初始化容量
public HashMap(int initialCapacity)
//使用默认容量16和默认负载因子
public HashMap()
//构建和指定map一样
public HashMap(Map<? extends K, ? extends V> m)
这是四种初始化函数，我们的代码中采用的是第二种
//用的是默认的负载因子
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//实际执行的初始化函数
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;
//这里阀值要被tableSizeFor函数重新计算
this.threshold = tableSizeFor(initialCapacity);
}
//这里就是比较特殊的一个地方，这个函数是通过几轮无符号右移，再加上异或，最后得到的n一定是2的幂
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
//上面这里大家可以算一下，输入的是5（或者是6），经过几轮运算会变成8（2的幂）
//这时候已经有了initialCapacity容量，负载因子loadFactor和阀值threshold，但是没看到初始化我们的table数组啊，那用的时候怎么办？那我们就来看用的时候怎么办？
//put函数调用了putVal函数
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//putVal函数首先判断当前的table是不是null，如果是null，则resize重新分配容量
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
...
//下面我们来看看最重要的resize函数
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
//第一次使用，table没有初始化，因此容量为0
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
}
//这里很重要，oldThr是有值的，因此会执行这段代码
else if (oldThr > 0)
//把初始化的阀值付给了新的容量（也就是新容量为8）
newCap = oldThr;
//这个是没有任何参数时
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//既然阀值付给了新的容量，那我们重新计算一个阀值吧
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
//终于初始化Node类型的数组了！！！
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
...
从上面我们就可以看出来初始化这个HashMap的时候的做法，那为什么容量一定要是2的n次方呢？？
因为要让每个数据能在容量范围内均匀分布
因为后面的章节中会介绍到，确定元素位置的公式是：
(容量-1)&hash值
如果我们的容量为8，任意一条数据的hash值都会与容量-1做按位与操作，自己领会一下其中的意思吧。
Hash函数
HashMap并不是自己又实现了一套Hash函数，而是在key.hashCode()基础上，也就是在Object.hashCode()的基础上，又做了些操作，从而得到了真正的hash值。
static final int hash(Object key) {
int h;
//右移16位，然后与原来的值做异或操作
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
(h = key.hashCode()) ^ (h >>> 16)
有了hash值，那怎么确定在数组中的位置呢？看看put函数中的代码就知道了。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//(n-1)&hash就是通过hash来定位的，如果这个位置的值等于null，就可以存入了
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
....
(n - 1) & hash 这里的n是当前容量
那我们通过上面截图举的那个实例，看看“shanghai”是不是真的通过一系列运算，会保存在数组0的位置。
可以看到，通过一系列计算后，得到的hash值是-747430380，这个值会保存在Node<K,V>对象的hash变量中，和截图中的一致，然后再通过和容量-1进行按位与操作，最终得到的下标是0.
动态扩容
这是java的HashMap的精髓，能够动态扩容
先看一下代码：
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;
}
//扩容为原有容量的2倍
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 defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//刚才容量为2倍了，现在重新计算阀值
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
//扩容了一个原有容量2倍的数组
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//扩容之后重新分布原有数据
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//节点有数据，但没有链表
if (e.next == null)
//原有数据的hash值(这个hash值是经过计算的)和新容量-1做按位与
newTab[e.hash & (newCap - 1)] = e;
//节点是一个红黑树
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
//这里是链表，循环处理链表中每个元素
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
//原位置
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
//原位置加8（原有容量）
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
从上面的代码中，我们应该看到几个比较重要的地方：
- 如果扩容，新容量是原来的2倍
- 扩容过程中，原有数据需要重新定位，但是不需要重新hash就能判断新位置
第2点我们重点来分析一下：
因为在Node<K,V>中记录了第一次数据进入数组时的hash值，因此在resize时我们就不需要重新计算了，只需要拿出来，和新的容量-1做按位与操作，就能确定这条记录的新位置。
newTab[e.hash & (newCap - 1)]
可以看到，如果resize的话，shanghai这条数据的位置是原有位置+8。
当然其它数据也可能位置不变，相信大家自己就能看出来。
新的位置有可能是当前位置不变，也有可能是当前位置+8，链表中元素同理
冲突解决办法
前面提到过，解决冲突使用链表法，但是链表长度超过一定的值，则会改为红黑树
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果新数组
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;
//如果key和key的hash值完全相等，那就直接覆盖
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果原有的p是一个红黑树节点对象，则走红黑树的逻辑
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {//key不相等，也不是树节点，那就只能进行链表了
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;
}
//如果发现这个节点key和key的hash值相同，则覆盖
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;
//如果超过阀值，则需要resize
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
从上面的代码，就可以看出，当遇到冲突的时候，Node节点的next可以指向另一个Node节点，形成了单链表，当链表的长度大于某个阀值时，链表会转化为红黑树。
static final int TREEIFY_THRESHOLD = 8; //链表长度阀值
也就是说，当链表长度超过8的时候，就会变成红黑树，当元素比较多的时候，红黑树自身带着一种平衡排序的原理，便于查找，具体细节，请查看我另一篇文章。
总结
写到这里，HashMap的大致原理是明白了，知道了这些细节，对以后写代码中是否要使用HashMap就有个明确的认识了。
