哈希算法专栏一《哈希表基础理论》

哈希表概述

哈希表的定义

哈希表是根据关键码的值而直接进行访问的数据结构。

这么这官方的解释可能有点懵，其实直白来讲其实数组就是一张哈希表。

哈希表中关键码就是数组的索引下标，然后通过下标直接访问数组中的元素，如下图所示：

哈希表的核心思想是使用哈希函数将键转换为数组索引。哈希函数可以将任意大小的输入映射为固定大小的输出，通常会将键转换为一个整数值。这个整数值作为数组的索引，相应的值就存储在该索引位置上。

哈希表的作用

快速查找：哈希表通过使用哈希函数将键映射到特定的位置，从而实现了快速的查找操作。通过计算哈希值并在相应位置上查找，可以在平均情况下以常量时间复杂度 O(1) 完成查找操作。

例如要查询一个名字是否在这所学校里。要枚举的话时间复杂度是O(n)，但如果使用哈希表的话， 只需要O(1)就可以做到。我们只需要初始化把这所学校里学生的名字都存在哈希表里，在查询的时候通过索引直接就可以知道这位同学在不在这所学校里了。

插入和删除：哈希表也能够以常量时间复杂度 O(1) 完成插入和删除操作。通过计算键的哈希值并将键值对存储在相应位置，可以高效地插入和删除元素。

字典存储：哈希表常被用作字典（Dictionary）来存储键值对。它可以根据键快速找到对应的值，类似于字典中通过单词找到对应的含义。

缓存存储：哈希表适用于缓存存储，可以通过将数据的哈希值作为索引，将数据存储在内存中快速访问。这样可以减少对磁盘或网络等慢速存储介质的访问，提高数据的读取速度。

将学生姓名映射到哈希表上就涉及到了hash function ，也就是哈希函数。

下面来介绍哈希函数：

哈希函数

哈希函数，把学生的姓名直接映射为哈希表上的索引，然后就可以通过查询索引下标快速知道这位同学是否在这所学校里了。

哈希函数如下图所示，通过hashCode把名字转化为数值，一般hashcode是通过特定编码方式，可以将其他数据格式转化为不同的数值，这样就把学生名字映射为哈希表上的索引数字了。

如果hashCode得到的数值大于 哈希表的大小了，也就是大于tableSize了，怎么办呢？

此时为了保证映射出来的索引数值都落在哈希表上，我们会在再次对数值做一个取模的操作，这样我们就保证了学生姓名一定可以映射到哈希表上了。

此时问题又来了，哈希表我们刚刚说过，就是一个数组。

如果学生的数量大于哈希表的大小怎么办，此时就算哈希函数计算的再均匀，也避免不了会有几位学生的名字同时映射到哈希表 同一个索引下标的位置。

接下来哈希碰撞登场

哈希碰撞

什么是哈希碰撞

如图所示，小李和小王都映射到了索引下标 1 的位置，这一现象叫做哈希碰撞。

一般哈希碰撞有两种解决方法， 拉链法和线性探测法。

解决方案

拉链法

拉链法就是在数组冲突的索引处挂一个链表，发生冲突的元素都被存储在链表中。 这样我们就可以通过索引找到小李和小王了。

（数据规模是dataSize， 哈希表的大小为tableSize）

其实拉链法就是要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。

线性探测法

使用线性探测法，一定要保证tableSize大于dataSize。 我们需要依靠哈希表中的空位来解决碰撞问题。

例如冲突的位置，放了小李，那么就向下找一个空位放置小王的信息。所以要求tableSize一定要大于dataSize ，要不然哈希表上就没有空置的位置来存放 冲突的数据了。如图所示：

其实关于哈希碰撞还有非常多的细节，感兴趣的读者可以再好好研究一下，我这篇博客主要提供刷哈希表的题目的基础知识的补充，这里我就不再赘述了

常见的哈希结构

当我们想使用哈希法来解决问题的时候，我们一般会选择如下三种数据结构。

• 数组
• set （集合）
• map(映射)

下面我们来具体看一下java中实现了哈希结构的一些容器

set

HashSet

1.HashSet接口方法（也就是Collection的接口方法）

