当前位置：首页 > article >正文

数据结构与算法-18算法专向（hash）

article 2024/9/21 10:54:39

话题引入：

给你N（1<N<10）个自然数,每个数的范围为（1~10000000000）。现在让你以最快的速度判断某一个数是否在这N个数内，不得使用已经封装好的类，该如何实现。 A[] = new int[N+1]？

散列表

散列表（Hash table），也被称为哈希表，是一种根据键（Key）而直接访问在内存存储位置的数据结构。它通过计算一个关于键值的函数（即散列函数），将所需查询的数据映射到表中一个位置来访问记录，从而加快查找速度。

1 简介

定义：散列表是一种通过键来直接访问内存存储位置的数据结构，它利用散列函数将键映射到表中一个位置，以实现快速查找。
核心组件
- 散列函数：一个用于计算散列值的函数，通常表示为hash(key)，其中key是元素的键值，hash(key)的值是经过散列函数计算得到的散列值。
- 散列表：存放记录的数组，也称为哈希表。
特性
- 确定性：如果两个散列值是不相同的（根据同一函数），那么这两个散列值的原始输入也是不相同的。
- 散列碰撞（Collision）：散列函数的输入和输出不是唯一对应关系的。如果两个散列值相同，两个输入值很可能是相同的，但也可能不同。这种情况称为散列碰撞。
- 不可逆性：一个哈希值对应无数个明文，理论上无法直接通过哈希值反推出原始输入。
- 混淆特性：输入一些数据计算出散列值后，部分改变输入值，一个具有强混淆特性的散列函数会产生一个完全不同的散列值。

2 散列冲突解决方法

2.1 开放寻址法

开放寻址法（Open Addressing）：通过探查序列来寻找空闲位置。

2.1.1 常见的开放寻址法：

线性探测法（Linear Probing）
- 当发生冲突时，从冲突的地址开始，线性地向后探测，直到找到第一个空闲的地址。
- 公式：𝐻(𝑘,𝑖)=(ℎ(𝑘)+𝑖)mod 𝑚H(k,i)=(h(k)+i)modm
- 其中，ℎ(𝑘)h(k) 是原始哈希函数，𝑚m 是哈希表的大小，𝑖i 是探测序列中的步长，通常从1开始。
二次探测法（Quadratic Probing）
- 与线性探测类似，但探测的步长是二次方的序列，即1, 4, 9, 16, …。
- 公式：𝐻(𝑘,𝑖)=(ℎ(𝑘)+𝑐𝑖)mod 𝑚H(k,i)=(h(k)+c**i)modm
- 其中，𝑐𝑖=𝑖2c**i=i2。
双哈希法（Double Hashing）
- 使用两个哈希函数，当发生冲突时，使用第二个哈希函数计算下一个探测地址。
- 公式：𝐻(𝑘,𝑖)=(ℎ1(𝑘)+𝑖⋅ℎ2(𝑘))mod 𝑚H(k,i)=(h1(k)+i⋅h2(k))modm
- 其中，ℎ1(𝑘)h1(k) 和 ℎ2(𝑘)h2(k) 是两个不同的哈希函数。

2.2.2 优缺点

优点

空间利用率高：不需要额外的存储空间来存储冲突的元素。
简单易实现：算法实现相对简单。

缺点：

聚集问题：特别是线性探测法，容易形成聚集，影响查找效率。
删除操作复杂：删除元素时需要标记删除，而不是真正删除，以避免影响探测序列。

2.2.3 示例说明

线性探测法的工作原理
- 线性探测法的基本思想是，当一个元素通过哈希函数计算得到的地址已被占用时，它会从这个地址开始，线性地向后（或向前，这取决于实现方式）探测，直到找到一个空闲的地址。探测的步长通常是1。
线性探测法的步骤
- 计算哈希地址：使用哈希函数 ℎ(𝑘)h(k) 计算键 𝑘k 的哈希地址。
- 探测冲突：如果该地址已被占用，就从该地址开始，线性地向后探测。
- 找到空闲地址：探测到第一个空闲地址，将元素插入该地址。
- 插入元素：将元素插入到找到的空闲地址中。
示例
- 假设我们有一个哈希表大小为6，哈希函数定义为 ℎ(𝑘)=𝑘 mod 6 ，现在我们要插入以下元素：
  - 元素1：ℎ(1)= 1 mod 6=1 h(1)=1mod 6=1
  - 元素2：ℎ(2)=2 mod 6=2 h(2)=2mod 6=2
  - 元素3：ℎ(3)=3 mod 6=3 h(3)=3mod 6=3
  - 元素4：ℎ(4)=4 mod 6=4 h(4)=4mod 6=4
  - 元素6：ℎ(7)=7 mod 6=1 h(6)=6mod 6=1（与元素1冲突）
- 下面是插入元素6的步骤：
  - 计算元素7的哈希地址：ℎ(7)=1。
  - 地址1已被元素1占用，发生冲突。
  - 从地址1开始线性探测，往下寻址【 2（不为空） -> 3（不为空） -> 4（不为空） -> 5（空）】
  - 将元素7插入到地址5。
