【資料結構】散清單-hash

散清單-hash

散清單的直覺感受就是用一個有幾個分格的書架擺放一堆各種各樣的書。

我們試圖把同一類書放到一起，

又試圖把他們成盡可能多的類，以友善我們能完全按照格子的分類檢索。

對于使用不同分類方法生成的各個分類的集合而言，

分類方法即是散列函數，由散列函數給出某個對象<數字字元等>在這個集合中所屬的類。

這個時候就可以說散清單這個概念了，散清單就是上面那個集合。

哈哈哈這種說法也太次奧了。

設計散列函數

h（key）= code

• 直接定址

  由關鍵詞的某個線性函數獲得位址

• 除留餘數法

  一堆數字 34 456 7 78 231 456 75 423 21 44

  看起來沒有什麼聯系，是否就要用上幾百個位置按他們的值的順序

  放置呢？

  如果讓他們對11取餘，則是完全能把他們分成有限的幾組的

• 數字分析法

  身份證号碼，不同的位上的數字組合代表着不同的意義，根據這些意義我們就能把一些數字分類

• 折疊法

  分割關鍵字後疊加

  如同

  123456

  分割成

  12

  34

  56

  加起來：

  12+34+56 = 102

  就生成了123456對應的分類碼

• 平法取中法

  和前者都是使取定的位更為多變

  <受到更多位上數字的影響-降低沖突機率>

簡單實作

-

聯系實際，牛津詞典就是妙絕的散清單

至少我們使用詞典時不會有“周遊詞典”的奇怪想法

我們會根據某個單詞的拼寫順序檢索字典中對應的部分

這樣，即使考慮到不是一下就能翻到我們想要的那一頁，我們查詞典時翻動的次數在很大程度也取決于單詞的長度，而和詞典中單詞的總量無關。

仿照字典的思路，我們可以完成一個簡單的名字表

把所有人的名字散列成26類，相同類的人名放到一起。

typedef struct hashNode{
public:
    hashNode* _front,*_behind;//節點串接
    string name;
}*hashTable;
           

1、取名字的首拼，取整形對26取餘(衆所周知，英文字母隻有26個)。
2、獲得的整數對26取餘，獲得分類。
3、相同分類的人名組成一個連結清單。
           

int hashFunc(string name)
{
    return ((int)name[0])%26;
}
           

當然，這并不讓人滿意，畢竟相較于可能的人名數量，26這個分類數還是太小，那麼我們可以對人名的第二個字母做同樣的操作，把第一次的分類再分成26組，以此類推，直到你滿意為止。

void addName(hashNode ht[],string& name)
{
    int Loc = hashFunc(name);
    hashTable htxd;
    hashTable htx = &ht[Loc];
    if(htx->name.empty()){
        htx->name = name;cout<<"here0,fill the name you gave at "<<Loc<<endl;
    }else{
        while(htx->_behind != NULL){
            htx = htx->_behind;
        }
        htxd = new hashNode;///malloc和含有string成員的結構沖突<并沒有調用string的 cstr初始化string>
        htx->_behind = htxd;
        htx = htx->_behind;
        if(htx!=NULL)
            htx->name = name;
    }

}