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的哈希值可以表示为
等价于
在jdk中n=31、其中31是一个奇素数，jvm会将31i优化为（i<<<5）i
