1、哈希表

哈希表也叫做散列表（hash有剁碎的意思）
1、空间换时间
2、哈希函数也叫做散列函数
3、哈希表的内部数组元素，很多地方也叫做bucket（桶），整个数组叫做buckets或者 Bucket Array

2、哈希冲突

hash冲突

两个不同的key经过hash函数算出相同的结果
解决hash冲突常见的方法：
1、开放定址法（Open Addressing）
按照一定的规则向其他地址探测，直到遇到空桶
2、在哈希法
设计多个哈希函数
3、链地址法（Separate Chaining）
比如通过链表将统一index的元素串起来

3、JDK1.8的哈希解决冲突方案

JDK1.8的哈希解决冲突方案

1、默认使用单向链表串起来
2、在添加元素时，可能会由单向链表转为红黑树来存储元素
比如当哈希表容量>=64且单向链表的节点数量大于8时
3、当红黑树节点数量少到一定程度时，又会转为单向链表
4、JDK1.8的哈希表使用链表+红黑树解决哈希冲突

4、哈希函数

哈希表中的哈希函数的实现步骤大致如下
1、先生成key的哈希值（必须是整数）
2、再让key的哈希值跟数组的大小进行相关运算，生成一个索引值

public int hash(Object key) {
    return hash_code(key) % table.legnth;
}

为了提高效率，可以使用&取代%运算（条件：将数组的长度设计成2的幂次方）

public int hash(Object key) {
    return hash_code(key) & (table.legnth - 1);
}

5、生成Key的哈希值

key的常见种类可能有
整数、浮点数、字符串、自定义对象
不同种类的key，哈希值生成方式不一样，但目标是一致的

尽量让每个key的哈希值是唯一的
尽量让key的所有信息参与运算

在java中HashMap的key必须实现hashCode、equals方法、也允许key为null
1、整数

public static int hashCode(int value) {
    return value;
}

2、浮点数

public static int hashCode(float value) {
    return floatToIntBits(value);
}

5.1、Long和Double的哈希值

public static int hashCode(long value) {
    return (int)(value ^ (value >>> 32));
}

public static int hashCode(double value) {
    long bits = doubleToLongBits(value);
    return (int)(bits ^ (bits >>> 32));
}

>>>（无符号右移）^ （异或）
高32位和低32位混合计算出32bit的哈希值

5.2、字符串的哈希值

字符串是由若干个字符组成的
比如字符串 jack由j、a、c、k四个字符组成（字符串本身是整数）
因此,jack的哈希值可以表示为 $j*n^3 +a *n^2 + c*n^1 + k*n^0$
等价于 $[(j*n + a)*n + c]*n + k$
在jdk中n=31、其中31是一个奇素数，jvm会将31i优化为（i<<<5）i