編程實現哈希存儲算法的簡單實例

編程實現哈希存儲算法的簡單實現實例。

通過編寫一個簡單的哈希實例來加強對哈希算法的理解。下面實例包括存儲與查找算法。拉鏈法解決沖突問題。

如果時間長了對哈希算法的理論知識不夠了解，可以先閱讀前面轉載的兩篇文檔：

字符串哈希到整數函數，算法 ：http://www.linuxidc.com/Linux/2014-05/101600.htm

Hash算法沖突解決方法分析 ：http://www.linuxidc.com/Linux/2014-05/101601.htm

--------------------------------------分割線 --------------------------------------

2014阿裡實習面試題——哈希的原理和Java中HashMap如何實現的 http://www.linuxidc.com/Linux/2014-04/100598.htm

哈希連接(hash join) 原理 http://www.linuxidc.com/Linux/2013-11/92483.htm

C++中對hash_map自定義哈希函數和比較函數的理解 http://www.linuxidc.com/Linux/2012-11/73706.htm

--------------------------------------分割線 --------------------------------------

// 假設現在要實現一個存儲學生信息的hash內存表，封裝hash值的存儲與獲取，並通過拉鏈法解決地址沖突。
#include <stdio.h>
#include <string>
using std::string;

// 定義hash表初始開辟內存空間元素的個數。這裡只用1000做測試。
#define BUFF_COUNT 1000

// 學生信息結構
struct Student_info
{
        string name;
        int age;
};

// 實際存儲元素結構
struct Store_info
{
      string key;                                    // 將key做存儲，目的是為了判斷沖突問題
        struct Student_info stu;                        // 實際需要存儲的數據信息
        Store_info *pNext;                              // 當發生沖突時用以形成鏈表
        Store_info():pNext(NULL){}
};
Store_info *buff;  //之後用於申請大片存儲數據的內存

// BKDRHash函數，得到一個字符串所對應的整型，用於計算hash值。此函數見：http://www.linuxidc.com/Linux/2014-05/101600.htm
unsigned int BKDRHash(char *str)
{
    unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
    unsigned int hash = 0;
    while (*str)
    {
        hash = hash * seed + (*str++);
    }
    return (hash & 0x7FFFFFFF);
}

bool Hash_set(string key, const Student_info& student)
{
        // 計算實際的hash值，除以BUFF_COUNT是為了使hash的映射到一個較小的范圍。
        unsigned int hash_index =  BKDRHash((char*)key.c_str())%BUFF_COUNT;

        Store_info *pStore = &buff[hash_index];
        while ((pStore->key != key) && (pStore->pNext != NULL)) // if some key exists, store to the link list
        {
                pStore = pStore->pNext;
        }

        if (pStore->key == key)
        {
                pStore->stu = student;
                return true;
        }

        Store_info *pNewStore = new Store_info();
        pNewStore->key = key;
        pNewStore->stu = student;

        pStore->pNext = pNewStore;
        return true;
}

Student_info* Hash_get(string key)
{
        unsigned int hash_index =  BKDRHash((char*)key.c_str())%BUFF_COUNT;
        Store_info *pStore = &buff[hash_index];
        if ((pStore->key != key) && (pStore->pNext != NULL))
        {
                pStore = pStore->pNext;
        }

        if (pStore->key == key)
        {
                return &pStore->stu;
        }
        return NULL;
}

int main()
{
        buff = new Store_info[BUFF_COUNT];
        Student_info stu1;
        stu1.name = "hu";
        stu1.age = 11;
        Hash_set("key1", stu1);

        Student_info stu2 = stu1;
        stu2.age = 22;
        Hash_set("key2", stu2);

        Student_info stu3 = stu1;
        stu3.age = 33;
        Hash_set("key2", stu3);

        Student_info *pstu = Hash_get("key2");
        if (pstu == NULL)
        {
                        printf("ERROR:Get NULL\n");
        }
        else
        {
                        printf("name:%s\nage:%d\n",pstu->name.c_str(),pstu->age);
        }

        printf("end~\n");
        delete[] buff;
        return 0;
}

如有任何問題，希望各位指正，謝謝。