- 此时，哈希表的状态如下：
  - 地址0：空闲
  - 地址1：元素1
  - 地址2：元素2
  - 地址3：元素3
  - 地址4：元素4
  - 地址5：元素6

2.2 链表法

链表法（Chaining）：在散列表中，每个位置对应一条链表，所有散列值相同的元素都放到相同位置对应的链表中。这种方法更加常用且简单。

2.2.1 工作原理

哈希函数：首先使用哈希函数 ℎ(𝑘)h(k) 计算键 𝑘k 的哈希地址。
链表存储：在哈希表的对应地址处，维护一个链表，所有哈希值相同的键都将被存储在这个链表中。
插入操作：当插入一个新元素时，根据其哈希值找到对应的链表，然后在链表的末尾添加新元素。
查找操作：当查找一个元素时，根据其哈希值找到对应的链表，然后在链表中顺序查找该元素。
删除操作：当删除一个元素时，同样需要根据其哈希值找到对应的链表，然后在链表中找到该元素并删除。

2.2.2 优缺点

优点

冲突易于处理：冲突的元素可以简单地存储在同一哈希值的链表中。
动态扩展：链表的长度可以根据需要动态变化，适应不同数量的冲突。
删除方便：删除元素时不需要考虑其他元素的探测或重新散列。

缺点

空间开销：每个槽都需要额外的空间来存储链表的节点。
性能问题：如果哈希表的负载因子（即元素数量与槽数量的比值）过高，链表可能会变得很长，导致查找效率下降。

2.2.3 示例说明

假设我们有一个哈希表大小为3，哈希函数定义为 ℎ(𝑘)=𝑘mod 3h(k)=kmod3，现在我们要插入以下元素：

元素1：ℎ(1)=1mod 3=1h(1)=1mod3=1
元素4：ℎ(4)=4mod 3=1h(4)=4mod3=1（与元素1冲突）
元素7：ℎ(7)=7mod 3=1h(7)=7mod3=1（与元素1和4冲突）

插入过程如下：

元素1插入到哈希表的地址1的链表中。
元素4也插入到地址1的链表中，因为它与元素1冲突。
元素7同样插入到地址1的链表中。

此时，哈希表的状态如下：

地址0：空闲
地址1：元素1 -> 元素4 -> 元素7
地址2：空闲

3 散列表&hashMap

散列表与hashMap

HashMap 是 Java 中的一个非常重要的集合类，它基于散列表（Hash Table）实现，用于存储键值对（key-value pairs）。散列表是一种使用哈希函数组织数据，以支持快速插入和搜索的数据结构。在 HashMap 中，散列表的使用是其高效性的关键所在。

3.1 什么是hashmap

Java中的HashMap是Java集合框架中的一个非常重要的类，它实现了Map接口。HashMap存储键值对（key-value pairs），其中每个键都映射到最多一个值。一个键可以映射到最多一个值。HashMap不保证映射的顺序；特别是，它不保证该顺序会随着时间的推移保持不变（扩容）。

特点：

基于哈希表实现：HashMap内部通过一个哈希表来存储键值对，这使得它在查找、插入和删除操作方面具有较高的效率，平均时间复杂度为O(1)。
允许null键和null值：与Hashtable不同，HashMap允许使用null键和null值。但最多只能有一个null键，因为键是唯一的。
不保证顺序：HashMap不保证映射的顺序；特别是它不保证该顺序会随着时间的推移保持不变。
初始容量和负载因子：HashMap的默认初始容量是16，默认负载因子是0.75。当HashMap中的元素数量超过容量乘以负载因子时，哈希表会进行扩容，即创建一个新的哈希表，并将原哈希表中的所有元素重新哈希后存储到新表中。扩容操作是代价较高的。

hashmap使用示例

import java.util.HashMap;  
import java.util.Map;  
  
public class HashMapExample {  
    public static void main(String[] args) {  
        // 创建一个HashMap实例  
        Map<String, Integer> ageMap = new HashMap<>();  
  
        // 向HashMap中添加键值对  
        ageMap.put("Alice", 30);  
        ageMap.put("Bob", 25);  
        ageMap.put("Charlie", 35);  
  
        // 访问HashMap中的值  
        System.out.println("Alice's age: " + ageMap.get("Alice")); // 输出: Alice's age: 30  
  
        // 检查HashMap中是否包含某个键  
        if (ageMap.containsKey("Bob")) {  
            System.out.println("Bob is in the map.");  
        }  
  
        // 检查HashMap中是否包含某个值（注意，这可能会返回true，因为可能有多个键映射到相同的值）  
        if (ageMap.containsValue(30)) {  
            System.out.println("There is someone who is 30 years old.");  
        }  
  
        // 修改HashMap中已存在的键对应的值  
        ageMap.put("Alice", 31); // 将Alice的年龄改为31  
  
        // 移除HashMap中的键值对  
        ageMap.remove("Charlie");  
  
        // 遍历HashMap（使用entrySet()遍历键和值）  
        for (Map.Entry<String, Integer> entry : ageMap.entrySet()) {  
            System.out.println(entry.getKey() + ": " + entry.getValue());  
        }  
  
        // 或者，如果你只对键或值感兴趣，可以使用keySet()或values()  
        // 遍历HashMap中的所有键  
        for (String key : ageMap.keySet()) {  
            System.out.println(key);  
        }  
  
        // 遍历HashMap中的所有值  
        for (Integer value : ageMap.values()) {  
            System.out.println(value);  
        }  
  
        // 使用Java 8的forEach()方法和Lambda表达式遍历  
        ageMap.forEach((key, value) -> System.out.println(key + ": " + value));  
    }  
}

