散列表（Hash table，也叫哈希表），是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過把關(guān)鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。

給定表M，存在函數(shù)f(key)，對任意給定的關(guān)鍵字值key，代入函數(shù)后若能得到包含該關(guān)鍵字的記錄在表中的地址，則稱表M為哈希（Hash）表，函數(shù)f(key)為哈希(Hash) 函數(shù)。

若關(guān)鍵字為k，則其值存放在f(k)的存儲位置上。由此，不需比較便可直接取得所查記錄。稱這個對應(yīng)關(guān)系f為散列函數(shù)，按這個思想建立的表為散列表。
對不同的關(guān)鍵字可能得到同一散列地址，即k1≠k2，而f(k1)==f(k2)，這種現(xiàn)象稱為沖突（英語：Collision）。具有相同函數(shù)值的關(guān)鍵字對該散列函數(shù)來說稱做同義詞。綜上所述，根據(jù)散列函數(shù)f(k)和處理沖突的方法將一組關(guān)鍵字映射到一個有限的連續(xù)的地址集（區(qū)間）上，并以關(guān)鍵字在地址集中的“像”作為記錄在表中的存儲位置，這種表便稱為散列表，這一映射過程稱為散列造表或散列，所得的存儲位置稱散列地址。
若對于關(guān)鍵字集合中的任一個關(guān)鍵字，經(jīng)散列函數(shù)映象到地址集合中任何一個地址的概率是相等的，則稱此類散列函數(shù)為均勻散列函數(shù)（Uniform Hash function），這就是使關(guān)鍵字經(jīng)過散列函數(shù)得到一個“隨機(jī)的地址”，從而減少沖突

sample_hashmap.h:

// 創(chuàng)建日期：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; // 桶的初始數(shù)量
?? ?int buckets_size; // 桶的數(shù)量
?? ?int keys_count; // key的數(shù)量
?? ?vector<Node<T>>buckets; // 不定義成指針類型，免去初始化的步驟
?? ?int hashfun(T val); // 哈希函數(shù)
public:
?? ?HashTable();
?? ?~HashTable();
?? ?int& operator[](int index) const; // 重載[]運(yùn)算符，哈希表暫時用不到
?? ?void insert(T val); // 插入
?? ?void erase(T val); // 刪除
?? ?bool find(T val); // 尋找
?? ?void expand(); // 擴(kuò)容
?? ?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; // 數(shù)組元素是結(jié)構(gòu)體對象，.next調(diào)出結(jié)構(gòu)體成員.
    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;
}

到此這篇關(guān)于C++實(shí)現(xiàn)哈希散列表的示例的文章就介紹到這了,更多相關(guān)C++ 哈希散列表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: