C++实现哈希散列表的示例

Bianca ·

更新时间:2024-09-20

· 394 次阅读

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

给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希（Hash）表，函数f(key)为哈希(Hash) 函数。

若关键字为k，则其值存放在f(k)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数，按这个思想建立的表为散列表。

对不同的关键字可能得到同一散列地址，即k1≠k2，而f(k1)==f(k2)，这种现象称为冲突（英语：Collision）。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述，根据散列函数f(k)和处理冲突的方法将一组关键字映射到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便称为散列表，这一映射过程称为散列造表或散列，所得的存储位置称散列地址。

若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数（Uniform Hash function），这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突

sample_hashmap.h:

// 创建日期：2022-07-13
// 作者：YZM
// 参考：https://github1s.com/ACking-you/my_tiny_stl/blob/HEAD/src/Data_struct_tool/HashTable/sample_HashMap.h
#pragma once
#ifndef SAMPLE_HASHMAP_H
#define SAMPLE_HASHMAP_H
#include<iostream>
#include<vector>
using namespace std;
template<typename T>
struct Node {
    Node* next;
    T val;
    Node() :next(nullptr), val(0) {};
    Node(T _val) :next(nullptr), val(_val) {};
    Node(T _val, Node* nxt) :next(nxt), val(_val) {};
};
template<typename T>
class HashTable {
private:
    const static int init_buckets_size = 49; // 桶的初始数量
    int buckets_size; // 桶的数量
    int keys_count; // key的数量
    vector<Node<T>>buckets; // 不定义成指针类型，免去初始化的步骤
    int hashfun(T val); // 哈希函数
public:
    HashTable();
    ~HashTable();
    int& operator[](int index) const; // 重载[]运算符，哈希表暂时用不到
    void insert(T val); // 插入
    void erase(T val); // 删除
    bool find(T val); // 寻找
    void expand(); // 扩容
    void clear(); // 清空并释放资源
    void print(); // 打印检查
};
#endif

sample_hashmap.cpp:

#include "sample_hashmap.h"
using namespace std;
template<typename T>
HashTable<T>::HashTable():buckets_size(init_buckets_size), keys_count(0), buckets(vector<Node<T>>(init_buckets_size)){}
template<typename T>
HashTable<T>::~HashTable() {
    clear();
}
template<typename T>
int HashTable<T>::hashfun(T val) {
    return val % buckets_size;
}
template<typename T>
void HashTable<T>::insert(T val) {
    int key = hashfun(val);
    Node<T>* newNode = new Node<T>(key);
    newNode->next = buckets[key].next;
    buckets[key].next = newNode;
    ++keys_count;
    expand();
}
template<typename T>
void HashTable<T>::erase(T val) {
    int key = hashfun(val);
    Node<T>* cur = buckets[key].next; // 数组元素是结构体对象，.next调出结构体成员.
    Node<T>* pre = nullptr;
    while (cur) {
        if (cur->val == val) {
            if (pre == nullptr) {
                buckets[key].next = cur->next;
                delete cur;
            }
            else {
                pre->next = cur->next;
                delete cur;
            }
            return;
        }
        pre = cur;
        cur = cur->next;
    }
    --keys_count;
}
template<typename T>
bool HashTable<T>::find(T val) {
    int key = hashfun(val);
    Node<T>* cur = buckets[key].next;
    while (cur) {
        if (cur->val == val) return true;
        cur = cur->next;
    }
    return false;
}
template<typename T>
void HashTable<T>::clear() {
    for (int i = 0; i < buckets_size; ++i) {
        Node<T>* cur = buckets[i].next;
        while (cur) {
            Node<T>* pre = cur;
            cur = cur->next;
            delete pre;
        }
        buckets[i].next = nullptr;
    }
}
template<typename T>
void HashTable<T>::expand() {
    if (keys_count > buckets_size) {
        buckets_size <<= 1;
        buckets.resize(buckets_size);
    }
}
template<typename T>
void HashTable<T>::print() {
    for (int i = 0; i < buckets_size; ++i) {
        Node<T>* cur = buckets[i].next;
        while (cur) {
            cout << cur->val << ' ';
            cur = cur->next;
        }
    }
    cout << endl;
}
int main() {
    HashTable<int>hash;
    hash.insert(4);
    hash.print();
    hash.clear();
    hash.print();
    hash.insert(4);
    hash.print();
    hash.erase(4);
    hash.print();
    return 0;
}

到此这篇关于C++实现哈希散列表的示例的文章就介绍到这了,更多相关C++ 哈希散列表内容请搜索软件开发网以前的文章或继续浏览下面的相关文章希望大家以后多多支持软件开发网！

c+ 列表示例哈希 C++

1024 个赞