因为 Set接口是Collection的子接口，set接口没有提供额外的方法

1.添加
add(Object obj)
addAll(Collection coll)
2.获取有效元素的个数
int size()
3.清空集合
void clear()
4.是否是空集合
boolean isEmpty()
5.是否包含某个元素
boolean contains(Object obj)：是通过元素的equals方法来判断是否是同一个对象
boolean containsAll(Collection c)：也是调用元素的equals方法来比较的。拿两个集合的元素挨个比较。
6.删除
boolean remove(Object obj)：通过元素的equals方法判断是否是要删除的那个元素，只会删除找到的第一个元素 boolean removeAll(Object coll)：去当前集合的差集
7.取两个集合的交集
boolean retainAll(Collection c)：把交集的结果存在当前集合中，不影响c
8.集合是否相等
boolean equals(Object obj)
9.转成对象数组
Object[] toArray()
10.获取集合对象的哈希值
hash.Code()
11.遍历
iterator()：返回迭代器对象，用于集合遍历

2.HashSet特点

1.HashSet 是 Set 接口的典型实现，大多数时候使用 Set 集合时都使用这个实现类
2.HashSet 按 Hash 算法来存储集合中的元素，因此具有很好的存取、查找、删除性能。
3.HashSet具有以下特点：
（1）不能保证元素的排列顺序；
（2）HashSet不是线程安全的
（3）集合元素可以是null
4.HashSet 集合判断两个元素相等的标准： 两个对象通过 hashCode() 方法比较相等，并且两个对象的 equals() 方法返回值也相等。

3.向HashSet中添加元素的过程（不影响调用，了解了会更清楚原理）

1. 当向 HashSet 集合中存入一个元素时，HashSet 会调用该对象的 hashCode() 方法来得到该对象的 hashCode 值，然后根据 hashCode 值，通过某种散列函数决定该对象在 HashSet 底层数组中的存储位置。（这个散列函数会与底层数组的长度相计算得到在数组中的下标，并且这种散列函数计算还尽可能保证能均匀存储元素，越是散列分布，该散列函数设计的越好）
2. 如果两个元素的hashCode()值相等，会再继续调用equals方法，如果equals方法结果为true，添加失败；如果为false，那么会保存该元素，但是该数组的位置已经有元素了，那么会通过链表的方式继续链接。如果两个元素的 equals() 方法返回 true，但它们的 hashCode() 返回值不相等，hashSet 将会把它们存储在不同的位置，但依然可以添加成功

4.HashSet的子类——LinkedHashSet

区别：它同时使用双向链表维护元素的次序，这使得元素看起来是以插入
顺序保存的。这主要体现在迭代的遍历过程中，普通的HashSet遍历时元素的顺序和插入顺序没有关系，而LinkedHashSet可以保证遍历到的顺序和插入顺序相同。

4.1 程序验证HashSet与LinkedHashSet的无序与有序

验证代码 1：

package com.kjz.test;
import java.util.*;

public class TestHash {
? ? public static void main(String[] args) {
? ? ? ? Set<Integer> normalHash = new?
HashSet<>();
? ? ? ? Set<Integer> linkedHash = new?
LinkedHashSet<>();
? ? ? ? for (int i = 0; i < 20; i++) {
? ? ? ? ? ? normalHash.add(i);
? ? ? ? ? ? linkedHash.add(i);
? ? ? ? }
? ? ? ? System.out.println(normalHash);
? ? ? ? System.out.println(linkedHash);
? ? }
}

结果：

这么看，两者似乎没有区别 但是换个输入看看

package com.kjz.test;
import java.util.*;

public class TestHash {
? ? public static void main(String[] args) {
? ? ? ? Set<Integer> normalHash = new?
HashSet<>();
? ? ? ? Set<Integer> linkedHash = new?
LinkedHashSet<>();
? ??
? ? ? ? normalHash.add(30);
? ? ? ? normalHash.add(10);
? ? ? ? normalHash.add(50);
? ? ? ? normalHash.add(20);

? ? ? ? linkedHash.add(30);
? ? ? ? linkedHash.add(10);
? ? ? ? linkedHash.add(50);
? ? ? ? linkedHash.add(20);

? ? ? ? System.out.println(normalHash);
? ? ? ? System.out.println(linkedHash);
? ? }
}

