目录
一 哈希表的概念
1.1 引入哈希表
1.2 哈希表概念
二 哈希冲突
2.1 哈希冲突概念
2.2 冲突避免
2.3 常见哈希函数
2.4 负载因子调节
2.5 解决哈希冲突
2.5.1闭散列
1. 线性探测
2. 二次探测
3 闭散列的缺陷
2.5.2 开散列/哈希桶（重要！）
1 开散列法
2 性能分析
三 Java代码实现
四 面试高频问题
4.1 hashCode一样时，equals()的结果一定一样吗？
4.2 equals()一样时，hashCode的结果一定一样吗？
一 哈希表的概念
1.1 引入哈希表
在我们常见的顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，在平衡树中查找的时间复杂度为树的高度，即O(logN )，可以看出，搜索的效率取决于搜索过程中元素的比较次数。
而我们设想能够有一个理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。 如果构造一种存储结构，通过某种函 数(hashFunc)使元素的存储位置与它的关键码之间能够建立映射的关系，那么在查找时通过该函数可以很快找到该元素。
1.2 哈希表概念
哈希表（Hash table，也叫散列表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。
当向该结构中：
插入元素： 根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放。搜索元素： 对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置取元素比较，若关键码相等，则搜索成功。
二 哈希冲突
2.1 哈希冲突概念
例如：数据集合{11，22，33，44，88，66}， 哈希函数设置为：hash(key) = key % capacity（capacity为存储元素底层空间总的大小）。
按照上述哈希方式，向集合中插入元素34，会出现什么问题？
以上这种情况就是哈希冲突的例子，对于两个数据元素的关键字 Ki 和 Kj (i != j)，有Ki != Kj ，但有：Hash(Ki ) == Hash(Kj )，即：不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。
2.2 冲突避免
首先，我们需要明确一点，由于我们哈希表底层数组的容量往往是小于实际要存储的关键字的数量的，这就导致一 个问题，冲突的发生是必然的，但我们能做的应该是尽量的降低冲突率。
引起哈希冲突的一个原因可能是：哈希函数设计不够合理。
哈希函数设计原则：
哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1 之间哈希函数计算出来的地址能均匀分布在整个空间中哈希函数应该比较简单
2.3 常见哈希函数
注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突。
1. 直接定制法--(常用)
取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
优点：简单、均匀。
缺点：需要事先知道关 键字的分布情况
使用场景：适合查找比较小且连续的情况。
2. 除留余数法--(常用)
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数： Hash(key) = key% p(p<=m),将关键码转换成哈希地址。
3. 平方取中法--(了解)
假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址； 再比如关键字为4321，对 它平方就是18671041，抽取中间的3位671(或710)作为哈希地址。
使用场景：不知道关键字的分布，而位数又不是很大的情况。
4. 折叠法--(了解)
折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和， 并按散列表表长，取后几位作为散列地址。 折叠法适合事先不需要知道关键字的分布。
使用场景：适合关键字位数比较多的情况。
5. 随机数法--(了解)
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数 函数。
使用场景：通常应用于关键字长度不等时采用此法。
6. 数学分析法--(了解)
设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某 些位上分布比较均匀，每种符号出现的机会均等，在某些位上分布不均匀只有某几种符号经常出现。可根据 散列表的大小，选择其中各种符号分布均匀的若干位作为散列地址。
例如某高校为新生办理校园卡，可能前七位都是一样的，而只有后面四位不同。
使用场景：数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀的情况。
2.4 负载因子调节
哈希表的负载因子 a = 填入表中元素的个数 / 哈希表的长度，a默认均为0.75。
所以当冲突率达到一个无法忍受的程度时，我们需要通过降低负载因子来变相的降低冲突率。 已知哈希表中已有的关键字个数是不可变的，那我们能调整的就只有哈希表中的数组的大小。
2.5 解决哈希冲突
解决哈希冲突两种常见的方法是：闭散列和开散列.
2.5.1闭散列
闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以 把key存放到冲突位置中的 “下一个” 空位置中去。那如何寻找下一个空位置呢？
1. 线性探测
线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
2. 二次探测
线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨 着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为：Hi = (H0 + i^2 )% m, 或者：Hi = (H0 - i^2 )% m。H0是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置， m是表的大小。
3 闭散列的缺陷
研究表明：当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不 会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的装载因子a不超过0.5，如果超出必须考虑增容。 因此：比散列最大的缺陷就是空间利用率比较低，这也是哈希的缺陷，空间利用率不高。（当负载因子为0.75时，数组大小为10，放第八个元素时就要考虑扩容）
2.5.2 开散列/哈希桶（重要！）
1 开散列法
开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子 集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
开散列从数据结构上可以看作由数组加链表加红黑树组成。（当链表长度大于等于8，链表长度大于等于64，此时将会变成红黑树）
哈希桶是一种哈希表的实现方式，其结构如下：
数组：哈希桶基于数组来实现，每个元素都是一个哈希桶节点。哈希函数：哈希桶使用哈希函数将数据映射到数组中的某个位置。链表：当多个数据经过哈希函数映射到了同一个数组位置时，哈希桶使用链表来解决冲突。哈希桶节点：每个哈希桶节点存储了一个数据项的值、哈希值和一个指向下一个节点的指针。当哈希函数将多个数据项映射到同一个数组位置时，这些数据项会被放在同一个链表中的不同节点上。
2 性能分析
虽然哈希表一直在和冲突做斗争，但在实际使用过程中，我们认为哈希表的冲突率是不高的，冲突个数是可控的， 也就是每个桶中的链表的长度是一个常数，所以，通常意义下，我们认为哈希表的插入/删除/查找时间复杂度是 O(1) 。
三 Java代码实现
这里需要注意的是，在对数组进行扩容之后，需要对每个元素进行重新的哈希运算。
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[] arr;
public int usedSize;
public static final double LOAD_FACTOR = 0.75;
public HashBuck(){
arr = new Node[10];
}
public void put(int key,int val){
int index = key % arr.length;
Node cur = arr[index];
while (cur!=null){
if(cur.key == key){
cur.val = val;
return;
}
cur = cur.next;
}
//头插
Node node = new Node(key,val);
node.next = arr[index];
arr[index] = node;
usedSize++;
if(calcLoad_Fac() >= LOAD_FACTOR){
resize();
}
}
//每个元素重新进行哈希运算，位置可能不一样
private void resize() {
Node[] newarr = new Node[2*arr.length];
for (int i = 0;i < arr.length;i++){
Node cur = arr[i];
while (cur != null){
Node curNext = cur.next;
int index = cur.key % newarr.length;
cur.next = newarr[index];
newarr[index] = cur;
cur = cur.next;
}
}
arr = newarr;
}
/*计算负载因子*/
private double calcLoad_Fac(){
return usedSize*0.1 / arr.length;
}
public int get(int key){
int index = key % arr.length;
Node cur = arr[index];
while (cur != null){
if(cur.key == key){
return cur.val;
}
cur = cur.next;
}
return -1;
}
}
但是上述代码只能实现 int 类型的数据存取，如果对象变成了String,或者一个Student（）类呢？
这时我们就需要泛型了。
public class HashBuck2
static class Node
public K key;
public V val;
public Node
public Node(K key, V val) {
this.key = key;
this.val = val;
}
}
public Node
public int usedSize;
public void put(K key,V val){
int hash = key.hashCode();
int index = hash % arr.length;
Node
while (cur!=null){
if(cur.key.equals(key)){
cur.val = val;
return;
}
cur = cur.next;
}
//头插
Node
node.next = arr[index];
arr[index] = node;
usedSize++;
}
public V get(K key){
int hash = key.hashCode();
int index = hash % arr.length;
Node
while (cur != null){
if(cur.key.equals(key)){
return cur.val;
}
cur = cur.next;
}
return null;
}
}
这时我们可以准备一个Student()类进行测试。
class Student{
String id;
public Student(String id) {
this.id = id;
}
}
在使用泛型时，想要student1和student2表示同一个对象，一定要重写hashCode()和equals()方法！
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Student student = (Student) o;
return Objects.equals(id, student.id);
}
@Override
public int hashCode() {
return Objects.hash(id);
}
public static void main(String[] args) {
Student student1 = new Student("1");
System.out.println(student1.hashCode());
Student student2 = new Student("1");
System.out.println(student2.hashCode());
HashBuck2
hashBuck2.put(student1,"zhangsan");
String val = hashBuck2.get(student2);
System.out.println(val);
}
因为重写了hashCode()和equals()方法，student1和student2的hashCode值相同，所以最终打印的val为zhangsan。
四 面试高频问题
4.1 hashCode一样时，equals()的结果一定一样吗？
不一定，因为hashcode一样，只能证明在数组中位置一样，链表中具体的位置并不确定。
4.2 equals()一样时，hashCode的结果一定一样吗？
一定，对于两个对象，如果它们的equals()方法返回true，那么它们的hashCode()方法应该返回相同的值。但是，如果两个对象的equals()方法返回false，它们的hashCode()方法返回相同的值的情况也是有可能发生的。
精彩链接
您阅读本篇文章共花了：
发表评论