C++数据结构之：哈希表Hash

摘要：

   it人员无论是使用哪种高级语言开发东东，想要更高效有层次的开发程序的话都躲不开三件套：数据结构，算法和设计模式。数据结构是相互之间存在一种或多种特定关系的数据元素的集合，即带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系，分为逻辑结构和存储结构。

   此系列专注讲解数据结构数组、链表、队列、栈、树、哈希表、图，通过介绍概念以及提及一些可能适用的场景，并以c++代码简易实现，多方面认识数据结构，最后为避免重复造轮子会浅提对应的stl容器。本文介绍的是哈希表hash。

（开发环境：vscode，c++17）

关键词： c++，数据结构，哈希表，hash

(文章目录：)

正文：

介绍：

   哈希表（hash table，也叫散列表）是一种根据关键码值（key value）而直接进行访问的数据结构。它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做哈希函数，存放记录的数组叫做哈希表。

   从图中可以看出，左边是个数组，数组的每个成员包括一个指针，指向一个链表的头。我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。

   哈希表的主要优点是查找速度快，其时间复杂度通常接近o(1)。然而，哈希表也存在一些缺点，如空间利用率可能不高，以及处理冲突，当两个或多个关键字具有相同的散列地址时，此情况就叫做哈希冲突，哈希冲突几乎是无法避免的，解决哈希冲突的方法主要有两种，一种是开放寻址法，一种是链表法（哈希桶，也即是图中的结构法）。

特性：

• 快速查找：哈希表通过散列函数将关键字映射到表中的位置，从而实现常数时间复杂度的查找操作（平均情况下为o(1)）。
• 无序性：哈希表中的元素是无序的，它们按照散列函数计算出的地址进行存储。因此，哈希表不支持直接按照元素的顺序进行遍历。
• 动态调整：哈希表的大小可以根据需要进行动态调整，以平衡空间利用率和查找效率。

应用：

• 缓存系统：哈希表在缓存系统中被广泛使用，如cpu缓存、数据库查询缓存、web页面缓存等。通过将数据存储在哈希表中，可以快速查找和访问缓存中的数据，从而提高系统的性能。
• 数据库索引：哈希表可以用于构建数据库索引，加速数据的查找速度。在数据库系统中，哈希索引通常用于等值查询和范围查询。
• url路由：在web框架中，哈希表可以用于实现url路由。通过将url路径映射到对应的处理函数或控制器，可以快速定位到处理请求的代码。
• 网络协议：在网络协议中，哈希表可以用于实现路由表、arp缓存等功能。这些功能需要快速查找和匹配网络地址，哈希表提供了高效的解决方案。

代码实现：

#ifndef chash_h
#define chash_h
#include <iostream>
#include <vector>  
#include <list>  
#include <functional> 
#include <string>

using namespace std;
// 假设我们使用一个简单的整数键和一个字符串值  
using keytype = string;  
using valuetype = string;  
  
// 哈希函数，std::hash 为标准类型（如 int、std::string、std::pair 等）提供了默认的哈希函数
// 对于更复杂的键类型（如自定义类型）需要实现一个更复杂的哈希函数。
struct hashfunc {  
    size_t operator()(const keytype& key) const {  
        return hash<keytype>{}(key);  
    }
}; 

// 哈希表节点  
template <class k, class v>
class hashnode
{
public:
    k key;
    v value;
    hashnode* next;

public:
    hashnode(k k, v v) : key(k), value(v), next(nullptr) {}

private:
    // 禁止拷贝、赋值
    hashnode(const hashnode<k, v>& node);
    hashnode& operator=(const hashnode<k, v>& node);
};  
  

// 哈希表实现  
template <class k, class v, class hf = hashfunc>  
class chashtable 
{  
private:  
    vector<hashnode<k, v>*> buckets;  
    hf hashfunc;  
    size_t bucketsize;  
  
public:  
    chashtable(size_t size) : buckets(size, nullptr), hashfunc(), bucketsize(size) {}  
    ~chashtable();                          // 析构函数（用于释放内存）
      
    void insert(k key, v value);            // 插入键值对
    v find(k key, v defaultvalue = v());    // 查找键对应的值（如果不存在则返回默认值）  
    bool remove(k key);                     // 移除键值对
    void print();                           // 打印哈希表
    // 可添加动态调整大小（即当哈希表变满时增加桶的数量）
  
};
 
