C++数据结构之哈希算法详解

概述

哈希算法是一种常用于对数据进行快速检索的算法，它通常将数据映射为一个较短的指纹码，并将这个指纹码作为数据的索引值，这样可以快速地根据索引值找到对应的数据。

本文将详细讲解哈希算法的实现原理、常见应用场景以及在 C++ 语言中如何实现一个简单的哈希表。

哈希算法的实现原理

哈希算法的核心思想是将输入数据通过一个哈希函数进行映射，将其转换为一个固定长度的指纹码，从而实现快速检索。

常用的哈希函数有以下几种：

• 直接寻址法
• 数字分析法
• 平方取中法
• 折叠法
• 随机数法
• 数字转化为字符串法

其中，直接寻址法最为简单，它将输入数据直接作为指纹码的位置，比如输入数据为 x，则它的指纹码为 x。但显然这种写法适用性较差，如果输入数据的取值很大，在散列表中就会产生许多空洞，造成空间的浪费。因此，我们一般使用其他哈希函数来实现哈希算法。

比较常用的是平方取中法，这种算法将输入数据的平方值的中间 n 位作为指纹码的值，其中 n 是指纹码的长度。这种算法的好处在于可以避免输入数据较小的情况下产生的空洞问题，但在输入数据非常大的情况下，还是会产生空洞。

其他的哈希函数，如折叠法、随机数法等，都有其具体的实现细节，需要根据具体的应用场景进行选择。

哈希算法的应用场景

哈希算法广泛应用于大规模数据的快速检索中，例如：

• 基于关键字的搜索引擎
• 负载均衡
• 数据库索引
• 缓存实现

在这些应用场景下，哈希算法能够通过将输入数据进行快速映射，快速地定位到对应的数据，大大提升了系统的查询速度和响应速度。

在 C++ 语言中实现哈希表

在 C++ 语言中，可以使用 STL 中提供的 unordered_map 来实现哈希表的功能。unordered_map 可以接收一个哈希函数，将输入数据映射为一个指纹码，并将指纹码作为 key，对应的值存储在哈希表中。

#include <iostream>
#include <unordered_map>

int main()
{
    std::unordered_map<int, std::string> hash_map;

    // 插入数据
    hash_map[1] = "one";
    hash_map[2] = "two";
    hash_map[3] = "three";

    // 查询数据
    std::cout << hash_map[1] << std::endl;

    // 遍历哈希表
    for (auto& iter : hash_map)
    {
        std::cout << "Key = " << iter.first << ", Value = " << iter.second << std::endl;
    }

    return 0;
}

在上述代码中，我们创建了一个 unordered_map 对象 hash_map，将一些数据插入到哈希表中，并通过 key 查询对应的 value。同时，我们也演示了如何遍历哈希表中的所有数据，可以看到，查询和遍历操作都非常快速。

此外，C++ 11 中还提供了一些哈希函数，如 std::hash 和 std::hash_combine 等，可以方便地自定义哈希函数，从而实现更加灵活的哈希算法。

示例说明

示例一：基于哈希表实现电话簿

下面我们来通过一个例子，更深入地了解哈希算法的实际应用。我们将使用哈希表来实现一个简单的电话簿程序，从而更好地理解哈希算法的实现过程。

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

// 定义联系人结构体
struct Contact {
    std::string name;
    std::string phone_number;
};

int main()
{
    // 定义哈希表对象
    std::unordered_map<std::string, Contact> phone_book;

    // 插入联系人信息
    phone_book["Tom"] = { "Tom", "123456" };
    phone_book["Jerry"] = { "Jerry", "111111" };
    phone_book["Alice"] = { "Alice", "222222" };

    // 查询联系人信息
    std::string name = "Alice";
    if (phone_book.count(name)) {
        Contact contact = phone_book[name];
        std::cout << "Name: " << contact.name << ", Phone: " << contact.phone_number << std::endl;
    }
    else {
        std::cout << "Contact not found." << std::endl;
    }

    return 0;
}

在上述代码中，我们定义了一个名为 Contact 的结构体，用于存储每个联系人的姓名和电话号码。通过使用哈希表，我们可以将每个联系人的姓名作为 key，对应的 Contact 对象作为 value，来进行快速的查找。

在程序中，我们首先插入了一些联系人信息，然后查询了一个名为 Alice 的联系人，并输出了其姓名和电话号码。可以看到，使用哈希表实现电话簿程序非常简单且高效。

示例二：基于哈希表实现缓存

另一个应用哈希表的实际例子是实现一个缓存程序。缓存程序通常需要快速读取和写入数据，并且可以限制存储数据的大小，当缓存已达到上限时自动删除最旧的数据。

下面是一个示例代码，用于演示如何使用哈希表来实现一个 LRU 缓存。

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

// 定义缓存对象结构体
struct CacheEntry {
    std::string key;
    std::string value;
    CacheEntry(const std::string& k, const std::string& v) : key(k), value(v) {}
};

class LRUCache {
public:
    LRUCache(int capacity) : m_capacity(capacity) {}

    std::string get(const std::string& key) {
        auto iter = m_cache_map.find(key);
        if (iter == m_cache_map.end()) {
            return "";
        }
        m_key_list.splice(m_key_list.begin(), m_key_list, iter->second);
        return iter->second->value;
    }

    void put(const std::string& key, const std::string& value) {
        auto iter = m_cache_map.find(key);
        if (iter != m_cache_map.end()) {
            m_key_list.splice(m_key_list.begin(), m_key_list, iter->second);
            iter->second->value = value;
            return;
        }
        if (m_cache_map.size() == m_capacity) {
            auto last_node = m_key_list.end();
            last_node--;
            m_cache_map.erase(last_node->key);
            m_key_list.pop_back();
        }
        m_key_list.emplace_front(key, value);
        m_cache_map[key] = m_key_list.begin();
    }

private:
    std::unordered_map<std::string, std::list<CacheEntry>::iterator> m_cache_map;
    std::list<CacheEntry> m_key_list;
    int m_capacity;
};

int main()
{
    LRUCache cache(2);

    cache.put("key1", "value1");
    cache.put("key2", "value2");
    std::cout << cache.get("key1") << std::endl; // Expected output: "value1"
    cache.put("key3", "value3");
    std::cout << cache.get("key2") << std::endl; // Expected output: ""

    return 0;
}

在上述代码中，我们使用了一个哈希表来缓存数据，并使用一个双向链表来记录数据的访问顺序。其中，双向链表头结点表示最近访问的数据，链表尾结点表示最近最少访问的数据。当程序需要插入新数据时，如果缓存已满，则删除最近最少访问的数据；如果需要访问数据时，将其移动到链表头结点，表示最近访问过。通过这种方式，我们可以在满足空间限制的情况下，实现快速地访问和插入数据。

总结

哈希算法是一种常用于数据快速检索的算法，它通过将输入数据映射为一个指纹码，并将指纹码作为数据的索引值，实现了快速检索的功能。在实际应用中，哈希算法可以应用于搜索引擎、负载均衡、数据库索引和缓存等方面。在 C++ 语言中，可以使用 STL 中提供的 unordered_map 来实现简单的哈希表，也可以使用 std::hash 和 std::hash_combine 等函数自定义哈希函数，实现更加灵活的哈希算法。