目录
1、哈希表
1.1、概念
顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。
顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(logN)，搜索的效率取决于搜索过程中元素的比较次数。
理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。 如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。
当向该结构中：
插入元素：根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放
搜索元素：对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功
该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，
构造出来的结构称为哈希表(HashTable)(或者称散列表)
按照上述哈希方式，向集合中插入元素14，会出现冲突的现象，这种现象称为哈希冲突
1.2、冲突
概念：
哈希冲突/哈希碰撞：不同的关键字KEY 通过相同的哈希函数计算出相同的哈希地址
避免：
由于哈希表底层数组的容量往往是小于实际要存储的关键字的数量的，这就导致一 个问题，冲突的发生是必然的，但我们能做的应该是尽量的降低冲突率
解决哈希冲突两种常见的方法是：闭散列和开散列
2、哈希函数设计
引起哈希冲突的一个原因可能是：哈希函数设计不够合理。 哈希函数设计原则：
- 哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间
- 哈希函数计算出来的地址能均匀分布在整个空间中
- 哈希函数应该比较简单
常见哈希函数
1. 直接定址法--(常用)
取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B优点：简单、均匀
缺点：需要事先知道关键字的分布情况
使用场景：适合查找比较小且连续的情况
例如：key : 91
int index = key - minVal minVal是一组数据中最小的数据
2. 除留余数法--(常用)
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m),将关键码转换成哈希地址
3. 平方取中法--(了解)
假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址； 再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址 平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况
4. 折叠法--(了解)5. 随机数法--(了解)
6. 数学分析法--(了解)
注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突
3、负载因子调节
散列表的负载因子定义为：α = 填入表中的元素个数 / 散列表的长度
α 是散列表装满程度的标志因子。由于表长是定值，α 与“填入表中的元素个数”成正比，所以，α 越大，表明填入表中的元素越多，产生冲突的可能性就越大；反之，α 越小，表明填入表中的元素越少，产生冲突的可能性就越小。
Java的系统库限制了负载因子为0.75，超过此值将使用扩容的方式重构散列表，将负载因子控制在 0.75 内
所以当冲突率达到一个无法忍受的程度时，我们需要通过降低负载因子来变相的降低冲突率。 已知哈希表中已有的关键字个数是不可变的，那我们能调整的就只有哈希表中的数组的大小
4、闭散列
闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的 “下一个” 空位置中；那如何寻找下一个空位置呢？
1. 线性探测
比如上面的场景，现在需要插入元素14，先通过哈希函数计算哈希地址，下标为4，因此44理论上应该插在该 位置，但是该位置已经放了值为4的元素，即发生哈希冲突。
线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
插入：
- 通过哈希函数获取待插入元素在哈希表中的位置
- 如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，使用线性探测找到下一个空位置，插入新元素
- 采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素
2. 二次探测
二次探测法指采用前后跳跃式探测的方法，发生冲突时，向后1位探测，向前1位探测，向后2^2 位探测，向前2^2 位探测……以跳跃式探测，避免堆积。
二次探测的增量序列为di =1^2 , -1^2 , 2^2 , -2^2 , …, k^2 , -k^2（k ≤m /2），对应哈希函数中的 i = 1,2,3,4, …
研究表明：当表的长度为质数且表装载因子 α 不超过0.5 时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。
因此只要表中有一半的空位置，就不会存在表满的问题。
在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。
因此：闭散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷
5、开散列/哈希桶（重点掌握）
开散列法又叫链地址法(开链法)
核心思想：将所有元素存储在一个链表中，每个链表的头指针存储在哈希表的相应槽位中。当发生哈希冲突时，新的元素会被添加到对应链表的末尾，哈希表的每个元素就是各链表的头节点
插入链表的时，JDK1.7及以前采用的是头插法，1.8 开始采用尾插法
从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。
开散列，可以认为是把一个在大集合中的搜索问题转化为在小集合中做搜索了
如果冲突严重，就意味着小集合的搜索性能其实也时不佳的，这个时候我们就可以将这个所谓的小集合搜索问题继续进行转化，例如：
1. 每个桶的背后是另一个哈希表
2. 每个桶的背后改变成一棵搜索树，比如说变成红黑树
Java的HashMap就是就是采用开散列的方式来解决哈希冲突的
数组+链表+红黑树(当数组长度 >= 64 && 链表长度 >=8 以后，就会把链表变成红黑树)
6、实现哈希桶
6.1、put方法
面试问题：
1.上图的这种扩容方式可不可行
答：不可以，因为数组长度变了，原来位置冲突的元素可能要放到新的数组的其他位置去
2. 扩容需要注意的是什么？
答：HashMap 扩容时，原来 HashMap 中数组下的每一个结点都要重新计算它在新数组中的位置（重新哈希）
6.2、HashMap的扩容机制
为什么需要扩容？
随着哈希表中存储的元素不断增加，哈希冲突的概率也会越来越高，这会导致哈希表的性能下降，查找、插入和删除操作的时间复杂度可能会接近O(n)。为了保证哈希表的性能，当哈希表中的元素数量达到一定阈值时，就需要对哈希表进行扩容。
扩容的触发条件：
在 HashMap 中，有两个重要的参数：容量（capacity）和负载因子（loadFactor）。容量指的是哈希表中数组的长度，负载因子是一个介于 0 到 1 之间的浮点数，默认值为 0.75。当哈希表中的负载因子大小超过 0.75 时，就会触发扩容操作。
扩容的过程：
- 创建新数组：将原数组的容量扩大为原来的 2 倍。
- 重新哈希：遍历原数组中的每个元素，重新计算它们在新数组中的位置，并将元素插入到新数组中。
6.3、get方法
7、HashMap
HashMap<String,Integer> map = new HashMap<>();
map.put("hello",2);
map.put("abcd",10);
map.put("zhang",3);
Integer val = map.get("abcd");
System.out.println(val); // 10
// 不是按顺序输出的，因为HashMap底层是哈希桶，是通过某种哈希函数确定的位置的
System.out.println(map);
// 遍历方式
for(Map.Entry<String,Integer> entry :map.entrySet()){
System.out.println("key: "+entry.getKey()+" val: "+entry.getValue());
}
Map不支持迭代器遍历，因为支持迭代器遍历的都实现了 Iterable 接口，HashMap和TreeMap 都没有实现 Iterable 接口；要想用迭代器遍历，只能将Map转换为Set，再通过迭代器遍历Set
Map的一个注意事项：HashMap的key可以是对象，也可以是null，TreeMap则不行，因为TreeMap的key必须是可以比较的
HashMap<Student,Integer> map2 = new HashMap<>();
map2.put(new Student(),2); // hashcode
map2.put(new Student(),2);map2.put(null,2);
// 上述代码均能通过
8、HashSet
1. Set不能存储相同的key，天然可以去重的
HashSet<String> set = new HashSet<>();
set.add("hello");
set.add("abcd");
set.add("hello");System.out.println(set); // 打印结果：[hello, abcd]
2. 不是按顺序输出的，因为HashSet底层是哈希桶，是通过某种哈希函数确定的位置的
3. 底层是一个HashMap 每次存储元素时，默认的value是一个Objcet对象
8.1、哈希表性能分析
虽然哈希表一直在和冲突做斗争，但在实际使用过程中，我们认为哈希表的冲突率是不高的，冲突个数是可控的， 也就是每个桶中的链表的长度是一个常数，所以，通常意义下，我们认为哈希表的插入/删除/查找时间复杂度是 O(1) 。
9、hashcode
通过上述可以知道，HashMap的key可以是对象，也可以是null，使用哈希函数的key一定得转化为整数，那么如何把对象转化为整数呢？ -- 使用hashcode方法可以把对象转化为整数
hashcode方法是Object类中的方法，所以可以直接调用
两个相同id的学生，正常情况下在HashMap中在同一个位置，但上图的运行结果得到的整数是不一样的；想要得到正确的结果，需要重写hashcode方法
在IDEA中直接生成，会根据id生成重写的 equals() 和 hashCode() 方法
重写后，再运行相同id的学生会输出相同的整数，这样再通过哈希之后就会在相同的位置；
使用HashMap可以用关键字student2拿到student1的值，说明这里的HashMap调用的是自己重写后的hashcode，如果没有重写则找不到
所以，当以后在写一个自定义类型的时候，最好把equals() 和 hashCode() 方法都进行重写，这样就不会出现一些意料之外的事情；拓展：建议把toString也写一下
9.1、hashCode和equals的区别
1. 如果两个对象相等，那么它们的hashCode()值一定相同。这里的相等是指，通过equals()比较两个对象时返回true。
2. 如果两个对象hashCode()相等，它们不一定相等。因为在散列表中，hashCode()相等，即两个键值对的哈希值相等。然而哈希值相等，并不一定能得出键值对相等，此时就出现所谓的哈希冲突场景。3. hashCode和equals的最大区别就是：hashCode 用于找到关键字在哈希表中的位置，这个位置的关键字的hashCode都是相同的；找到位置后，从该位置下的所有关键字中找到某个关键字用 equals
总结：equals方法用于判断两个对象是否相等，hashCode方法用于生成对象的哈希码。equals方法要求两个对象相等时hashCode值也相等，而hashCode方法要求hashCode值相等时两个对象不一定是相等的
10、实现哈希桶<K,V>
public class HashBuck2<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;
public int usedSize;
public static final float DEFAULT_LOAD_FACTOR = 0.75f;
public HashBuck2() {
array = (Node<K,V>[])new Node[10];
}
public void put(K key,V val) {
int hash = key.hashCode();
int index = hash % array.length;
Node<K,V> cur = array[index];
while (cur != null) {
if(cur.key.equals(key)) {
//更新value
cur.val = val;
return;
}
cur = cur.next;
}
Node<K,V> node = new Node(key,val);
node.next = array[index];
array[index] = node;
usedSize++;
}
public V getValue(K key) {
int hash = key.hashCode();
int index = hash % array.length;
Node<K,V> cur = array[index];
while (cur != null) {
if(cur.key.equals(key)) {
return cur.val;
}
cur = cur.next;
}
return null;
}
}