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

news/2024/9/24 23:35:16/

话题引入：

给你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 常见的开放寻址法：
  1. 线性探测法（Linear Probing）
    • 当发生冲突时，从冲突的地址开始，线性地向后探测，直到找到第一个空闲的地址。
    • 公式：𝐻(𝑘,𝑖)=(ℎ(𝑘)+𝑖)mod  𝑚H(k,i)=(h(k)+i)modm
    • 其中，ℎ(𝑘)h(k) 是原始哈希函数，𝑚m 是哈希表的大小，𝑖i 是探测序列中的步长，通常从1开始。
  2. 二次探测法（Quadratic Probing）
    • 与线性探测类似，但探测的步长是二次方的序列，即1, 4, 9, 16, …。
    • 公式：𝐻(𝑘,𝑖)=(ℎ(𝑘)+𝑐𝑖)mod  𝑚H(k,i)=(h(k)+c**i)modm
    • 其中，𝑐𝑖=𝑖2c**i=i2。
  3. 双哈希法（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 工作原理
  1. 哈希函数：首先使用哈希函数 ℎ(𝑘)h(k) 计算键 𝑘k 的哈希地址。
  2. 链表存储：在哈希表的对应地址处，维护一个链表，所有哈希值相同的键都将被存储在这个链表中。
  3. 插入操作：当插入一个新元素时，根据其哈希值找到对应的链表，然后在链表的末尾添加新元素。
  4. 查找操作：当查找一个元素时，根据其哈希值找到对应的链表，然后在链表中顺序查找该元素。
  5. 删除操作：当删除一个元素时，同样需要根据其哈希值找到对应的链表，然后在链表中找到该元素并删除。
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插入到哈希表的地址1的链表中。
  2. 元素4也插入到地址1的链表中，因为它与元素1冲突。
  3. 元素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不保证映射的顺序；特别是，它不保证该顺序会随着时间的推移保持不变（扩容）。

特点：

  1. 基于哈希表实现：HashMap内部通过一个哈希表来存储键值对，这使得它在查找、插入和删除操作方面具有较高的效率，平均时间复杂度为O(1)。
  2. 允许null键和null值：与Hashtable不同，HashMap允许使用null键和null值。但最多只能有一个null键，因为键是唯一的。
  3. 不保证顺序：HashMap不保证映射的顺序；特别是它不保证该顺序会随着时间的推移保持不变。
  4. 初始容量和负载因子：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来记录；跳到646Lineelse 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函数的应用场景

  1. 加密与算法>哈希算法
  • MD5 算法>哈希算法
    • 广泛用于生成数据的128位二进制哈希值（指纹）。
    • 尽管理论上存在冲突可能（因为输出空间有限），但实际应用中冲突概率极低。
    • 用途：密码存储（注意：MD5已不推荐用于安全敏感场景，因其易受碰撞攻击）。
    • 示例：md5(md5("password") + "salt") 用于密码加盐哈希。
    • 不可逆性：MD5生成的哈希值无法直接还原为原始数据。
  1. 视频重复检测
  • 方法：使用MD5算法对视频文件内容进行哈希，得到其唯一标识。
  • 优点：快速检测视频文件是否重复，只需比较哈希值。
  • 注意：大文件哈希计算可能耗时较长，且对于微小差异的视频文件可能无法区分。
  1. 相似性检测（如论文查重）
  • 指纹算法：将论文内容转化为特征向量（指纹），通常基于文本特征提取。
  • 汉明距离：用于衡量两个指纹之间的相似度，汉明距离越小表示相似度越高。
  • 应用：在学术查重系统中广泛使用，以检测论文的抄袭情况。
  1. 负载均衡（如Nginx配置）
  • 场景：在拥有多台服务器的环境中，合理分配请求以平衡负载。
  • 方法：根据请求的某些特征（如IP地址）计算哈希值，然后对服务器数量取模，决定请求发往哪台服务器。
  • 优点：简单有效，能快速实现请求的均衡分配。
  1. 分布式系统数据分库分表
  • 目的：处理大规模数据，将数据存储到多个数据库或表中以提高性能和可扩展性。
  • 方法：使用哈希函数对数据的唯一标识（如ID）进行哈希，然后对表数量取模，决定数据存储位置。
  • 示例：id % 10 用于决定将ID分配到10个表中的哪一个。
  • 扩展性：当需要增加表数量时，需重新分配数据，可能导致数据迁移和性能影响。
  1. 分布式存储表扩展问题

