अंतिम अद्यतन：2026-10-12

STL स्वहस्त लिखी हैश तालिका कार्यान्वयन¶

0.प्रस्तावना¶

उद्देश्य: स्वयं हाथ से एक हैश तालिका कार्यान्वित करना, जिसमें श्रृंखलन विधि (separate chaining) से निर्माण हो तथा प्रत्येक hash(key) के संगत एक रेड-ब्लैक ट्री हो।

देखने में सरल लगता है, पर इसमें बहुत कुछ सीखने को मिलता है। कार्यान्वयन भाषा: C++।

एल्गोरिद्म की नींव मज़बूत करने के लिए github पर एक रिपॉज़िटरी बनाई गई है, जिसमें आगे एल्गोरिद्म आधार के अनुप्रयोग तथा कार्यान्वयन पूरे किए जाएँगे। पता:

https://github.com/Light-City/algPratice

मूल लेख पर क्लिक करके भी पढ़ा जा सकता है।

1.सरल संस्करण हैश तालिका¶

हम हैश तालिका को एक क्लास में लपेटते हैं, तथा traversal की परिभाषा-घोषणा के साथ-साथ कंस्ट्रक्टर तथा डिस्ट्रक्टर का कार्यान्वयन पूरा करते हैं:

template<typename Key, typename Value>
class HashTable {
private:
    const static int upperTol = 3;
    const static int lowerTol = 1;
    const static int initCapacity = 1;
    map<Key, Value> **hashtable;
    int M;
    int size;
public:
    /**
     * 传参构造
     * @param M
     */
    HashTable(int M) : M(M), size(0) {
        // 这里的括号是为了初始化为0,这就可以不用写下面的代码,当然在后面add之类的操作,就不需要动态分配内存.
        // this->hashtable = new map<Key, Value> *[M]();
        this->hashtable = new map<Key, Value> *[M];
        for (int i = 0; i < M; i++) {
            this->hashtable[i] = new map<Key, Value>;
        }
    }

    /**
     * 默认构造
     */
    HashTable() {
        HashTable(initCapacity);
    }

    /**
     * 析构函数,释放内存
     */
    ~HashTable() {
        free(M);
    }
private:
    /**
     * 释放内存
     * @param M
     */
    void free(int M) {
        for (int i = 0; i < M; i++) {
            if (hashtable[i])
                delete hashtable[i];
        }
        delete[]hashtable;

};

हैश तालिका के कार्यान्वयन में एक अपेक्षाकृत महत्वपूर्ण हैश फंक्शन होता है; यहाँ हम पहले स्वयं एक परिभाषित करते हैं:

/**
* 哈希函数
* @param key
* @return
*/
int hashFunc(Key key) {
    std::hash<Key> h;
    return (h(key) & 0x7fffffff) % M;
}

यहाँ std के hash से मान प्राप्त करने के बाद, उसे 0x7fffffff से & करके उच्च बिट का ऋणचिह्न हटाकर धनात्मक संख्या बनाया जाता है, फिर M से शेषफल लिया जाता है।

अब इन सबके साथ हम इसके जोड़ना, हटाना, बदलना तथा खोजना कार्यान्वित करते हैं।

जोड़ने का ऑपरेशन (add)

अंतर्निहित रूप से रेड-ब्लैक ट्री उपयोग होता है; इंसर्शन insert विधि से, एक pair का निर्माण करके किया जाता है। और जब key पहले से मौजूद हो, तो केवल मान अद्यतन (update) करना होता है; अद्यतन के लिए सीधे insert उपयोग करना काम नहीं करता, जैसे नीचे के परीक्षण में:

