在学习hashmap的时候，遇到一个问题，hashmap存放的是键值对，一对[Key,Value]，赋值进去的时候是无序的，取值的时候也应该是无序的。但是，它的顺序是固定的，也就是说它肯定有固定的算法保证这种无序的输出每次都一个样，于是就很有兴致的深入学习了一下hashmap的底层，理解的不对的地方，还请高人指教。
HashMap是一个用于存储Key-Value键值对的集合，每一个键值对也叫做一个节点Node。这些个键值对分散存储在一个数组当中，这个数组就是HashMap的主干。当系统开始初始化 HashMap 时，系统会创建一个长度为 capacity (默认初始值为16)的 Node 数组，这个数组里可以存储元素的位置被称为“桶（bucket）”，每个 bucket 都有其指定索引，系统可以根据其索引快速访问该 bucket 里存储的元素。 HashMap 的每个“桶（bucket）”只存储一个元素（也就是一个 Node），由于 Node 对象可以包含一个引用变量（就是 Node 构造器的的最后一个参数）用于指向下一个 Node，当 Node 多于8个时自动转成树，当 Node 小于6个时自动转成链表。
HashMap的数据结构（数组+链表+树）如下图，桶中的结构可能是链表，也可能是树。
- HashMap内部包含了一个Node类型的数组table， table里的每一个数据都是一个Node对象。
- 再来看table里面存储的Node类型，Node里包含了hash变量，key,value，和另外一个Node对象。指向下一个Node的连接可以链表结构，也可以是树结构，作用是指向，通过我找到你，你再找到他。
我们来看一下jdk源码：
/******************* 源码来自jdk1.8 **************************
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
*/
//初始化时的Node[ ]数组，长度是2的幂
transient Node<K,V>[] table;
// 默认的初始容量是16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 当桶(bucket)上的结点数大于这个值时会转成树
static final int TREEIFY_THRESHOLD = 8;
// 当桶(bucket)上的结点数小于这个值时树转链表
static final int UNTREEIFY_THRESHOLD = 6;
// 桶中结构转化为树对应的table的最小大小
static final int MIN_TREEIFY_CAPACITY = 64;
//******************* 源码来自jdk1.8 ********************
//Node的结构
final int hash; //一个int型的hash值
final K key;
V value;
Node<K,V> next; //一个引用变量，指向下一个Node
//hash值是key的hashCode数的高16位与低16位做与运算，
//默认情况下，Object中的hashCode() 返回对象的32位jvm内存地址。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
那么数据是怎么存进去的呢？
put方法
元素位置的计算方法是 table长度减1,和key的hash做与运算，即：(table.length-1) & hash（Key）得到一个index位置，就是这个node在数组中的位置，打个比方，第一个键值对A进来，通过计算得到的index=0，记做:Node[0] = A。一会后又进来一个键值对B，通过计算其index也等于0，现在怎么办？HashMap会这样做:B.next = A,Node[0] = B,如果又进来C,index也等于0,那么C.next = B,Node[0] = C；这样我们发现index=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起。数组中存储的是最后插入的元素。
//****************** 源码来自jdk1.8 **************************
public V put(K key, V value) {
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;
// table未初始化或者长度为0，进行扩容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// (n - 1) & hash 确定元素存放在哪个桶中，桶为空，新生成结点放入桶中
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else { // 桶中已经存在元素
Node<K,V> e; K k;
// 比较桶中第一个元素的hash值相等，key相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p; // 将第一个元素赋值给e，用e来记录
else if (p instanceof TreeNode) // hash值不相等；为树结点
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;// 跳出循环
}
// 判断链表中结点的key值与插入的元素的key值是否相等
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break; // 相等，跳出循环
p = e;
}
}
// 表示在桶中找到key值、hash值与插入元素相等的结点
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 实际大小大于阈值则扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
get方法
使用Get方法根据Key来查找Value的时候，首先会把输入的Key做一次Hash，(table.length-1) & hash（Key）得到对应的index，如果桶（bucket）中的第一个数组元素相等就返回，如果index匹配到多个Node,这时候就需要顺着对应链表的头节点，一个一个向下来查找；如果是树结点就在树中查找，如果是链表就在链表中查找。
//****************** 源码来自jdk1.8 **************************
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;
// table已经初始化，长度大于0，根据hash寻找table中的项也不为空
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;
}
table的长度为什么是2的幂
元素位置 index = hash（Key） & （table.length - 1）
下面我们以值为“apple”的Key来演示整个过程：
1.计算apple的hash，结果为十进制的 93030097 ，二进制的101100010111000011011010001。
2.假定HashMap长度是默认的16，（table.length - 1） 的结果为十进制的15，二进制的1111。
3.把以上两个结果做与运算，10110001011100001101101 0001 & 1111 = 0001，十进制是1，所以 index = 1。
可以说，Hash算法最终得到的index结果，完全取决于Key的Hash值的最后几位。
假设HashMap的长度是10（二进制1010），（table.length - 1）就是9，二进制的1001。重复刚才的运算步骤：10000 1010 & 1001 = 1000，单独看这个结果，看不出什么，但是在这种情况下有些index结果永远不会出现，比如(0110)，而长度16或者其他2的幂，Length-1的值是所有二进制位全为1，这种情况下，index的结果等同于hash后几位的值。只要输入的HashCode本身分布均匀，Hash算法的结果就是均匀的。
