前言：顺序存储的结构类型需要一个一个地按顺序访问元素，当这个总量很大且我们所要访问的元素比较靠后时，性能就会很低。散列表是一种空间换时间的存储结构，是在算法中提升效率的一种比较常用的方式，但是所需空间太大也会让人头疼
预备知识：
散列法或哈希法 是一种将字符组成的字符串转换为固定长度（一般是更短长度）的数值的方法。更短的哈希值比用原始值进行数据库搜索更快，这种方法一般用来在数据库中建立索引并进行搜索
散列表或hash表 是能够通过给定的关键字的值直接访问到具体对应的值的一个数据结构。也就是说，把关键字映射到一个表中的位置来直接访问记录，以加快访问速度。
哈希表内部的数组元素，很多地方也叫 Bucket(桶)，整个数组叫Buckets或者Bucket Array
散列表为什么会产生冲突呢？
产生冲突是由于哈希函数有时对不同的 Key 计算之后获得了相同的地址
哈希冲突可能会导致数据存储和查找的效率下降的原因主要有两点：
- 查找效率下降：当发生哈希冲突时，即多个键被映射到相同的哈希值，这些键可能被存储在同一个桶（bucket）中。在查找时，需要遍历这个桶中的所有键值对来确定目标键的实际位置，这会增加查找的时间复杂度。当哈希冲突较为严重时，桶中可能会包含大量的键值对，导致查找效率显著下降。
- 存储效率下降：在发生哈希冲突时，哈希表通常需要通过额外的数据结构（如链表或红黑树）来解决冲突，使得每个哈希桶存储的不再是单个键值对，而是多个键值对组成的链表或树结构。这样会增加额外的内存开销，并且在插入或删除操作时需要维护这些数据结构，导致存储效率下降。
因此，哈希冲突可能会导致数据存储和查找的效率下降，影响哈希表的性能表现。为了解决这个问题，需要采取一些方法来有效地处理哈希冲突，如开放定址法、链地址法或者更为复杂的技术，以提高哈希表的效率和性能。
解决hash冲突的常用方法：
开放地址法（也叫开放寻址法）实际上就是当需要存储值时，对Key哈希之后，发现这个地址已经有值了，这时该怎么办？不能放在这个地址，不然之前的映射会被覆盖。这时对计算出来的地址进行一个探测再哈希，比如往后移动一个地址，如果没人占用，就用这个地址。如果超过最大长度，则可以对总长度取余。这里移动的地址是产生冲突时的增列序量
再哈希法 在产生冲突之后，使用关键字的其他部分继续计算地址，如果还是有冲突，则继续使用其他部分再计算地址。这种方式的缺点是时间增加了
链地址法 链地址法其实就是对Key通过哈希之后落在同一个地址上的值，做一个链表。其实在很多高级语言的实现当中，也是使用这种方式处理冲突的，我们会在后面着重学习这种方式
JDK1.8中哈希冲突解决方案
默认使用单向链表将元素串起来
1.在添加元素时，可能会由单向链表转为红黑树来存储元素
比如当哈希表容量≥64且单向链表的节点数量大于8时
2.当红黑树节点数量少到一定程度时，又会转为单向链表
总结：JDK1.8中的哈希表是使用链表+红黑树解决哈希冲突
为什么不使用双链表或者直接在链表首端添加？
因为并不是根据大小来进行hash值的插入而是从前往后或者从后往前一个个的进行比对，如果value相同则进行覆盖
索引值(hash函数)
哈希表中哈希函数的实现步骤
1．先生成key 的哈希值（必须是整数)
2．再让 key的哈希值跟数组的大小进行相关运算，生成一个索引值
public int hash(object key) {
return hash_code( key) % table.length;
}
为了提高效率，可以使用&位运算取代%运算
同时还需要将数组的长度设计为2的幂(2")
这样再配合位运算可以帮助我们有效的将哈希值限制在哈希表的容量范围内
public int hash( object key) {
return hash_code( key ) & (table. length - 1) ;
}
预备知识：与运算都为1结果才是1
问题：为什么要设计为2的n次幂？
10100
& 01111 ==> 2^n
----------
10100
二进制减法运算规则 0-1=1（产生错位）如下
1 2^0 0 2^0-1
10 2^1 01 2^1-1 => 1
100 2^2 011 2^2-1 => 11
1000 2^3 0111 2^3-1 => 111
2^n-1的二进制整数其实是11、111、111.....n个1
任何数&1111 结果还是原来的数
意味着所得结果大小范围为 0 到 1111 ( 2^n-1 ) 之间 如下
1 0011 1101
11 & 1111 & 1111
111 ------- -------
..... 0011 1101
1...第n个1
所以数组长度设计为2的n次幂时，所得索引值的范围是0 - table.length-1
hashCode
预备知识：
int、float占4个字节为32位
long、double 占8个字节为64位
java官方规定hash值必须是int类型
思考：为什么hashCode必须是int?
hashCode就是链表的索引（数组索引），若规定为long存储数据太大可能造成内存溢出，int较为合适
hashcode(key)的值具体怎么计算？key可以为哪些类型？
可以为整数、浮点数、字符串、自定义对象
不同种类的key，哈希值的生成方式不一样，但目标是一致的（默认以int类型作为hash值）
hash值计算要求：
尽量让每个key的哈希值是唯一的
尽量让key的所有信息参与运算
- 各种类型的hash值计算方式：
int的hashCode
public static int hashCode(float value) {
return value；
}
float的hashCode
floatToinBits 方法将 float 转换为二进制整数作为hash值
Integer.toBinaryString(1.2f); //
Float.floatToIntBits(1.2f); //浮点数转化为int，中间实质经历了toBinaryString
public static int hashCode(float value) {
return fLoatToIntBits(value)；
}
long和double的hashCode(右移32位异或运算)
public static int hashCode(long value){
return (int)(value^(value>>>32));
}
public static int hashCode(long value){
value=doubleToLongBits(value);
return (int)(value^(value>>>32));
}
采用 | 运算 vlaue>>>32若为 00000...00 结果是value
采用 & 运算 value>>>32若为 11111....11 结果是value>>>32
只有异或运算才能够混合运算出不同值
所以long和double是高低32位异或运算
这样做既约束了hash值的范围，又保证了key的每一部分都参与了运算
字符串的hashCode（重复计算和乘数奇数数）
整数5489是如何计算出来的?
5* 10^3＋4* 10^2+8* 10^1 +9 * 10^0
字符串是由若干个字符组成的
字符串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?
31是一个奇素数 (既是奇数，又是素数，也就是质数)，素数和其他数相乘的结果比其他方式更容易产成唯一性，减少哈希冲突，最终选择31是经过观测分布结果后的选择
31* i = (32-1)* i = (2^5-1)* i = i*2^5 - i = (i<< 5) - i
JVM会将 31*i 优化成 (i<<5)- i
进行验证，如下：
public static void main( String[] args) {
string string = "jack"; //3254239int
len = string.length();
int hashCode = 0;
for (int i = 0; i < len; i++) {
char c = string.charAt(i);
hashCode = hashCode * 31 +c;
//hashCode = ( hashCode << 5) - hashCode + c;
}
system.out.print1n(hashcode ) ;
//hashCode = ((j* 31 +a)* 31 +c)* 31 +k
}
官方实现
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;
}
总结：所有类型的hashCode的调用方法
public static void main( String[ ] args){
Integer a = 110;
Float b = 10.6f;
Long c = 1561;
Double d = 10.9;
string e = "rose";
System.out. print1n(a.hashCode());
System. out.println(b.hashcode());
System.out.println(c.hashCode());
System.out.println(d.hashcode());
System.out.println(e.hashCode());
}
对象的hashCode
对象的每个属性相当于字符串的每一个字符
public class Student{
public String name;
public int age;
public float weight;
....
}
public void main(String[] args){
Student s1= new Student("zhangsan",10,100.1f);
Student s2= new Student("zhangsan",10,100.1f);
HashMap map = new HashMap();
map.put(s1,10);
map.put(s2,20);
map.size();
}
思考：map.size()的值为多少？
若没有重写hashCode方法，那么s1和s2的hashCode是依据 对象的内存地址 计算而来，明显不一样
思考：观察发现s1和s2是两个相同的对象，s1和s2的hashCode应该一样才对，那么怎么才能保证它们的hashCode相同？
解决问题：引用类型需要重写hashCode方法
@override
public int hashCode(){
int hashCode=name ? 0 : null : name.hashCode();
hashCode=hashCode*31 + Integer.hashCode(age);
hashCode=hashCode*31 + float.hashCode(weight);
return hashCode;
}
思考：不同对象的索引值可能一样吗？不同类型的索引值可能一样吗？
public void main(String[] args){
Student s1= new Student("zhangsan",10,100.1f);
Student s2= new Student("lisi",13,87.1f);
}
public void main(Stirng[] args){
String name="zhangsan"
int age=10;
float weigt=100.1f;
}
首先根据之前所述，索引值的公式为：
索引值=（对象、基本类型）hashCode & table.length-1
s1与s2的hashCode不同，生成索引可能相同
name、age、weight不同，生成索引可能相同
hashCode不同，但生成索引可能相同
hashCode相同，生成索引一定相同
解决问题：所以重写hashCode的还不能完全保证合理，还需要重写equals方法
@override
public void equals(Obejct obj){
//内存地址一样，绝对是同一个对象
if(this==obj)return true;
//(obj==null || !obj.instanceOf(Person))return true;
if(obj==null || obj.getClass()!=getClass())return false;
//return obj.hashCode()==hashCode() 两个不同对象hash值可能一样
Person person=(Person)obj；
return person.name==null?name=null : person.name.equals(name)&&person.age==age&&person.weight==weight;
}
首先比较内存地址，内存地址一样绝对是同一对象
内存地址不一样是不同对象，不同对象可能代表同一个人，所以需要继续验证
但是不同类的话绝对不是同一个人，先看是否是同类
最后再比较 同一个类不同对象的每一个属性
再或者根据需求而定
值比较对象其中之一的属性
比如同一个人的年龄和体重可能发生变化，但是名字不改变
@override
public void equals(Obejct obj){
if(this==obj)return true;
//(obj==null || !obj.instanceOf(Person))return false;
if(obj==null || obj.getClass()!=getClass())return false;
Person person=(Person)obj；
return person.name==null?name=null : person.name.equals(name);
}
思考：都不重写，只重写hashCode，或者只重写equals分别会发生什么情况？
public void main(String[] args){
Student s1= new Student("zhangsan",10,100.1f);
Student s2= new Student("zhangsan",10,100.1f);
HashMap map = new HashMap();
map.put(s1,10);
map.put(s2,20);
map.size();
都不重写
情况1：s1与s2的hashCode不一样，生成的索引也不一样，size=2
情况2：s1与s2的hashCode不一样，生成的索引一样，equals默认比较内存地址，s1与s2不一样，size=2
情况3：s1与s2的hashCode一样，生成的索引一样，equals默认比较内存地址，s1与s2不一样，size=2
其余两种（只重写equals和只重写hashCode）按上面的步骤进行分析
结论：自定义对象作为key，最好同时重写hashcode ，必须保证equals为true的2个key的哈希值一样，反过来hashcode相等的key，不一定equals为true
思考：索引判断和equals判断先后顺序？
因为一般情况下索引都不一样，所以判断时先索引再equals
