哈希值与哈希表 • ArronHC的博客

哈希值#

将任何值通过哈希函数转换为哈希值 具有以下特点：

同一值转换的哈希值是固定的
不论输入值长度大小，哈希值的长度是固定的
无法通过哈希值反推原值

简单总结：哈希值就是数据的“指纹”或“身份证号”。它独一无二（理想情况下），能代表原始数据，但又隐藏了原始数据的具体内容。

哈希表#

哈希表是一种数据结构，它利用哈希值的思想来实现极速的增、删、查、改。 分为以下步骤：

将输入值转换为哈希值
假如要对数据进行存储操作，查询哈希值是否发生冲突，若有，进行冲突处理
哈希值对容器大小取模得到容器中数据的索引，从而对数据进行增删改查

哈希冲突#

在实际操作中，通过哈希函数转换，张三 和 李四 可能得到相同的哈希值，例如 47，这样会导致两个人共用同一个“47号柜子”。

对于这样的冲突，提供两种解决方法：

一. 链表法#

通过哈希函数得到柜子号 47
这次我们给柜子挂上一条链表，链表上存储着所有哈希值等于柜子号的数据
这样一来，用户得到哈希值对应到柜号 47后，只需要顺着链表就能找到自己的数据

二. 开放空间法（线性搜索法）#

通过哈希函数得到柜子号 47
李四发现张三已经占用了 47 柜子，则往后搜索，看看 48、49… 找到第一个空柜子存自己的数据

哈希函数的选择#

我们的核心目标是：追求速度和均匀性、追求安全性 均匀分布是为了降低冲突概率

一、用于数据结构的增删改查#

使用非加密哈希函数 特点：

速度快
散列均匀：能最大限度地避免冲突
对小输入友好：即使数据只有微小变化，仍然会导致哈希值变化很大 常见选择：
MurmurHash：性能极高，分布性非常好，是业界非常流行的非加密哈希算法。Redis, Hadoop 等很多知名项目都在使用它。
FNV (Fowler-Noll-Vo)：一个非常简单且快速的算法，在很多场景下表现良好，易于实现。
xxHash：以其惊人的速度而闻名，在许多基准测试中都是最快的哈希算法之一，同时保持了良好的分布性。
CityHash / FarmHash：由 Google 开发，专为 64 位架构优化，性能卓越。

黄金法则：

黄金法则：不要自己造轮子！
绝大多数情况下，你不需要自己去实现这些算法。直接使用你所用编程语言内置的哈希功能即可。

在 Java 中，每个对象都有 hashCode() 方法。HashMap 就依赖这个方法。

在 Python 中，有内置的 hash() 函数。dict 和 set 都依赖它。

在 C++ 中，标准库提供了 std::hash。

语言标准库的实现通常是经过深度优化的、可靠的非加密哈希函数，它们足以应对绝大多数哈希表的需求。只有在对性能有极致要求的特定场景下，才需要考虑引入 MurmurHash、xxHash 等第三方库。

二. 用于数据加密#

此时, 速度不再是第一要义, 算法的安全性最重要所以我们使用加密哈稀函数 评估标准:

符合基础特点
原像抗性: 不可逆性
第二原像抗性: 抗篡改性

Example

举个例子, 网站在发给你一个文件的同时, 像你发送了一串 SHA-256 哈希值, 让你检验文件是否被篡改

一个黑客想攻击你, 制作了病毒文件, 并通过技术让他的文件哈希值也恰好等于原哈希值

这样一来, 你一比对并无偏差, 安安心心的下载了病毒文件, 招致了困惑

碰撞抗性: 几乎不可能找到任意两个不同的 A 和 B, 使得 H(A) 等于 H(B)

哈希函数在 c++中的实现#

在 c++中，我们无需导入库，可直接使用 hash 类实现

hash<string> stringHasher;//创建哈希函数
string s = "abc";
cout<<stringHasher(s);

cpp

哈希表在 c++中的实现#

在 c++中，哈希表通常采用 #include<unordered_map> 实现，unordered_map 用于存储键值对，正好符合哈希表的功能。以下是利用哈希表在列表中以 O(n) 实现数据查找

#include<unordered_map>

unordered_map<int,int> hashTable;
for(int i=1;i<=n;i++) {
	hashTable[a[i]] = i;
}
cin>>x;
auto it = hashTable.find(x);
if(it != hashTable.end()) {
	return it->second;
}
return NULL;

cpp