template <class k, class v, class hf>
inline chashtable<k, v, hf>::~chashtable()
{
    for (size_t i = 0; i < bucketsize; ++i)
    {
        hashnode<k, v>* current = buckets[i];
        while (current != nullptr) {
            hashnode<k, v>* todelete = current;
            current = current->next;
            delete todelete;
        }
    }
}

template <class k, class v, class hf>
inline void chashtable<k, v, hf>::insert(k key, v value)
{
    size_t index = hashfunc(key) % bucketsize;
    // 处理冲突（这里使用链地址法）
    hashnode<k, v>* newnode = new hashnode<k, v>(key, value);
    if (buckets[index] == nullptr) {
        buckets[index] = newnode;
    } 
    else {
        hashnode<k, v>* current = buckets[index];
        while (current->next != nullptr) {
            current = current->next;
        }
        current->next = newnode;
    }
}

template <class k, class v, class hf>
inline v chashtable<k, v, hf>::find(k key, v defaultvalue)
{
    size_t index = hashfunc(key) % bucketsize;
    hashnode<k, v>* current = buckets[index];
    while (current != nullptr) {
        if (current->key == key) {
            return current->value;
        }
        current = current->next;
    }
    return defaultvalue;
}

template <class k, class v, class hf>
inline bool chashtable<k, v, hf>::remove(k key)
{
    size_t index = hashfunc(key) % bucketsize;
    hashnode<k, v>* current = buckets[index];
    hashnode<k, v>* currentafter = current->next;
    while (current != nullptr) {
        if (current->key == key) {
            delete current;
            current = nullptr;
            buckets[index] = currentafter;
            return true;
        }
        current = current->next;
        currentafter = current->next;
    }
    return false;
}

template <class k, class v, class hf>
inline void chashtable<k, v, hf>::print()
{
    for (size_t i = 0; i < bucketsize; ++i)
    {
        hashnode<k, v>* current = buckets[i];
        while (current != nullptr) {
            hashnode<k, v>* todelete = current;
            current = current->next;
            cout << todelete->value << " ";
        }
    }
    cout << endl;
}

#endif // chash_h

#include "chash.h"
using namespace std;

int main(int argc, char**argv) {
    chashtable<keytype, valuetype> ht(10); // 创建一个大小为10的哈希表
    ht.insert("1", "one");
    ht.insert("2", "two");
    ht.insert("11", "eleven");
    ht.insert("2", "two3");

    cout << ht.find("2") << endl;
    ht.print();
    ht.remove("2");
    cout << ht.find("1") << endl;
    cout << ht.find("2") << endl;
    cout << ht.find("11") << endl;
    ht.print();
    return 0;
}

对应stl：

   unordered_set，unordered_multiset，unordered_map，multimap这四种容器的共同点是：底层使用了哈希表，容器中的元素是一个无序的序列。

   网络上有对 map vs unordered_map 效率对比的测试，通常 map 增删元素的效率更高，unordered_map 访问元素的效率更高，另外，unordered_map 内存占用更高，因为底层的哈希表需要预分配足量的空间。其它 xxx 和 unordered_xxx 区别也一样。

   unordered_xxx 容器更适用于增删操作不多，但需要频繁访问，且内存资源充足的场合。

基于哈希表的集合

• unordered_set

  容器属性：关联容器**，**无序，元素自身即key，元素有唯一性，使用内存分配器动态管理内存，可以自由的插入和删除元素。

• unordered_multiset

  容器属性：关联容器，无序，元素自身即key，允许不同元素值相同，使用内存分配器动态管理内存，是对 unordered_set 的简单拓展。

基于哈希表的映射

• unordered_map

  容器属性：关联容器，无序，元素类型<key, value>，key是唯一的，使用内存分配器动态管理内存。

• unordered_multimap

  容器属性：关联容器，无序，元素类型<key, value>，允许不同元素key相同，使用内存分配器管理内存，unordered_multimap 是对 unordered_map 的拓展。

推荐阅读

c/c++专栏：
（内含其它数据结构及对应stl容器使用）