一篇文章搞懂C++实现哈希算法_C/C++

#include <iostream>
#include <string>

unsigned int simplehash(const std::string& input) 
{
    unsigned int hash = 0;
    for (char c : input) {
        hash = hash * 31 + c;  // 使用31乘以之前的哈希值并添加当前字符的ascii值
    }
    return hash;
}

int main() 
{
    std::string data = "hello, world!";
    std::cout << "the hash of '" << data << "' is " << simplehash(data) << std::endl;
    return 0;
}

解释代码

1.函数定义:

simplehash函数接受一个std::string类型的输入，并返回一个unsigned int类型的哈希值。

2.初始化哈希值:

unsigned int hash = 0;这行代码初始化哈希值为0。这是累加过程的起始点。

3.遍历字符串中的每个字符:

for (char c : input)循环遍历输入字符串中的每个字符。

4.计算哈希值:

hash = hash * 31 + c;这行是核心的哈希算法，其中31是一个质数，这是哈希函数设计中常用的一个技巧。质数在哈希函数中的使用可以帮助更均匀地分布哈希值，从而减少冲突的概率。每个字符的ascii值被加到乘以31的当前哈希值上。

5.返回哈希值:

函数通过return hash;返回最终计算出的哈希值。

其中为什么使用31？

在哈希函数中使用31的原因是它是一个相对小的质数，可以帮助在乘法运算中减少哈希值的碰撞（即不同的输入产生相同的输出）。此外，质数在乘法运算中有助于更好地分散哈希值，使得输出分布更加均匀。通过这样一个简单的示例，你可以开始理解哈希函数是如何将输入（在这种情况下是字符串）转换成一个较小的、固定大小的数值（哈希值）。这个过程对于构建更复杂的数据结构如哈希表，以及在其他应用如数据检索和安全性中都是非常重要的。

二、哈希表

哈希表是一种非常重要的数据结构，广泛应用于需要快速数据访问的场景。在c++中，哈希表通常通过标准模板库（stl）中的std::unordered_map实现。在深入解释哈希表的使用前，我们先了解一下它的基本概念和原理。

哈希表概念

哈希表利用哈希函数将键（key）映射到表中一个位置上，以存储相应的值（value）。这允许快速的数据插入、查找和删除。理想情况下，哈希函数应该将键均匀分布在哈希表中，从而最小化键之间的冲突。

c++中的`std::unordered_map`

在c++中，std::unordered_map是一个基于哈希表实现的关联容器，它存储元素形成键值对。下面是如何使用std::unordered_map的一个简单例子：

#include <iostream>
#include <unordered_map>
#include <string>

int main() {
    // 创建一个unordered_map，键类型为std::string，值类型为int
    std::unordered_map<std::string, int> agemap;

    // 插入数据
    agemap["alice"] = 30;
    agemap["bob"] = 25;
    agemap["charlie"] = 35;

    // 访问和输出bob的年龄
    std::cout << "bob's age is: " << agemap["bob"] << std::endl;

    // 检查一个键是否存在
    std::string key = "dave";
    if (agemap.find(key) == agemap.end()) {
        std::cout << key << " not found in the map." << std::endl;
    } else {
        std::cout << key << "'s age is: " << agemap[key] << std::endl;
    }

    // 删除一个元素
    agemap.erase("alice");

    // 遍历哈希表中的所有元素
    std::cout << "current contents of the map:" << std::endl;
    for (const auto& pair : agemap) {
        std::cout << pair.first << " is " << pair.second << " years old." << std::endl;
    }

    return 0;
}

代码解释

1.创建哈希表:

std::unordered_map<std::string, int> agemap; 这行代码创建了一个哈希表，其中键是字符串类型，值是整数类型。

2.插入元素:

使用方括号操作符[]插入和访问元素。例如，agemap["alice"] = 30; 将键为"alice"的元素设置为30。

3.访问元素:

通过键直接访问元素，如agemap["bob"]访问bob的年龄。

4.检查键存在:

使用find方法检查一个键是否存在。如果键不存在，find返回end迭代器。

5.删除元素:

使用erase方法通过键来删除元素。

6.遍历哈希表:

使用范围基于的for循环遍历unordered_map，每个元素是一个键值对。

使用哈希表的优势：

高效性：哈希表的插入、删除和查找操作通常在常数时间内完成，适用于需要快速访问数据的应用场景。

灵活性：哈希表可以存储各种类型的键值对，适应不同的数据处理需求。

自动管理：哈希表会自动处理哈希函数调用和冲突解决，不需要手动管理。

内置函数：std::unordered_map提供了丰富的成员函数，支持多种操作如查找、插入、删除、遍历等，简化了开发过程。

三、哈希算法的应用：

1. 数据检索（哈希表）

哈希算法最常见的应用之一就是实现哈希表，也称为散列表。哈希表是一种使用哈希算法快速定位数据的数据结构，可以实现几乎即时的数据插入、查找和删除操作。在哈希表中，数据项通过哈希函数转换为一个哈希值，该哈希值作为数组的索引。每个索引位置称为一个“桶”，桶中可以存放一个或多个元素。

例如，在一个在线商店的商品数据库中，商品的id可以通过哈希算法映射到哈希表的一个位置，从而快速定位该商品的信息，如价格、描述等。

2. 安全加密

哈希算法在保障数据安全方面也扮演着重要角色。安全的哈希算法（如sha-256）能够从任何形式的数据生成一个固定长度的哈希值，这个哈希值对于原始数据来说是唯一的。由于哈希函数的单向特性，给定一个哈希值，几乎不可能恢复出原始数据。

在密码学中，用户的密码常常通过哈希处理后存储在数据库中，这样即便数据库被泄露，黑客也难以直接获取原始密码。同时，哈希算法也用于生成数据的数字签名，确保数据在传输过程中未被篡改。

3. 数据去重

哈希算法广泛应用于数据去重，这在处理大量数据时尤为重要。通过为每个数据项计算哈希值，然后将哈希值存储到一种快速查找的结构（如哈希集合）中，可以快速检查新数据是否已存在。

例如，在电子邮件系统中防止发送重复邮件，系统可以存储每封邮件内容的哈希值，新邮件到来时先计算其哈希值，如果哈希值已存在，则判断该邮件为重复。

4. 负载均衡

在大规模分布式系统中，哈希算法可以用于实现负载均衡。通过对客户端的ip地址或会话id进行哈希处理，将请求均匀分配到不同的服务器上。这样可以确保服务器的负载均衡，提高系统的处理能力和效率。

5. 缓存机制

在web服务中，哈希算法用于缓存优化。服务器可以对页面或数据进行哈希处理，然后将哈希值与数据内容关联起来存储在缓存中。用户再次请求相同数据时，服务器先计算请求的哈希值，直接从缓存中取得对应数据，减少数据处理时间，提高响应速度。

以上内容为本人学习后总结输出的结果，如果对大家有所帮助，动动手指三连哦！

一篇文章搞懂C++实现哈希算法

2024年07月28日 • C/C++ •我要评论

一、哈希算法概述

哈希算法定义

哈希函数的特性

示例：简单的字符串哈希函数