devbox
知新_RL
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C++数据结构之：哈希表Hash_c++ hash

作者：知新_RL | 2024-07-20 09:37:19

赞

踩

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

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
#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;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

在这里插入图片描述

对应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++专栏：https://blog.csdn.net/weixin_45068267/category_12268204.html
（内含其它数据结构及对应STL容器使用）

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号