可以了解了解（redis cluster集群的一致性哈希）

  • 挑战：在增加新表后，需要重新计算并迁移旧数据到新结构，可能导致大量数据移动和服务中断。
  • 解决方案
    • 增量迁移：逐步迁移数据，减少一次性迁移压力。
    • 使用更灵活的算法>哈希算法：如一致性哈希，减少数据迁移量。
    • 动态扩容策略：设计能够动态调整数据分布的机制，减少手动干预。
  1. 查找算法：HashMap
  • 核心：基于哈希表的键值对存储结构，提供快速的查找、插入和删除操作。
  • 原理：通过哈希函数将键转换为数组索引，实现快速定位。
  • 冲突解决：通过链表、红黑树等方式处理哈希冲突。
  • 应用：广泛应用于缓存、数据库索引、编程语言数据结构等场景。

http://www.ppmy.cn/news/1530013.html

相关文章

深度对比：etcd、Consul、Zookeeper 和 Nacos 作为注册中心和配置中心的优势与劣势

深度对比：etcd、Consul、Zookeeper 和 Nacos 作为注册中心和配置中心的优势与劣势

在现代分布式系统和微服务架构中&#xff0c;服务注册中心 和 配置中心 是系统稳定运行的关键组成部分。服务注册中心负责服务的动态注册与发现&#xff0c;而配置中心用于集中管理配置&#xff0c;确保系统在变化的环境中保持一致性。本文将对比 etcd、Consul、Zookeeper 和 N…
阅读更多...
C++速通LeetCode中等第1题-字母异位词分组

C++速通LeetCode中等第1题-字母异位词分组

思路要点&#xff1a;对字符串排序&#xff0c;排序结果存放在map的key中&#xff0c;排序结果相同的字符串存放到map的value中 。 class Solution { public:string keys;vector<vector<string>> groupAnagrams(vector<string>& strs) {vector<vecto…
阅读更多...
力扣 2529.正整数和负整数的最大计数

力扣 2529.正整数和负整数的最大计数

文章目录 题目介绍解法 题目介绍 解法 采用红蓝染色体法&#xff0c;具体介绍参考 红蓝染色体法 通过红蓝染色体法可以找到第一个大于大于target的位置&#xff0c;使所以本题可以找第一个大于0的位置&#xff0c;即负整数的个数&#xff1b;数组长度 - 第一个大于1的位置即正…
阅读更多...
001、引用FeignClient循环依赖问题

001、引用FeignClient循环依赖问题

1.报错信息 HandlerInterceptor引用FeignClient造成循环依赖 The dependencies of some of the beans in the application context form a cycle:┌─────┐| appAuthInterceptor defined in URL [jar:file:/deployments/app.jar!/BOOT-INF/classes!/com/XX/assembler/in…
阅读更多...
Hbase日常运维

Hbase日常运维

1 Hbase日常运维 1.1 监控Hbase运行状况 1.1.1 操作系统 1.1.1.1 IO 群集网络IO&#xff0c;磁盘IO&#xff0c;HDFS IO IO越大说明文件读写操作越多。当IO突然增加时&#xff0c;有可能&#xff1a;1.compact队列较大&#xff0c;集群正在进行大量压缩操作。 2.正在执行…
阅读更多...
Datawhile 组队学习Tiny-universe Task01

Datawhile 组队学习Tiny-universe Task01

Task01&#xff1a;LLama3模型讲解 仓库链接&#xff1a;GitHub - datawhalechina/tiny-universe: 《大模型白盒子构建指南》&#xff1a;一个全手搓的Tiny-Universe 参考博客&#xff1a;LLaMA的解读与其微调(含LLaMA 2)&#xff1a;Alpaca-LoRA/Vicuna/BELLE/中文LLaMA/姜子…
阅读更多...
com.kingbase8.util.KSQLException: ERROR: permission denied for table xxx

com.kingbase8.util.KSQLException: ERROR: permission denied for table xxx

前言 在信创改造中&#xff0c;数据库替换为国产数据库是不可缺少的一部分。而可替换选项中多数选项无非是人大金仓和达梦数据库二选一。本文将介绍人大金仓在使用过程的问题以及解决办法。 问题 在使用人大金仓数据库后&#xff0c;程序运行报错 com.kingbase8.util.KSQLEx…
阅读更多...
Redis(redis基础，SpringCache,SpringDataRedis)

Redis(redis基础，SpringCache,SpringDataRedis)

文章目录 前言一、Redis基础1. Redis简介2. Redis下载与安装3. Redis服务启动与停止3 Redis数据类型4. Redis常用命令5. 扩展数据类型 二、在Java中操作Redis1. Spring Data Redis的使用1.1. 介绍1.2. 环境搭建1.3. 编写配置类&#xff0c;创建RedisTemplate对象1.4. 通过Redis…
阅读更多...
最新文章

Copyright @ 2022~2023