【愚公系列】2023年12月 数据结构(七)-哈希表
🏆 作者简介，愚公搬代码
🏆《头衔》：华为云特约编辑，华为云云享专家，华为开发者专家，华为产品云测专家，CSDN博客专家，阿里云专家博主，腾讯云优秀博主，掘金优秀博主，51CTO博客专家等。
🏆《近期荣誉》：2022年CSDN博客之星TOP2，2022年华为云十佳博主等。
🏆《博客内容》：.NET、Java、Python、Go、Node、前端、IOS、Android、鸿蒙、Linux、物联网、网络安全、大数据、人工智能、U3D游戏、小程序等相关领域知识。
🏆🎉欢迎 👍点赞✍评论⭐收藏
🚀前言
数据结构是计算机科学中的一个重要概念，它描述了数据之间的组织方式和关系，以及对这些数据的访问和操作。常见的数据结构有：数组、链表、栈、队列、哈希表、树、堆和图。
-
数组（Array）：是一种线性数据结构，它将一组具有相同类型的数据元素存储在一起，并为每个元素分配一个唯一的索引。数组的特点是具有随机访问的能力。
-
链表（Linked List）：也是一种线性数据结构，它由一系列的节点组成，每个节点包含数据和指向下一个节点的引用。链表的特点是可以动态地插入或删除节点，但访问某个节点时需要从头开始遍历。
-
栈（Stack）：是一种后进先出（LIFO）的数据结构，它只能在栈顶进行插入和删除操作。栈通常用于实现递归算法、表达式求值和内存管理等场景。
-
队列（Queue）：是一种先进先出（FIFO）的数据结构，它可以在队尾插入元素，在队头删除元素。队列通常用于数据的缓存、消息队列和网络通信等场景。
-
哈希表（Hash Table）：也称为散列表，它是一种根据关键字直接访问数据的数据结构。哈希表通常由数组和散列函数组成，可以在常数时间内进行插入、删除和查找操作。
-
树（Tree）：是一种非线性数据结构，它由一系列的节点组成，每个节点可以有若干个子节点。树的特点是可以动态地插入或删除节点，常见的树结构包括二叉树、平衡树和搜索树等。
-
堆（Heap）：是一种特殊的树结构，它通常用于实现优先队列和堆排序等算法。堆分为最大堆和最小堆，最大堆的每个节点的值都大于等于其子节点的值，最小堆则相反。
-
图（Graph）：是一种由节点和边组成的非线性数据结构，它可以用来表示各种实体之间的关系，如社交网络、路线图和电路图等。图的遍历和最短路径算法是常见的图算法。
🚀一、哈希表
🔎1.基本思想
哈希表的基本思想是根据键值直接访问数据，而不是通过遍历整个数据结构来获取数据。它通过将键映射到索引来快速定位数据，这个映射函数就是哈希函数（也称为散列函数）。
具体地，哈希表中的每个元素都有一个唯一的键值，该键值通过哈希函数映射到一个数组的索引位置上。在查询、插入、删除数据时，只需通过哈希函数计算出对应的索引位置，然后在该位置直接访问数据。由于哈希函数是固定的，对于相同的键值，每次计算得到的索引位置都是一样的。因此，对于大量数据的查询、插入、删除操作而言，哈希表通常比线性数据结构具有更高的效率。
当然，哈希表也可能存在碰撞（即不同的键值被哈希到了同一个索引位置上），通常采用开放地址法或者链式法来解决碰撞问题。
🔎2.哈希表常用操作
🦋2.1 自定义哈希表
/* 初始化哈希表 */
Dictionary<int, String> map = new ();
/* 添加操作 */
// 在哈希表中添加键值对 (key, value)
map.Add(12836, " 小哈");
map.Add(15937, " 小啰");
map.Add(16750, " 小算");
map.Add(13276, " 小法");
map.Add(10583, " 小鸭");
/* 查询操作 */
// 向哈希表输入键 key ，得到值 value
String name = map[15937];
/* 删除操作 */
// 在哈希表中删除键值对 (key, value)
map.Remove(10583);
遍历哈希表
/* 遍历哈希表 */
// 遍历键值对 Key->Value
foreach (var kv in map) {
Console.WriteLine(kv.Key + " -> " + kv.Value);
}
// 单独遍历键 key
foreach (int key in map.Keys) {
Console.WriteLine(key);
}
// 单独遍历值 value
foreach (String val in map.Values) {
Console.WriteLine(val);
}
🦋2.2 内置哈希表
C# 中哈希表（Hashtable）在进行常用的操作时，以下是一些常见的操作：
- 添加元素：使用 Add 或者 [] 操作符添加元素，例如：
Hashtable hashtable = new Hashtable();
hashtable.Add("key", "value");
hashtable["key"] = "value";
- 移除元素：使用 Remove 方法移除元素，例如：
hashtable.Remove("key");
- 查找元素：使用 ContainsKey 判断键是否存在，使用 ContainsValue 判断值是否存在，例如：
bool containsKey = hashtable.ContainsKey("key");
bool containsValue = hashtable.ContainsValue("value");
- 获取元素：使用 [] 操作符或者 TryGetValue 获取元素，例如：
string value = (string)hashtable["key"];
string value;
if (hashtable.TryGetValue("key", out value))
{
// ...
}
- 遍历元素：使用 foreach 遍历元素，例如：
foreach (DictionaryEntry entry in hashtable)
{
object key = entry.Key;
object value = entry.Value;
}
- 获取键集合或值集合：使用 Keys 或者 Values 获取键集合或值集合，例如：
ICollection keys = hashtable.Keys;
ICollection values = hashtable.Values;
🔎3.哈希表的实现
/* 键值对 int->string */
class Pair {
public int key;
public string val;
public Pair(int key, string val) {
this.key = key;
this.val = val;
}
}
/* 基于数组简易实现的哈希表 */
class ArrayHashMap {
private List<Pair?> buckets;
public ArrayHashMap() {
// 初始化数组，包含 100 个桶
buckets = new();
for (int i = 0; i < 100; i++) {
buckets.Add(null);
}
}
/* 哈希函数 */
private int hashFunc(int key) {
int index = key % 100;
return index;
}
/* 查询操作 */
public string? get(int key) {
int index = hashFunc(key);
Pair? pair = buckets[index];
if (pair == null) return null;
return pair.val;
}
/* 添加操作 */
public void put(int key, string val) {
Pair pair = new Pair(key, val);
int index = hashFunc(key);
buckets[index] = pair;
}
/* 删除操作 */
public void remove(int key) {
int index = hashFunc(key);
// 置为 null ，代表删除
buckets[index] = null;
}
/* 获取所有键值对 */
public List<Pair> pairSet() {
List<Pair> pairSet = new();
foreach (Pair? pair in buckets) {
if (pair != null)
pairSet.Add(pair);
}
return pairSet;
}
/* 获取所有键 */
public List<int> keySet() {
List<int> keySet = new();
foreach (Pair? pair in buckets) {
if (pair != null)
keySet.Add(pair.key);
}
return keySet;
}
/* 获取所有值 */
public List<string> valueSet() {
List<string> valueSet = new();
foreach (Pair? pair in buckets) {
if (pair != null)
valueSet.Add(pair.val);
}
return valueSet;
}
/* 打印哈希表 */
public void print() {
foreach (Pair kv in pairSet()) {
Console.WriteLine(kv.key + " -> " + kv.val);
}
}
}
public class array_hash_map {
[Test]
public void Test() {
/* 初始化哈希表 */
ArrayHashMap map = new ArrayHashMap();
/* 添加操作 */
// 在哈希表中添加键值对 (key, value)
map.put(12836, "小哈");
map.put(15937, "小啰");
map.put(16750, "小算");
map.put(13276, "小法");
map.put(10583, "小鸭");
Console.WriteLine("\n添加完成后，哈希表为\nKey -> Value");
map.print();
/* 查询操作 */
// 向哈希表输入键 key ，得到值 value
string? name = map.get(15937);
Console.WriteLine("\n输入学号 15937 ，查询到姓名 " + name);
/* 删除操作 */
// 在哈希表中删除键值对 (key, value)
map.remove(10583);
Console.WriteLine("\n删除 10583 后，哈希表为\nKey -> Value");
map.print();
/* 遍历哈希表 */
Console.WriteLine("\n遍历键值对 Key->Value");
foreach (Pair kv in map.pairSet()) {
Console.WriteLine(kv.key + " -> " + kv.val);
}
Console.WriteLine("\n单独遍历键 Key");
foreach (int key in map.keySet()) {
Console.WriteLine(key);
}
Console.WriteLine("\n单独遍历值 Value");
foreach (string val in map.valueSet()) {
Console.WriteLine(val);
}
}
}
🔎4.哈希冲突与扩容
哈希冲突是指在哈希表中两个或多个不同的键值映射到了同一个哈希桶的情况。当哈希冲突发生时，会导致哈希表的性能下降，因为需要额外的时间来解决冲突。
扩容是为了减少哈希冲突的发生，当哈希表中的元素数量超过了哈希表的负载因子阈值时，会触发扩容机制。扩容的过程是将哈希表的大小增加一倍，并且重新计算所有元素的哈希值，将它们分配到新的哈希桶中。扩容后，哈希表中的元素会更加稀疏，这样每个哈希桶中存储的元素数量就会减少，从而减少哈希冲突的发生，提高哈希表的性能。但扩容也会消耗额外的空间和时间。
🦋4.1 哈希冲突
哈希冲突的解决方法主要有以下几种：
-
链地址法：将哈希冲突的键值对存储在同一个哈希桶中的一个链表或者其他数据结构中，即将所有哈希值相同的元素都放在同一个桶中，通过链表将它们串联起来，形成一个链表结构。
-
开放寻址法：在发生哈希冲突时，尝试在其他哈希桶中寻找空闲哈希桶，直到找到一个合适的位置，存储相应的键值对。
-
建立公共溢出区：将所有发生哈希冲突的键值对都放到一个公共溢出区中，需要查找一个键值对时，先在哈希表中进行查找，如果找不到则从溢出区中查找。
其中，链地址法是最常用的方法，它具有简单、可扩展性好的特点。实现时只需要在哈希表中维护一个链表即可。开放地址法虽然实现起来相对简单，但在处理高密度数据时会导致性能下降。建立公共溢出区虽然能够解决哈希冲突，但当数据集比较大时，该方法的效率会比较低，因为需要从溢出区中查找数据。
☀️4.1.1 链地址法
哈希冲突的链地址法（Chaining）是一种解决哈希表冲突的方法。它的基本思想是在哈希表存储的每个位置上放置一个链表，当多个关键字哈希到同一位置时，将它们存储在同一个链表中，称为同义词链。
在链地址法中，哈希表的主要数据结构是一个数组，数组中的每个元素都是一个链表的头结点。当插入一个新元素时，先计算关键字的哈希值，然后根据哈希值找到对应的数组元素，如果该元素为空，则将新元素作为该元素的头结点；如果该元素不为空，则遍历该链表，查找是否已经存在相同的关键字，如果没有，则将新元素添加到该链表的末尾。
在查询一个元素时，先计算出该元素的哈希值，然后根据哈希值找到对应的数组元素，然后遍历该元素所对应的链表，查找是否有相同的关键字。
链地址法是一种简单有效的哈希冲突解决方法，具有较好的时间复杂度和空间利用率。但是，它需要额外的空间存储链表结构，而且当同义词链过长时，查询效率会降低，因此需要合理设置哈希表大小和调整哈希函数，以尽量减少哈希冲突的发生。
/* 链式地址哈希表 */
class HashMapChaining {
int size; // 键值对数量
int capacity; // 哈希表容量
double loadThres; // 触发扩容的负载因子阈值
int extendRatio; // 扩容倍数
List<List<Pair>> buckets; // 桶数组
/* 构造方法 */
public HashMapChaining() {
size = 0;
capacity = 4;
loadThres = 2.0 / 3.0;
extendRatio = 2;
buckets = new List<List<Pair>>(capacity);
for (int i = 0; i < capacity; i++) {
buckets.Add(new List<Pair>());
}
}
/* 哈希函数 */
private int hashFunc(int key) {
return key % capacity;
}
/* 负载因子 */
private double loadFactor() {
return (double)size / capacity;
}
/* 查询操作 */
public string get(int key) {
int index = hashFunc(key);
// 遍历桶，若找到 key 则返回对应 val
foreach (Pair pair in buckets[index]) {
if (pair.key == key) {
return pair.val;
}
}
// 若未找到 key 则返回 null
return null;
}
/* 添加操作 */
public void put(int key, string val) {
// 当负载因子超过阈值时，执行扩容
if (loadFactor() > loadThres) {
extend();
}
int index = hashFunc(key);
// 遍历桶，若遇到指定 key ，则更新对应 val 并返回
foreach (Pair pair in buckets[index]) {
if (pair.key == key) {
pair.val = val;
return;
}
}
// 若无该 key ，则将键值对添加至尾部
buckets[index].Add(new Pair(key, val));
size++;
}
/* 删除操作 */
public void remove(int key) {
int index = hashFunc(key);
// 遍历桶，从中删除键值对
foreach (Pair pair in buckets[index].ToList()) {
if (pair.key == key) {
buckets[index].Remove(pair);
size--;
break;
}
}
}
/* 扩容哈希表 */
private void extend() {
// 暂存原哈希表
List<List<Pair>> bucketsTmp = buckets;
// 初始化扩容后的新哈希表
capacity *= extendRatio;
buckets = new List<List<Pair>>(capacity);
for (int i = 0; i < capacity; i++) {
buckets.Add(new List<Pair>());
}
size = 0;
// 将键值对从原哈希表搬运至新哈希表
foreach (List<Pair> bucket in bucketsTmp) {
foreach (Pair pair in bucket) {
put(pair.key, pair.val);
}
}
}
/* 打印哈希表 */
public void print() {
foreach (List<Pair> bucket in buckets) {
List<string> res = new List<string>();
foreach (Pair pair in bucket) {
res.Add(pair.key + " -> " + pair.val);
}
foreach (string kv in res) {
Console.WriteLine(kv);
}
}
}
}
public class hash_map_chaining {
[Test]
public void Test() {
/* 初始化哈希表 */
HashMapChaining map = new HashMapChaining();
/* 添加操作 */
// 在哈希表中添加键值对 (key, value)
map.put(12836, "小哈");
map.put(15937, "小啰");
map.put(16750, "小算");
map.put(13276, "小法");
map.put(10583, "小鸭");
Console.WriteLine("\n添加完成后，哈希表为\nKey -> Value");
map.print();
/* 查询操作 */
// 向哈希表输入键 key ，得到值 value
string name = map.get(13276);
Console.WriteLine("\n输入学号 13276 ，查询到姓名 " + name);
/* 删除操作 */
// 在哈希表中删除键值对 (key, value)
map.remove(12836);
Console.WriteLine("\n删除 12836 后，哈希表为\nKey -> Value");
map.print();
}
}
☀️4.1.2 开放寻址法
哈希冲突的开放寻址法是一种解决哈希冲突的方法，它的基本思想是将发生冲突的元素插入到哈希表中的另一个空闲单元中。这种方法需要在哈希表中使用一个标记数组，用于标记每个单元是否被占用，以及一个处理冲突的函数。
开放寻址法分为三种方式：
-
线性探测：当发生冲突时，依次扫描哈希表中的下一个单元，直到找到一个空闲单元。
-
二次探测：当发生冲突时，从当前位置开始，按照一定的步长探测下一个单元，直到找到一个空闲单元。
-
双重散列：当发生冲突时，使用另外一个哈希函数计算出一个新的哈希值，然后根据这个新的哈希值继续查找哈希表中的下一个单元。
开放寻址法的优点是不需要额外的空间来存储链表，缺点是当哈希表的负载因子比较大时，开放寻址法的冲突率会变得很高，影响查找性能。此时可以考虑使用链表法解决哈希冲突。
/* 开放寻址哈希表 */
class HashMapOpenAddressing {
private int size; // 键值对数量
private int capacity = 4; // 哈希表容量
private double loadThres = 2.0 / 3.0; // 触发扩容的负载因子阈值
private int extendRatio = 2; // 扩容倍数
private Pair[] buckets; // 桶数组
private Pair TOMBSTONE = new Pair(-1, "-1"); // 删除标记
/* 构造方法 */
public HashMapOpenAddressing() {
size = 0;
buckets = new Pair[capacity];
}
/* 哈希函数 */
private int hashFunc(int key) {
return key % capacity;
}
/* 负载因子 */
private double loadFactor() {
return (double)size / capacity;
}
/* 搜索 key 对应的桶索引 */
private int findBucket(int key) {
int index = hashFunc(key);
int firstTombstone = -1;
// 线性探测，当遇到空桶时跳出
while (buckets[index] != null) {
// 若遇到 key ，返回对应桶索引
if (buckets[index].key == key) {
// 若之前遇到了删除标记，则将键值对移动至该索引
if (firstTombstone != -1) {
buckets[firstTombstone] = buckets[index];
buckets[index] = TOMBSTONE;
return firstTombstone; // 返回移动后的桶索引
}
return index; // 返回桶索引
}
// 记录遇到的首个删除标记
if (firstTombstone == -1 && buckets[index] == TOMBSTONE) {
firstTombstone = index;
}
// 计算桶索引，越过尾部返回头部
index = (index + 1) % capacity;
}
// 若 key 不存在，则返回添加点的索引
return firstTombstone == -1 ? index : firstTombstone;
}
/* 查询操作 */
public string get(int key) {
// 搜索 key 对应的桶索引
int index = findBucket(key);
// 若找到键值对，则返回对应 val
if (buckets[index] != null && buckets[index] != TOMBSTONE) {
return buckets[index].val;
}
// 若键值对不存在，则返回 null
return null;
}
/* 添加操作 */
public void put(int key, string val) {
// 当负载因子超过阈值时，执行扩容
if (loadFactor() > loadThres) {
extend();
}
// 搜索 key 对应的桶索引
int index = findBucket(key);
// 若找到键值对，则覆盖 val 并返回
if (buckets[index] != null && buckets[index] != TOMBSTONE) {
buckets[index].val = val;
return;
}
// 若键值对不存在，则添加该键值对
buckets[index] = new Pair(key, val);
size++;
}
/* 删除操作 */
public void remove(int key) {
// 搜索 key 对应的桶索引
int index = findBucket(key);
// 若找到键值对，则用删除标记覆盖它
if (buckets[index] != null && buckets[index] != TOMBSTONE) {
buckets[index] = TOMBSTONE;
size--;
}
}
/* 扩容哈希表 */
private void extend() {
// 暂存原哈希表
Pair[] bucketsTmp = buckets;
// 初始化扩容后的新哈希表
capacity *= extendRatio;
buckets = new Pair[capacity];
size = 0;
// 将键值对从原哈希表搬运至新哈希表
foreach (Pair pair in bucketsTmp) {
if (pair != null && pair != TOMBSTONE) {
put(pair.key, pair.val);
}
}
}
/* 打印哈希表 */
public void print() {
foreach (Pair pair in buckets) {
if (pair == null) {
Console.WriteLine("null");
} else if (pair == TOMBSTONE) {
Console.WriteLine("TOMBSTONE");
} else {
Console.WriteLine(pair.key + " -> " + pair.val);
}
}
}
}
public class hash_map_open_addressing {
[Test]
public void Test() {
/* 初始化哈希表 */
HashMapOpenAddressing map = new HashMapOpenAddressing();
/* 添加操作 */
// 在哈希表中添加键值对 (key, value)
map.put(12836, "小哈");
map.put(15937, "小啰");
map.put(16750, "小算");
map.put(13276, "小法");
map.put(10583, "小鸭");
Console.WriteLine("\n添加完成后，哈希表为\nKey -> Value");
map.print();
/* 查询操作 */
// 向哈希表输入键 key ，得到值 value
string name = map.get(13276);
Console.WriteLine("\n输入学号 13276 ，查询到姓名 " + name);
/* 删除操作 */
// 在哈希表中删除键值对 (key, value)
map.remove(16750);
Console.WriteLine("\n删除 16750 后，哈希表为\nKey -> Value");
map.print();
}
}
🦋4.2 哈希算法
☀️4.2.1 哈希算法的意义
对于链地址哈希表，理想情况下键值对平均分布在各个桶中，达到最佳查询效率；最差情况下所有键值对都被存储到同一个桶中，时间复杂度退化至O(n)。
当哈希表容量 capacity固定时，哈希算法 hash()决定了输出值，进而决定了键值对在哈希表中的分布情况。
☀️4.2.2 哈希算法的目标
哈希算法的目标是将输入数据（例如字符串、文件、数字等）转换成固定长度的唯一输出值，称为哈希值或摘要。哈希算法的主要目的是保证数据的完整性和安全性，它可以用于数据加密、数字签名、数据验证、密码存储、数据比较等方面。哈希算法应该满足以下几个要求：
-
唯一性：对于不同的输入数据，哈希值应该是唯一的，即哈希冲突率尽可能低。
-
高效性：对于任意长度的输入数据，哈希算法应该能够快速计算出唯一的哈希值。
-
不可逆性：从哈希值无法推算出原始输入数据，即哈希算法应该是单向的。
-
散列性：即输入数据的微小变化应该能够引起哈希值的明显变化，这个属性也被称为“雪崩效应”。
哈希算法的应用非常广泛，如数据密钥管理、防篡改技术、密码学、文件系统、数据库管理和网络安全等领域。
☀️4.2.3 哈希算法的设计
哈希算法的设计是一个需要考虑许多因素的复杂问题。然而对于某些要求不高的场景，我们也能设计一些简单的哈希算法。
-
加法哈希：对输入的每个字符的 ASCII码进行相加，将得到的总和作为哈希值。
-
乘法哈希：利用了乘法的不相关性，每轮乘以一个常数，将各个字符的 ASCII码累积到哈希值中。
-
异或哈希：将输入数据的每个元素通过异或操作累积到一个哈希值中。
-
旋转哈希：将每个字符的 ASCII码累积到一个哈希值中，每次累积之前都会对哈希值进行旋转操作。
public class simple_hash {
/* 加法哈希 */
public static int addHash(string key) {
long hash = 0;
const int MODULUS = 1000000007;
foreach (char c in key) {
hash = (hash + c) % MODULUS;
}
return (int)hash;
}
/* 乘法哈希 */
public static int mulHash(string key) {
long hash = 0;
const int MODULUS = 1000000007;
foreach (char c in key) {
hash = (31 * hash + c) % MODULUS;
}
return (int)hash;
}
/* 异或哈希 */
public static int xorHash(string key) {
int hash = 0;
const int MODULUS = 1000000007;
foreach (char c in key) {
hash ^= c;
}
return hash & MODULUS;
}
/* 旋转哈希 */
public static int rotHash(string key) {
long hash = 0;
const int MODULUS = 1000000007;
foreach (char c in key) {
hash = ((hash << 4) ^ (hash >> 28) ^ c) % MODULUS;
}
return (int)hash;
}
[Test]
public void Test() {
string key = "Hello 算法";
int hash = addHash(key);
Console.WriteLine("加法哈希值为 " + hash);
hash = mulHash(key);
Console.WriteLine("乘法哈希值为 " + hash);
hash = xorHash(key);
Console.WriteLine("异或哈希值为 " + hash);
hash = rotHash(key);
Console.WriteLine("旋转哈希值为 " + hash);
}
}
☀️4.2.4 常见哈希算法
常见的哈希算法有：
-
MD5（Message Digest Algorithm 5）：输出128位散列值，被广泛应用于加密和验证文件的完整性，虽然现在已不被推荐使用。
-
SHA-1（Secure Hash Algorithm 1）：输出160位散列值，被广泛用于数字签名和加密等领域，目前算法已经过时。
-
SHA-2（Secure Hash Algorithm 2）：SHA-2系列算法包括SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224、SHA-512/256等，输出256位或更长的散列值，应用广泛。
-
SHA-3（Secure Hash Algorithm 3）：输出不同长度的散列值，能够提供比SHA-2更好的抗攻击性能，目前已被广泛应用。
-
CRC（Cyclic Redundancy Check）：用于检验数据传输中是否有错误，适用于数据传输的快速校验，但不适用于加密等安全应用。
/// <summary>
/// Hash辅助类
/// </summary>
public class HashHelper
{
/// <summary>
/// 计算文件的 MD5 值
/// </summary>
/// <param name="fileName">要计算 MD5 值的文件名和路径</param>
/// <returns>MD5 值16进制字符串</returns>
public static string MD5File(string fileName)
{
return HashFile(fileName, "md5");
}
/// <summary>
/// 计算文件的 sha1 值
/// </summary>
/// <param name="fileName">要计算 sha1 值的文件名和路径</param>
/// <returns>sha1 值16进制字符串</returns>
public static string SHA1File(string fileName)
{
return HashFile(fileName, "sha1");
}
/// <summary>
/// 计算文件的哈希值
/// </summary>
/// <param name="fileName">要计算哈希值的文件名和路径</param>
/// <param name="algName">算法:sha1,md5</param>
/// <returns>哈希值16进制字符串</returns>
private static string HashFile(string fileName, string algName)
{
if (!System.IO.File.Exists(fileName))
{
return string.Empty;
}
System.IO.FileStream fs = new System.IO.FileStream(fileName, System.IO.FileMode.Open, System.IO.FileAccess.Read);
byte[] hashBytes = HashData(fs, algName);
fs.Close();
return ByteArrayToHexString(hashBytes);
}
/// <summary>
/// 计算哈希值
/// </summary>
/// <param name="stream">要计算哈希值的 Stream</param>
/// <param name="algName">算法:sha1,md5</param>
/// <returns>哈希值字节数组</returns>
private static byte[] HashData(System.IO.Stream stream, string algName)
{
System.Security.Cryptography.HashAlgorithm algorithm;
if (algName == null)
{
throw new ArgumentNullException("algName 不能为 null");
}
if (string.Compare(algName, "sha1", true) == 0)
{
algorithm = System.Security.Cryptography.SHA1.Create();
}
else
{
if (string.Compare(algName, "md5", true) != 0)
{
throw new Exception("algName 只能使用 sha1 或 md5");
}
algorithm = System.Security.Cryptography.MD5.Create();
}
return algorithm.ComputeHash(stream);
}
/// <summary>
/// 字节数组转换为16进制表示的字符串
/// </summary>
private static string ByteArrayToHexString(byte[] buf)
{
return BitConverter.ToString(buf).Replace("-", "");
}
}
[TestClass]
public class HashHelperUnitTest
{
[TestMethod]
public void TestMethod1()
{
string fileName = @"D:\TempTest\RDIFramework.BizLogic.dll";
Assert.AreEqual(0, 0);
//01.计算文件的 MD5 值
Console.WriteLine(string.Format("计算文件的 MD5 值：{0}", HashHelper.MD5File(fileName)));
//02.计算文件的 sha1 值
Console.WriteLine(string.Format("计算文件的 sha1 值：{0}", HashHelper.SHA1File(fileName)));
}
}
☀️4.2.5 数据结构的哈希值
public class built_in_hash {
[Test]
public void Test() {
int num = 3;
int hashNum = num.GetHashCode();
Console.WriteLine("整数 " + num + " 的哈希值为 " + hashNum);
bool bol = true;
int hashBol = bol.GetHashCode();
Console.WriteLine("布尔量 " + bol + " 的哈希值为 " + hashBol);
double dec = 3.14159;
int hashDec = dec.GetHashCode();
Console.WriteLine("小数 " + dec + " 的哈希值为 " + hashDec);
string str = "Hello 算法";
int hashStr = str.GetHashCode();
Console.WriteLine("字符串 " + str + " 的哈希值为 " + hashStr);
object[] arr = { 12836, "小哈" };
int hashTup = arr.GetHashCode();
Console.WriteLine("数组 [" + string.Join(", ", arr) + "] 的哈希值为 " + hashTup);
ListNode obj = new ListNode(0);
int hashObj = obj.GetHashCode();
Console.WriteLine("节点对象 " + obj + " 的哈希值为 " + hashObj);
}
}
在许多编程语言中，只有不可变对象才可作为哈希表的 key 。假如我们将列表（动态数组）作为 key ，当列表的内容发生变化时，它的哈希值也随之改变，我们就无法在哈希表中查询到原先的 value 了。
虽然自定义对象（比如链表节点）的成员变量是可变的，但它是可哈希的。这是因为对象的哈希值通常是基于内存地址生成的，即使对象的内容发生了变化，但它的内存地址不变，哈希值仍然是不变的。
细心的你可能发现在不同控制台中运行程序时，输出的哈希值是不同的。这是因为 Python 解释器在每次启动时，都会为字符串哈希函数加入一个随机的盐（Salt）值。这种做法可以有效防止 HashDoS 攻击，提升哈希算法的安全性。
🔎5.优点和缺点
哈希表是一种用于存储键值对的数据结构，其优点和缺点如下：
优点：
- 快速查找：哈希表的查找时间复杂度为O(1)，具有快速查找的优势；
- 高效插入和删除：哈希表的插入和删除操作时间复杂度也为O(1)，具有高效的插入和删除操作；
- 适用于大数据量：哈希表适用于存储大量数据，因为其查找时间不会随着数据量的增加而增加。
缺点：
- 哈希冲突：哈希表中不同的键值可能会散列到同一个位置上，这种情况称为哈希冲突，解决哈希冲突的方法有很多种，但是会增加空间和时间的开销；
- 内存占用：哈希表需要使用额外的空间来存储哈希函数和链表，空间占用较高；
- 不支持范围查询：哈希表中的元素并不是按照顺序排列的，因此不支持范围查询，例如查找大于某个值的元素。
🔎6.应用场景
哈希表通常用于需要快速查找和插入大量数据的场景，例如：
-
缓存：常见的缓存策略就是使用哈希表来存储数据，以提高读写效率。
-
数据库索引：数据库通常会使用哈希表来实现索引，以加快查询速度。
-
字典：哈希表可以用于实现字典，将字符串映射为对应的键值对。
-
键值存储：键值存储通常使用哈希表实现，以快速查找相应键值对应的数据。
-
任务调度：哈希表可以用于实现任务调度器，将不同的任务分配到不同的桶中，定时执行任务。
-
防止重复：哈希表可以用于防止重复操作，例如过滤重复的数据、判断是否已经处理过某些数据等。
哈希表在数据处理、数据存储、数据分析等场景中都有广泛的应用。
🚀感谢：给读者的一封信
亲爱的读者，
我在这篇文章中投入了大量的心血和时间，希望为您提供有价值的内容。这篇文章包含了深入的研究和个人经验，我相信这些信息对您非常有帮助。
如果您觉得这篇文章对您有所帮助，我诚恳地请求您考虑赞赏1元钱的支持。这个金额不会对您的财务状况造成负担，但它会对我继续创作高质量的内容产生积极的影响。
我之所以写这篇文章，是因为我热爱分享有用的知识和见解。您的支持将帮助我继续这个使命，也鼓励我花更多的时间和精力创作更多有价值的内容。
如果您愿意支持我的创作，请扫描下面二维码，您的支持将不胜感激。同时，如果您有任何反馈或建议，也欢迎与我分享。
再次感谢您的阅读和支持！
最诚挚的问候， “愚公搬代码”
- 点赞
- 收藏
- 关注作者
评论（0）