首页 > 编程语言 >C++数据结构之：哈希表Hash

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

时间：2024-06-07 16:33:57浏览次数：23  
标签：Hash 哈希 HashNode C++ next current key unordered

摘要：

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

标签：Hash,哈希,HashNode,C++,next,current,key,unordered
From： https://blog.csdn.net/weixin_45068267/article/details/139476100

相关文章

  • C++数据结构之：图Graph
    摘要：  it人员无论是使用哪种高级语言开发东东，想要更高效有层次的开发程序的话都躲不开三件套：数据结构，算法和设计模式。数据结构是相互之间存在一种或多种特定关系的数据元素的集合，即带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系，分为逻辑结构和存储结......
  • C/C++ 联合体的注意事项
    联合体（Union）在C/C++中是一个特殊的数据类型，它允许在相同的内存位置存储不同的数据类型。联合体的主要特点是，其所有的成员共享同一块内存区域，也就是说，联合体中的各个成员首地址都是相同的。这使得联合体在节省内存、进行数据类型转换等方面非常有用。然而，使用联合体时也需要注意......
  • C++ 模板
    一.非类型模板参数模板参数分为类型形参与非类型形参。类型形参：类作为模板参数，typename/classT(T就是类型形参)非类型形参：内置类型作为模板参数，intdoublechar...(在C++20前只有int可以传)这样我们就可以随便定义栈的大小。注：因为n是常量所以是不能修改的。......
  • 免费，C++蓝桥杯比赛历年真题--第14届蓝桥杯省赛真题（含答案解析和代码）
    C++蓝桥杯比赛历年真题–第14届蓝桥杯省赛真题一、选择题答案：A解析：C++中bool类型与char类型一样，都需要1byte。一些其他类型的占用字节数:short:2byte，int:4byte，longlong:8byte，double:8byte，故答案为A。答案：C解析：A中结构体中可以定义成员变量，也可以定义只有该结......
  • 10_1、C++继承与派生：声明与继承关系
    声明与继承关系继承派生概念派生类声明派生类从基类继承的过程吸收基类成员修改基类成员添加新成员继承关系公有继承保护继承私有继承继承派生概念类的继承就是新类由已经存在的类获得已有特性。类的派生则是由已经存在的类产生新类的过程。由已有类产生新类时，新......
  • 【NOI】C++程序结构入门之循环结构二-for循环
    文章目录前言一、for循环1.导入2.语法3.使用场景4.条件控制5.小结二、例题讲解问题：1264-4位反序数问题：1085-寻找雷劈数问题：1057-能被5整除且至少有一位数字是5的所有整数的个数问题：1392-回文偶数？问题：1090-同因查找问题：1446.人口增长问题三、总结四、感谢......
  • C++ -- 引用
    什么是引用？引用其实就是一个变量的别名。也就是说，你可以通过引用的名称去访问原来的那个变量。其操作符很简单，就是在变量前面加上&。一个很简单的例子：//variableinti;//referencevariablesint&r=i;i=5;cout<<"valueofiis:"<<i<<endl;......
  • C++11原子操作
    目录1.什么是原子操作2.为什么需要原子操作？3.C++中的原子操作4.原子操作使用及注意5.应用场景6.使用原子操作的最佳实践7.原子操作与锁机制的比较8.总结1.什么是原子操作        原子操作是一种不可分割的操作，即在多线程环境中，这些操作要么全部执行完成，要么......
  • C++中的priority_queue和deque以及适配器
    C++中的priority_queue和deque一丶priority_queue1.1priority_queue的介绍1.2priority_queue的使用1.3priority_queue的模拟实现二丶deque2.1deque的简单介绍2.2deque的缺陷2.3为什么要选择deque作为stack和queue的迭代器三丶容器适配器3.1什么是适配器3.2S......
  • C++ Template
    一、Template什么是template？重要性如何？下面我就说道说道：无性生殖不只是存在于遗传工程中，对于程序员而言，它也是一个由来已久的动作。过去，我们只不过是以一个简单而基本的工具，也就是一个文字编辑器，重复的复制代码。今天，C++提供给我们一个更好的繁殖方法：template。复......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99