结果：

这么看HashSet确实是无序的，而LinkedHashSet是有序的
那么第一次测试为什么两者的结果为什么是一样的呢？

仔细回想，不难发现hashset底层使用hashmap来实现的，set的元素存放在map的key上面。
对于hashmap来讲，它的主体是一个Entry数组，Entry又是一个链表，因此hashmap的存储过程如下：
1.计算key的hash值
2.把得到的hash值作为数据下标去存储到Entry数组。在这里可能出现不一样的key的得到的hash值相等，如果相等，就把新的value存到当前下标下保存的Entry里面（Entry是链表）

由此可见，hashset实际上存储元素的时候进行了获取hash的操作，而对于第一次测试用例中的遍历0-19来说，他们的hash值就是自身，所以根据这个hash值得到数组的下标存储元素后，表现出来就是有序的。
也就是恰好输入顺序的哈希值就是有序的。

map

HashMap

1.HashMap接口方法

1.添加 、 删除、修改操作 ：
Object put(Object key,Object value)：将指定key-value添加到(或修改)当前map对象中
void putAll(Map m):将m中的所有key-value对存放到当前map中
Object remove(Object key)：移除指定key的key-value对，并返回value
void clear()：清空当前map中的所有数据
2.元素 查询的操作：
Object get(Object key)：获取指定key对应的value
boolean containsKey(Object key)：是否包含指定的key
boolean containsValue(Object value)：是否包含指定的value
int size()：返回map中key-value对的个数
boolean isEmpty()：判断当前map是否为空
boolean equals(Object obj)：判断当前map和参数对象obj是否相等
3.元 视图操作的方法：
Set keySet()：返回所有key构成的Set集合
Collection values()：返回所有value构成的Collection集合
Set entrySet()：返回所有key-value对构成的Set集合

2.HashMap特点

1. HashMap是 Map 接口 使用频率最高的实现类。
2. 允许使用null键和null值，与HashSet一样，不保证映射的顺序。
3. HashMap 判断两个 key 相等的标准是：两个 key 通过 equals() 方法返回 true，hashCode 值也相等
4. HashMap 判断两个 value 相等的标准是：两个 value 通过 equals() 方法返回 true
5. 一个key-value构成一个entry，所有的entry构成的集合是Set:无序的、不可重复的

3.向HashMap添加元素的过程

向HashMap中添加entry1(key，value)，需要首先计算entry1中key的哈希值(根据key所在类的hashCode()计算得到)，此哈希值经过处理以后，得到在底层Entry[]数组中要存储的位置i。如果位置i上没有元素，则entry1直接添加成功。如果位置i上已经存在entry2(或还有链表存在的entry3，entry4)，则需要通过循环的方法，依次比较entry1中key和其他的entry。如果彼此hash值不同，则直接添加成功。如果hash值不同，继续比较二者是否equals。如果返回值为true，则使用entry1的value去替换equals为true的entry的value。如果遍历一遍以后，发现所有的equals返回都为false,则entry1仍可添加成功。entry1指向原有的entry元素

4.HashMap的子类——LinkedHashMap

类似于LinkedHashSet与HashSet的关系，LinkedHashMap 是 HashMap 的子类，在HashMap存储结构的基础上，使用了一对双向链表来记录添加，元素的顺序，LinkedHashMap 可以维护 Map 的迭代顺序：迭代顺序与 Key-Value 对的插入顺序一致

table

HashTable

因为这个现在不怎么常用，并且大部分原理和方法都和HashMap相同，这里只做简单介绍

1. Hashtable是个古老的 Map 实现类，JDK1.0就提供了。不同于HashMap，
2. Hashtable是线程安全的。
3. Hashtable实现原理和HashMap相同，功能相同。底层都使用哈希表结构，查询速度快，很多情况下可以互用。
4. 与HashMap不同，Hashtable 不允许使用 null 作为 key 和 value
5. 与HashMap一样，Hashtable 也不能保证其中 Key-Value 对的顺序
6. Hashtable判断两个key相等、两个value相等的标准，与HashMap一致。
   ?

区别总结：HashSet、HashMap与HashTable