3.2 hashmap数据结构

jdk1.8之前（数组+链表）

在JDK 1.8之前，HashMap采用了数组+链表的方式去保存数据。通过计算Hash值将元素放到数组上的指定位置上。如果出现了Hash相同的情况（即哈希冲突），就会形成单向的链表，并且链表使用头插法，将最新插入的元素放到链表的头结点位置。

jdk1.8以后（数组+链表+红黑树）

从JDK 1.8开始，HashMap的数据结构进行了优化，引入了红黑树来解决链表过长导致的查找效率下降问题。当链表的长度超过8并且数组长度大于64时，为了避免查找搜索性能下降，该链表会转换成一个红黑树。红黑树是一种自平衡的二叉搜索树，它的插入、删除和查找的时间复杂度都是O(log n)，相比于链表的线性时间复杂度O(n)，可以大大提高操作的效率。
在这里插入图片描述

3.3 数据存储原理

根据key计算hash值。
判断数组是否存在，如果不存在则用resize方法创建默认长度为16的数组。
确定要存入的Node在数组中的位置，根据hash值与数组最大索引进行按位与运算得到索引位置。
判断该位置是否有元素，如果没有则直接创建一个Node存入；如果有元素，则进一步判断key是否相同，如果相同则覆盖，并将原来的值返回；如果key不相同，则在原Node基础上添加新的Node，并判断该位置是链表还是红黑树，进行相应的插入操作。

在这里插入图片描述

3.4 最后读读源码

备注很多认真看

3.4.1 get

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;//先计算hashcode
}

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && //  数组查找！！！！！！！
            ((k = first.key) == key || (key != null && key.equals(k)))) // hash值相同 且 key相等
            return first;//返回查找的数据
        if ((e = first.next) != null) {  //桶中不止一个节点
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);//红黑查找!!!!!
            do {//链表查找!!!!!
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;//否则返回null
}

3.4.2 put

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);//调用Map的putVal方法
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {//onlyIfAbsent：true不更改现有值；evict：false表示table为创建状态
    Node<K,V>[] tab; Node<K,V> p; int n, i;//临时变量
    if ((tab = table) == null || (n = tab.length) == 0)//数组是否null或者==0，第1次put为空
        n = (tab = resize()).length;//初始化数组(or扩容)！！！！！！！！！！！！！
    if ((p = tab[i = (n - 1) & hash]) == null)//寻址：(n - 1) & hash重要，16-1 按位与hash，为null表示没有值
        tab[i] = newNode(hash, key, value, null);//等空，直接插入
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&//key相等！！！！！！！！
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;//将第一个元素赋值给e，用e来记录；跳到646Line
        else if (p instanceof TreeNode)//判断是否红黑树！！！！！！！！！！！！！！！！
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else { //生成链表(操作链表),开始遍历链表
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {//p.next为空表明处于链表的尾部，1、生成链表  2、已经是链表！！！！  存储位置相等
                    p.next = newNode(hash, key, value, null);// 直接创建
                    if (binCount >= TREEIFY_THRESHOLD - 1) //链表长度如果>8转红黑树（or 扩容），-1是因为binCount从0开始
                        treeifyBin(tab, hash);//树化；还需要判断是否大于64，否则扩容
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))//对链表节点中数据进行覆盖判断
                    break;// 如果key相同,break跳出for循环,执行后面的逻辑
                p = e;
            }
        }
        if (e != null) { // key已经存在
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;// 用新的value值去覆盖老的value值
            afterNodeAccess(e);
            return oldValue;// 返回覆盖前的value值，put的返回值
        }
    }
    ++modCount;//用来记录HashMap的修改次数
    if (++size > threshold)//扩容
        resize();//如果size大于threshold,就需要进行扩容
    afterNodeInsertion(evict);
    return null;
}

4 hash函数的应用场景

加密与哈希算法

MD5 哈希算法
- 广泛用于生成数据的128位二进制哈希值（指纹）。
- 尽管理论上存在冲突可能（因为输出空间有限），但实际应用中冲突概率极低。
- 用途：密码存储（注意：MD5已不推荐用于安全敏感场景，因其易受碰撞攻击）。
- 示例：md5(md5("password") + "salt") 用于密码加盐哈希。
- 不可逆性：MD5生成的哈希值无法直接还原为原始数据。