 map<string,int> m{{"a",1},{"b",2}};
for(auto i:m) cout<<i.first<<" "<<i.second<<" ";
cout<<endl;
m.insert({{"a",2}});
for(auto i:m) cout<<i.first<<" "<<i.second<<" ";
cout<<endl;
m["a"]=2;
for(auto i:m) cout<<i.first<<" "<<i.second<<" ";
cout<<endl;

आउटपुट:

a 1 b 2 
a 1 b 2 
a 2 b 2

अतः यदि key के संगत value बदलनी हो, तो [] द्वारा बदला जा सकता है, या पहले डिलीट करके दोबारा इंसर्ट भी किया जा सकता है — यहाँ इसी विधि का उपयोग किया गया है।

/**
* 添加新元素
* @param key
* @param value
*/
void add(Key key, Value value) {
    // 拉链法出来的map如果为空,就动态分配一个map,然后进行插入
    // 如果key不存在就看内存是否存在,不存在,就分配,存在就插入
    if (hashtable[hashFunc(key)] == NULL || hashtable[hashFunc(key)]->count(key) == 0) {
        if (hashtable[hashFunc(key)] == NULL)
            hashtable[hashFunc(key)] = new map<Key, Value>;
        hashtable[hashFunc(key)]->insert(make_pair(key, value));
        size++;
        if (size >= maxCapacity())
            resize(2 * M);
    } else {
        // 否则,修改value.
        hashtable[hashFunc(key)]->erase(key);
        hashtable[hashFunc(key)]->insert(make_pair(key, value));
    }
}

हटाने का ऑपरेशन (remove)

यदि key मौजूद है तो डिलीट करें तथा size--, अन्यथा असफलता का चिह्न लौटाएँ।

/**
* 移除Key
* @param key
* @return 0 success -1 fail
*/
Value remove(Key key) {
    Value ret = -1;
    // 是否包含key,若包含key,则直接删除
    if (contains(key)) {
        hashtable[hashFunc(key)]->erase(key);
        size--;
    //            if (size == 0) delete hashtable[hashFunc(key)];       // 可以添加这行来动态减少内存
        ret = 0;
        // initCapacity 保证不会越界
        if (size < minCapacity() && M / 2 >= initCapacity) resize(M / 2);
    }
    return ret;
}

बदलने का ऑपरेशन (set)

आगे उल्लेख हो चुका है, यहाँ सीधे कोड रख देते हैं।

/**
* 重设value
* @param key
* @param value
*/
void set(Key key, Value value) {
    // key不存在
    if (!contains(key))
        hrow "key not exists!";
    // 修改value
    hashtable[hashFunc(key)]->erase(key);
    hashtable[hashFunc(key)]->insert(make_pair(key, value));
}

खोजने का ऑपरेशन (get)

key के संगत value प्राप्त करना।

/**
* 获取key对应的value
* @param key
* @return
*/
Value get(Key key) {
    if (contains(key))
        return hashtable[hashFunc(key)]->at(key);
    return 0;
}

अंत में, ऊपर contains तथा resize जैसे कुछ फंक्शन्स का उल्लेख नहीं हुआ।

key मौजूद है या नहीं

सबसे पहले contains फंक्शन का कार्यान्वयन — यही जाँचता है कि key मौजूद है या नहीं:

/**
    * 是否包含key
    * @param key
    * @return
    */
bool contains(Key key) {
    return hashtable[hashFunc(key)] == NULL || this->hashtable[hashFunc(key)]->count(key) == 0 ? false : true;
}

size प्राप्त करना

/**
* 获取哈希表元素个数
* @return
*/
int getSize() {
    return size;
}

अधिकतम क्षमता तथा न्यूनतम क्षमता

/**
    * 最大容量
    * @return
    */
Value maxCapacity() {
    return M * upperTol;
}

/**
    * 最小容量
    * @return
    */
Value minCapacity() {
    return M * lowerTol;
}

resize फंक्शन

मेमोरी का गतिशील समायोजन पूरा करता है — मूल मेमोरी की सामग्री को नए आवंटित स्पेस में कॉपी किया जाता है और मूल स्पेस जारी कर दिया जाता है!

/**
* 动态调整内存,保证时间复杂度O(1)查找
* 把扩容后的操作,平摊到前面每次操作,时间复杂度O(2),那就是O(1)了
* @param newM
*/
void resize(int newM) {
    cout << "resize " << newM << endl;
    map<Key, Value> **newHashTable = new map<Key, Value> *[newM];
    for (int i = 0; i < newM; i++) {
        newHashTable[i] = new map<Key, Value>;
    }
    int oldM = M;
    this->M = newM;
    for (int i = 0; i < oldM; i++) {
        map<Key, Value> m = *(hashtable[i]);
        for (auto p:m)
            newHashTable[hashFunc(p.first)]->insert(make_pair(p.first, p.second));
    }

    free(oldM);
    this->hashtable = newHashTable;
}

<< ऑपरेटर का ओवरलोड

घोषणा:

private:
    template<typename K, typename V>
    // 重载<<操作符
    friend ostream &operator<<(ostream &out, HashTable<K, V> &hashTable);

परिभाषा:

template<typename K, typename V>
ostream &operator<<(ostream &out, HashTable<K, V> &hashTable) {
    hashTable.print();
    return out;
}

इस प्रकार उपरोक्त हैश तालिका का कार्यान्वयन पूरा हुआ; अब परीक्षण करते हैं:

#include "hash.h"
#include <vector>
int main() {

    vector<string> words{"java", "c++", "c", "c++", "c#", "python", "ruby", "python",
                         "c", "c", "c++", "java", "c++", "rust", "python"};
    HashTable<string, int> ht(1);
    for (string word : words) {
        if (ht.contains(word)) {
            ht.set(word, ht.get(word) + 1);
        } else {
            ht.add(word, 1);
        }
    }
    cout<<ht;
    cout<<"size="<<ht.getSize()<<",maxCapacity="<<ht.maxCapacity()<<",minCapacity="<<ht.minCapacity()<<endl;
    string w="c++";
    ht.remove(w);
    if (ht.contains(w))
        cout << "" << w << ": " << ht.get(w) << endl;
    else
        cout << "No word " << w << " in words" << endl;
    cout<<ht;
    ht.remove("c#");
    ht.remove("java");
    ht.remove("c");
    cout<<"size="<<ht.getSize()<<",maxCapacity="<<ht.maxCapacity()<<",minCapacity="<<ht.minCapacity()<<endl;
    cout<<ht;

    return 0;
}

आउटपुट परिणाम:

resize 2
resize 4
{c#:1,java:2,ruby:1,c:3,rust:1,python:3,c++:4}
size=7,maxCapacity=12,minCapacity=4
No word c++ in words
{c#:1,java:2,ruby:1,c:3,rust:1,python:3}
resize 2
size=3,maxCapacity=6,minCapacity=2
{python:3,ruby:1,rust:1}

इस प्रकार एक सरल हैश तालिका पूरी हो गई।

1.अनुकूलित हैश तालिका¶

gcc2.9 संस्करण में अंतर्निहित हैश तालिका की क्षमता अभाज्य संख्याओं के रूप में गतिशील रूप से संशोधित होती थी, इसीलिए यहाँ का अनुकूलन इसी बिंदु से शुरू होता है:

क्लास के भीतर आरंभ में निम्नलिखित array जोड़ें:

// 素数数组
const vector<int> capacity = {53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317,
                                196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843,
                                50331653, 100663319, 201326611, 402653189, 805306457, 1610612741};

पैरामीटर वाला कंस्ट्रक्टर हटाकर, डिफ़ॉल्ट कंस्ट्रक्टर को इस प्रकार बदलें:

/**
* 默认构造
* @param M
*/
HashTable()  {
    M = capacity[capacityIndex], size = 0;
    // 这里的括号是为了初始化为0,这就可以不用写下面的代码,当然在后面add之类的操作,就不需要动态分配内存.
    // this->hashtable = new map<Key, Value> *[M]();
    this->hashtable = new map<Key, Value> *[M];
    for (int i = 0; i < M; i++) {
        this->hashtable[i] = new map<Key, Value>;
    }
}

add फंक्शन बदलें: size++ के बाद निम्नलिखित कोड जोड़ें:

if (size >= maxCapacity() && capacityIndex + 1 < capacity.size()) {
    capacityIndex++;
    resize(capacity[M]);
}

प्रत्येक बार resize में capacity से मान लिया जाता है।

remove फंक्शन का संशोधन

size-- के बाद यह संशोधन करें:

if (size < minCapacity() && capacityIndex - 1 >= 0) {
    capacityIndex--;
    resize(capacityIndex);
}

इस प्रकार हैश तालिका पूरी हो गई! परीक्षण कोड वही है जो ऊपर दिया गया है।

STL स्वहस्त लिखी हैश तालिका कार्यान्वयन¶

0.प्रस्तावना¶

1.सरल संस्करण हैश तालिका¶

1.अनुकूलित हैश तालिका¶

संबंधित विषय¶

टिप्पणियाँ