一.哈希表与哈希冲突
1.什么是哈希冲突
假设hash表的大小为10（即有10个槽），现在要把一串数据存到表里：5,3,56,78,1,4,9,34,56,78
简单计算一下：hash(5)=5, 所以数据5应该放在hash表的第5个槽里；hash(56)=1，所以数据56应该放在hash表的第1个槽里；hash(34)=1，也就是说，数据34也应该放在hash表的第1个槽里——于是就造成了碰撞（也称为冲突，collision）。
2.解决哈希冲突的方法
a.开放地址法
这种方法也称再散列法，其基本思想是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。这种方法有一个通用的再散列函数形式：
Hi=（H（key）+di）% m （i=1，2，…，n）
b.再哈希法
这种方法是同时构造多个不同的哈希函数：
Hi=RH1（key） i=1，2，…，k
当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。
二.HashMap的实现原理
1.HashMap的原理
在Java编程语言中，最基本的结构就是两个，一个是分散，另外一个是指针（引用），HashMap就是通过这两个数据结构进行实现。HashMap实际上是一个“链表散列”的数据结构，即是和链表的结合体。
从上图中可以知道，HashMap就是一个数组结构，数组中的每一个又是一个链表。当新建一个HashMap的时候，就会初始化一个数组。
2.JDK中的构造函数
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);
// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
init();
}
3.HashMap的底层构造
JDK1.6,JDK1.7中，HashMap采用位桶+链表实现，即使用链表处理冲突，但是当位于一个桶中的元素较多，即hash值相等的元素较多时，通过key值依次查找效率较低，而在JDK1.8中，HashMap底层是由数组+链表/红黑树构成的。当添加一个元素（key,value）时，首先计算元素key对应的hash值，利用该哈希值计算出在数组中的位置，但是可能存在该数组下标已经存放过元素了，这时就产生了哈希冲突，解决这个问题的方法就是，形成具有相同hash值的链表，挂在该数组下标下。而当链表长度大于8时，链表就转换为红黑树，这样做的目的是增加查找效率。
数组元素Node<K,V>实现了Entry接口
//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;
}
hash值的计算及所在数组下标的计算
1.hashCode的计算
Integer的计算
源码如下：
@Override
public int hashCode() {
return Integer.hashCode(value);
}
可见Integer重写了hashCode方法，所以该类型返回的是数值本身。
String计算
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;
}
String对象的hashCode的计算是根据每一个字符的Ascall值来计算
假设字符串“abc”则对应的hashCode的值为
31*(31*(31*0+97)+98)+99=96354
2.对应数组下标的计算
计算出key的哈希值后，由于哈希值比较大，不能作为直接作为数组下标，对哈希值进行(高位运算或者取模运算）然后设为数组中的下标位置）HashMap采用的是高位运算，因为高位运算要比取模运算效率高很多，计算机中会更容易识别位运算，但是对于数组的长度也有要求。如下：
数组下标：hash&(map.size-1) = hash%(map.size)
使用高位运算来求数组下标那么数组的长度必须为2的n次幂。
3.数组的扩容
当向容器添加元素的时候，会判断当前容器的元素个数，如果大于等于阈值—即当前数组的长度乘以加载因子的值的时候，就要自动扩容啦。
扩容(resize)就是重新计算容量，向HashMap对象里不停的添加元素，而HashMap对象内部的数组无法装载更多的元素时，对象就需要扩大数组的长度，以便能装入更多的元素。当然Java里的数组是无法自动扩容的，方法是使用一个新的数组代替已有的容量小的数组，就像我们用一个小桶装水，如果想装更多的水，就得换大水桶。
加载因子：一般的数据结构，不是查询快就是插入快，HashMap就是一个插入慢、查询快的数据结构。
但这种数据结构容易产生两种问题：① 如果空间利用率高，那么经过的哈希算法计算存储位置的时候，会发现很多存储位置已经有数据了（哈希冲突）；② 如果为了避免发生哈希冲突，增大数组容量，就会导致空间利用率不高。
而加载因子就是表示Hash表中元素的填满程度。
加载因子 = 填入表中的元素个数 / 散列表的长度
为什么加载因子为0。75？这和概率论里的泊松分布有关