在实现快速查询上，哈希表是经常使用的一种数据结构，是根据关键码值(Key value)而直接进行访问的数据结构。而Java实现HashMap的原理具体是怎样的，需要以下方面来理解：
1.Java中分散与指针结构
2.HashMap的构造函数以及各个版本底层构造
3.hashCode的计算以及数组下标的计算
4.哈希冲突的发生和解决方案
一、Java中分散与指针结构
Java编程语言实现HashMap时，是采用分散和指针的数据结构实现一个“链表散列”的数据结构，即是和链表的结合体。
二、HashMap的构造函数以及各个版本底层构造
1.HashMap构造函数为：
//构造函数1
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;
this.threshold = tableSizeFor(initialCapacity);//新的扩容临界值
}
//构造函数2
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//构造函数3
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//构造函数4用m的元素初始化散列映射
public HashMap(Map<!--? extends K, ? extends V--> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
2.底层构造：
在JDK1.6、1.7中，HashMap位桶和链表来实现，而在JDK1.8中，则采用数组和红黑树来实现：
位桶数组：
//Node是单向链表，它实现了Map.Entry接口
static class Node<k,v> implements Map.Entry<k,v> {
final int hash;
final K key;
V value;
Node<k,v> next;
//构造函数Hash值 键 值 下一个节点
Node(int hash, K key, V value, Node<k,v> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() {
return key; }
public final V getValue() {
return value; }
public final String toString() {
return key + = + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
//判断两个node是否相等,若key和value都相等，返回true。可以与自身比较为true
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<!--?,?--> e = (Map.Entry<!--?,?-->)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
红黑树：
//红黑树
static final class TreeNode<k,v> extends LinkedHashMap.Entry<k,v> {
TreeNode<k,v> parent; // 父节点
TreeNode<k,v> left; //左子树
TreeNode<k,v> right;//右子树
TreeNode<k,v> prev; // needed to unlink next upon deletion
boolean red; //颜色属性
TreeNode(int hash, K key, V val, Node<k,v> next) {
super(hash, key, val, next);
}
//返回当前节点的根节点
final TreeNode<k,v> root() {
for (TreeNode<k,v> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
三、hashCode的计算以及数组下标的计算
1.HashCode的计算：
在java.util.HashMap中默认初始容量必须是2的整次数幂，原因是N为2的整数次幂，更加合理。
h(hashcode) = hashcode % N 等价于 h(hashcode) = hashcode &(N-1)
//操作与运算符，两数相与都为1结果才为1.而操作符&的运算速率比%效率更高
java.lang.Object.hashCode() 的实现：
public native int hashCode();
/*
Returns a hash code value for the object. This method is supported for the benefit
of hashtables such as those provided by java.util.Hashtable.
The general contract of hashCode is:
1. Whenever it is invoked on the same object more than once during an execution
of a Java application, the hashCode method must consistently return the same
integer, provided no information used in equals comparisons on the object is
modified. This integer need not remain consistent from one execution of an
application to another execution of the same application.
2. If two objects are equal according to the equals(Object) method, then calling
the hashCode method on each of the two objects must produce the same integer
result.
3. It is not required that if two objects are unequal according to the
equals(java.lang.Object) method, then calling the hashCode method on each of
the two objects must produce distinct integer results. However, the programmer
should be aware that producing distinct integer results for unequal objects may
improve the performance of hashtables.
As much as is reasonably practical, the hashCode method defined by class Object
does return distinct integers for distinct objects. (This is typically implemented
by converting the internal address of the object into an integer, but this
implementation technique is not required by the JavaTM programming language.)
*/
基于上述的要求，该方法的实现是采用把对象的内存地址用 hash 算法得到一个 int 类型的
数。这样的确做到了使不同的对象具有不同的 hash 值。
2.数组下标的计算：
设定一个table下标i=(table.length- 1) & ((h = key.hashCode()) ^ (h >>> 16))
当我们put的时候，会根据key获取对应的hash值，然后无符号右移16位（>>> 16）,在与原本的hash值进行^计算，然后再与table.length-1进行&计算，最终得出需要放入的位置
比如：key = “165156”，HashMap中table数组的大小为16，套入公式，那么我们就会计算出存放位置的下标为13
那么此时如果我们要将原HashMap的table数组扩容一倍，那么数组，以及链表中的对象，都需要重新分配位置，具体情况分为三种：
第一种情况：数组有值，链表无值，这个时候只需要重新计算位置，放进去就OK了（e.hash & (newCap - 1)）这个计算方式，就是上文数组下标计算，这里有个骚操作，可以结合第三种情况一起说
第二种情况：数组有值，链表无值 ，但是红黑树有值，
第三种情况：数组有值，链表有值，业务处理逻辑：循环列表判断每一个元素是否需要换位置，不需要的重新组合成链表，放入当前数组下标中，如果需要的，组成一个链表，放入指定的数组下标中
四、哈希冲突的发生及解决方案
1.哈希冲突的发生：
哈希冲突的发生，当两个不同的数据通过hash算出来的HashCode的值相同时，两者都要放在hash表的同一个位置中时，就发生了hash冲突。
2.哈希冲突解决方案：
在解决哈希冲突方面有多种方法：
一、 开放定址法
一旦发生冲突，就去寻找新的空的地址或者找到了相同的给定关键字，若未找到，则会失败。
二、双哈希法
使用多个Hash算法，在发生冲突后，使用后面的第二个，第三个…直到无冲突。
三、 链地址法
每个哈希表节点都有一个next指针，多个哈希表节点可以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向 链表连接起来。此时即使产生冲突，但是可以通道next指针将冲突所在所在的节点连接起来，这样就解决了哈希的冲突问题。
四、 建立公共溢出区
即建立一个缓冲区，将冲突的放在缓冲区中，在查找不到时在缓冲区中查找。