什么是哈希表
最理想的搜索方法 , 即就是在查找某元素时 , 不进行任何比较的操作 , 一次直接查找到需要搜索的元素 , 可以达到这种要求的方法就是哈希表.哈希表就是通过构造一种存储结构 , 通过某种函数使元素存储的位置与其关键码位形成一 一映射的关系 , 这样在查找元素的时候就可以很快找到目标元素
哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称为哈希表(Hash Table)(或者称散列表)
存在一个数组集合 {1，7，6，4，5，9}.
哈希函数设置为：hash(key) = key % capacity;
capacity 为存储元素底层空间总的大小。
如图所示: 这样存储数据更加便于查找
采取上面的方法，确实能避免多次关键码的比较，搜索的效率也提高的，但是问题来了，拿上述图的情况来举例子的话，我接着还要插入一个元素 14，该怎么办呢？
这个就是我们本章的重点，哈希冲突，4%10 = 4；14%10 = 4，此时发生了哈希冲突。
什么是哈希冲突
哈希冲突的概念
首先我们得知道，哈希冲突是必然的，无论怎么插入，插入多少都无法杜绝，哪怕就插入两个元素4，14都发生了哈希冲突，我们能做的就是尽量避免哈希冲突的发生。
这也就是我们哈希表这种结构存在的问题。
哈希冲突的概念：两个不同关键字key通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。
把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。
降低哈希冲突的发生的概率
两种解决方法
1.设计好的哈希函数；2.降低负载因子
哈希函数设计原则：
-
哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间。
-
哈希函数计算出来的地址能均匀分布在整个空间中。
-
哈希函数应该比较简单。
常用的两种哈希函数
1. 直接定制法
取关键字的某个线性函数为散列地址： Hash （ Key ） = A*Key + B
优点：简单、均匀。
缺点：需要事先知道关 键字的分布情况 使用场景：适合查找比较小且连续的情况。
2. 除留余数法
设散列表中允许的 地址数为 m ，取一个不大于 m ，但最接近或者等于 m 的质数 p 作为除数，按照哈希函数： Hash(key) = key% p(p<=m), 将关键码转换成哈希地址
降低负载因子
从图中我们可以直到要想降低冲突的概率，只能减小负载因子，而负载因子又取决于数组的长度。
公式： 负载因子 = 哈希表中元素的个数 / 数组的长度
因为哈希表中的已有的元素个数是不可变的，所以我们只能通过增大数组长度来降低负载因子。
当冲突发生时如何解决哈希冲突
解决哈希冲突 两种常见的方法是： 闭散列 和 开散列
闭散列
闭散列：有两种（线性探测法&&二次探测法）
闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以 把 key 存放到冲突位置中的 “ 下一个 ” 空位置中去。
线性探测
①什么是线性探测：
从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
②线性探测的相关操作：
当插入操作时，通过哈希函数获取待插入元素在哈希表中的位置 ；如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到 ；下一个空位置，插入新元素
简而言之就是寻找下一个空的地方
③弊端：（可能会导致冲突元素均被放在一起）
二次探测
①如何进行二次探测：
利用这个公式进入插入。其中：i = 1,2,3…，Hi是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小。
对于上述线性探测中的问题如果要插入44，产生冲突，使用解决后的情况为：
②重要结论：
当表的长度为质数且表装载因子 a 不超过 0.5 时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情 况，但在插入时必须确保表的装载因子a 不超过 0.5 ，如果超出必须考虑增容。
因此：闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷。
开散列
开散列：它的叫法有很多，也叫做哈希桶/链地址法/拉链法
①什么是哈希桶？？？
开散列法又叫链地址法 ( 开链法 ) , 首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。 开散列，可以认为是把一个在大集合中的搜索问题转化为在小集合中做搜索了。 参照下图：
②哈希桶如何进行存储？？？（链式存储法）.
③若遇到负载因子过大，要扩容，那么存入的数据又该怎么进行处理？？？（链表中的每一个数要进行重新哈希）,以下为二倍扩容后的图
实现一个哈希表
public class HashBuck {static class Node {public int key;public int val;public Node next;public Node(int key,int val) {this.key = key;this.val = val;}}public Node[] array;public int usedSize;public static final double DEFAULT_LOAD_FACTOR = 0.75;public HashBuck() {this.array = new Node[10];}/*** put函数* @param key* @param val*/public void put(int key,int val) {//1、找到Key所在的位置int index = key % this.array.length;//2、遍历这个下标的链表，看是不是有相同的key。有 要更新val值的Node cur = array[index];while (cur != null) {if(cur.key == key) {cur.val = val;//更新val值return;}cur = cur.next;}//3、没有这个key这个元素，头插法Node node = new Node(key, val);node.next = array[index];array[index] = node;this.usedSize++;//4、插入元素成功之后，检查当前散列表的负载因子if(loadFactor() >= DEFAULT_LOAD_FACTOR) {resize();//}}//扩容private void resize() {Node[] newArray = new Node[array.length*2];for (int i = 0; i < array.length; i++) {Node cur = array[i];while (cur != null) {int index = cur.key % newArray.length;//获取新的下标 11//就是把cur这个节点，以头插/尾插的形式 插入到新的数组对应下标的链表当中Node curNext = cur.next;cur.next = newArray[index];//先绑定后面newArray[index] = cur;//绑定前面cur = curNext;}}array = newArray;}private double loadFactor() {return 1.0*usedSize/array.length;}/*** 根据key获取val值* @param key* @return*/public int get(int key) {//1、找到Key所在的位置int index = key % this.array.length;//2、遍历这个下标的链表，看是不是有相同的key。有 要更新val值的Node cur = array[index];while (cur != null) {if(cur.key == key) {return cur.val;}cur = cur.next;}return -1;}说明：以上的代码只是简单的实现了两个重要的函数：插数据和取数据
并且只是简单的实现，底层的树化并没有实现。
问题--》
问题一：以上代码的key是整形，所以找地址的时候，可以直接用 key % array.length，如果我的key是一个引用类型呢？？？，我怎么找地址？？？
下面这段代码，两者的 id 都一样，运行结果却不一样，这就和我们刚刚的相同的key发生冲突就不一致了
class Person {public String id;public Person(String id) {this.id = id;}@Overridepublic String toString() {return "Person{" +"id=" + id +'}';}
}
public class Test {public static void main(String[] args) {Person person1 = new Person("134");Person person2 = new Person("134");System.out.println(person1.hashCode());System.out.println(person2.hashCode());}
}
重写hashCode()方法
class Person {public String id;public Person(String id) {this.id = id;}@Overridepublic String toString() {return "Person{" +"id=" + id +'}';}@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;Person person = (Person) o;return id == person.id;}@Overridepublic int hashCode() {return Objects.hash(id);}
}
public class Test {public static void main(String[] args) {Person person1 = new Person("134");Person person2 = new Person("134");System.out.println(person1.hashCode());System.out.println(person2.hashCode());}
}1.为什么引用类型就要谈到 hashCode() ？？
在引用类型中，比较对象的相等性通常需要使用 equals() 方法。但是在某些情况下，我们需要将对象用作集合（如 HashSet、HashMap）的键或进行哈希表操作时，还需要使用 hashCode() 方法。
在 Java 中，对象的哈希码（hash code）在哈希表等数据结构中用于确定对象的存储位置。哈希表通过使用对象的哈希码来快速查找和操作元素，以实现高效的插入、查找和删除操作。因此，为了在哈希表中正确地处理对象，我们需要重写 hashCode() 方法。
在哈希表中，首先会根据对象的哈希码计算出存储位置（存储桶），然后再使用 equals() 方法来进一步比较键的相等性。如果不重写 hashCode() 方法，不同的对象即使内容相等，它们的哈希码可能不同，导致在哈希表中无法正确地查找或比较它们。
2.按道理来说，学号相同的两个对象应该是同一个人，为什么重写 hashCode()，返回对象的哈希代码值才会一样，不重写为什么会导致最终在数组中寻找的地址不相同？？因为底层的hashCode()是Object类的方法，底层是由C/C++代码写的，我们是看不到，但是因为它是根据对象的存储位置来返回的哈希代码值，这里就可以解释了，person1和person2本质上就是两个不同的对象，在内存中存储的地址也不同，所以最终返回的哈希代码值必然是不相同的，哈希代码值不同，那么在数组中根据 hash % array.length 寻找的地址也就不相同。而重写 hashCode() 方法之后，咱们根据 Person 中的成员变量 id 来返回对应的哈希代码值，这就相当于当一个对象，多次调用，那么返回的哈希代码值就必然相同。
所以我们的哈希表的实现就可以相应的改写成这样：
public class HashBuck<K,V> {static class Node<K,V> {public K key;public V val;public Node<K,V> next;public Node(K key,V val) {this.key = key;this.val = val;}}//往期泛型博客有具体讲到数组为什么这样写public Node<K,V>[] array = (Node<K,V>[]) new Node[10];public int usedSize;public static final double DEFAULT_LOAD_FACTOR = 0.75;public void put(K key, V val) {Node<K,V> node = new Node<>(key,val);int hash = key.hashCode();int index = hash % array.length;Node<K,V> cur = array[index];while(cur != null) {if(cur.key.equals(key)) {cur.val = val;return;}cur = cur.next;}//头插node.next = array[index];array[index] = node;this.usedSize++;if(loadFactor() >= DEFAULT_LOAD_FACTOR) {reSize();}}private double loadFactor() {return this.usedSize * 1.0 / array.length;}private void reSize() {Node<K,V>[] newArray = (Node<K, V>[]) new Node[2 * array.length];for (int i = 0; i < array.length; i++) {Node<K,V> cur = array[i];while (cur != null) {Node<K,V> curNext = cur.next;int hash = cur.key.hashCode();int index = hash % newArray.length;cur.next = newArray[index];newArray[index] = cur;cur = cur.next;}}array = newArray;}public V get(K key) {int hash = key.hashCode();int index = hash % array.length;Node<K,V> cur = array[index];while(cur != null) {if(cur.key == key) {return cur.val;}cur = cur.next;}return null;}
}性能分析
虽然哈希表一直在和冲突做斗争，但在实际使用过程中，我们认为哈希表的冲突率是不高的，冲突个数是可控的，也就是每个桶中的链表的长度是一个常数，所以，通常意义下，我们认为哈希表的插入 / 删除 / 查找时间复杂度是 O(1)
面试问题一：hashCode()和equals() 在HashMap中的作用分别是什么？？？
1. hashCode() 方法用于确定对象在哈希表中的存储位置。HashMap 使用哈希码来计算键的存储位置，以便在查找、插入和删除元素时能够快速定位到对应的存储桶（bucket）。每个键对象的 hashCode() 方法返回的哈希码将被用作该键在哈希表中的索引。
2. equals() 方法用于检查两个键对象是否相等。当两个键的哈希码相同时，HashMap 会使用 equals() 方法来进一步比较键的内容是否相等。这是为了解决哈希冲突的情况，当不同的键具有相同的哈希码时，需要通过 equals() 方法进行确切的比较来确定它们是否相等。
具体来说，当我们向 HashMap 中插入键值对时，它会根据键的哈希码找到对应的存储桶，并在该存储桶中进行查找或插入操作。在这个过程中，会使用键对象的 hashCode() 方法来计算哈希码，并使用 equals() 方法来检查键的相等性。
在使用自定义类作为键时，我们通常需要重写 hashCode() 和 equals() 方法，以确保它们的正确性和一致性。重写 hashCode() 方法是为了根据对象的属性计算哈希码，以便在哈希表中能够正确定位到存储位置。而重写 equals() 方法是为了根据对象的属性比较相等性，以确保在哈希表中进行查找、插入和删除操作时的正确性。
总结而言，hashCode() 方法在 HashMap 中用于确定键的存储位置，而 equals() 方法用于检查键的相等性。这两个方法在 HashMap 中共同工作，确保正确的键查找和存储。hashCode()：用来找元素在数组中的位置；
equals()：用来比较数组下链表中的每个元素的 key 与我的 key 是否相同。
equals也一样，如果不重写，上面的person1和person2的比较结果必然是不相同。
hashCode()和equals()就好比查字典，比如要查美丽，肯定要先查美字在多少页--hashCode()，然后它的组词有美景，美女，美丽，equals()就能找到美丽。答案肯定是不一定，一定。
同一个地址下链表中的key不一定一样，就好比数组长度为10，4和14找到的都是4下标。
而equals一样，hashCode就一定一样，4和4肯定都在4下标。
所以这时候再回过头来看HashMap数据的打印时，就能明白HashMap和HashSet为什么无序了，它本身就不是一个顺序结构,至于TreeMap和TreeSet为啥有序，这就和我们之前学过的优先级队列是一个道理了。（整形的key，输出时，自然而然就排好序了，如果key是引用类型，则需要实现Comparable接口，或者传比较器）