雙星陣列

Question

這可能不是合適的詞，所以如果任何人都可以告訴我這個數據類型實際上被稱爲，那將不勝感激。

我有一個編程任務，在這個任務中我必須實現一個哈希映射作爲教授這樣的一個拖尾鏈表的數組。

LN** map = nullptr; 

該數組的每個索引都應該從尾部節點開始，這就是我遇到問題的地方。每當我嘗試將數組長度加倍時，代碼以某種方式將數量相等的尾部節點放在索引爲零的數組的長度上。在我做了一堆插入之後，哈希映射通常看起來像這樣。

// # Represents nullptr 
// pair[,] is a trailer. 
map m = bin[0]: pair[,] -> pair[,] -> pair[,] -> pair[,] -> pair[,] -> pair[,] -> pair[,] -> pair[,] -> # 
     bin[1]: pair[Shirley,Peanutbuttercup] -> pair[,] -> # 
     bin[2]: pair[Nicholas,Kafka] -> pair[,] -> # 
     bin[3]: pair[,] -> # 
     bin[4]: pair[Sora,Phammyy] -> pair[,] -> # 
     bin[5]: pair[Selv,Anthony] -> pair[,] -> # 
     bin[6]: pair[,] -> # 
     bin[7]: pair[,] -> # 

這很奇怪，考慮到我的代碼加倍數組是。

bins *= 2; 
map = new LN*[bins]; 
for (int i=0; i<bins; i++) { 
    map[i] = new LN(); 
} 

while (!q.empty()) { 
    Entry e = q.dequeue(); 
    int hash = hash_compress(e.first); 
    map[hash] = new LN(e, map[hash]); 
} 

我不希望任何人能夠調試我的代碼（雖然在起飛的機會，任何人都可以，那將是巨大的），但我會很感激，如果任何人都可以詳細介紹一下這個數據類型，以便我可以更好地找出我搞砸的地方。如果你想保持你的PROFS一個「拖」節點的概念

LN被定義爲

private: 
    class LN { 
    public: 
     LN()       : next(nullptr){} 
     LN (const LN& ln)    : value(ln.value), next(ln.next){} 
     LN (Entry v, LN* n = nullptr) : value(v), next(n){} 

     Entry value; // typedef ics::pair<KEY,T> Entry; declared earlier 
     LN* next; 
    }; 

Answer 1

，下面的代碼將做到這一點。我建議強烈反對「拖車」節點的想法，因爲它購買你沒有，只是使列表管理更繁瑣。你的教授本質上是告訴你把什麼假設是一個碰撞列表，但你的東西放在什麼東西永遠不會碰撞任何東西。 NULL是一個很好的列表結束標記，我建議你改用它。

我相信最重要的東西是而不是在構建新地圖時添加舊地圖的預告片節點。我相信他們都映射到零槽，而你卻一味把它們放到你的新地圖中。換句話說，在重新調整碰撞列表時，您並未忽略無用的預告片節點。

下面的代碼是對有效率，你會得到這樣，無需中間隊列，沒有節點複製，只有換湯不換藥現有節點，這將是移動（其指針）的新表：

// double the size of the hash table. 
unsigned int old_bin = bin; 
bin *= 2; 
LN** new_map = new LN*[bin](); 

// load new set of trailers into new map 
for (unsigned int i=0; i<bin; ++i) 
    new_map[i] = new LN(); 

// walk the old table (0..old_bin-1) rehashing and 
// moving existing nodes to new slots in the hash table. 
for (unsigned int i=0; i<old_bin; ++i) 
{ 
    // without the "trailer node", this should just be (map[i]) 
    while (map[i]->next) 
    { 
     // pull node from old collision list at i 
     LN *p = map[i]; 
     map[i] = p->next; 

     // rehash to new table based on new table size 
     unsigned int idx = hash_compress(p->value.first); 
     p->next = new_map[idx]; 
     new_map[idx] = p; 
    } 

    // delete trailer node (better be the last one) 
    delete map[i]; 
} 

delete [] map; 
map = new_map; 

那就是它。這將是相當更清潔，沒有所有的拖車節點瘋狂，但你可以把你的教授帶上。如果您將NULL用於碰撞列表標記而不是一些虛構的拖車節點，那麼將近一半的代碼會消失。我會恭敬地作爲你的助手爲什麼他認爲把什麼東西這不是碰撞在碰撞列表是一個好主意（因爲它不是）。

Answer 2

int hash = hash_compress(e.first); 

您在0處得到很多散列值。您是否檢查空輸入？如果散列總是被認爲是有效的，那麼如何區分有效和無效輸入？

正如您的表格所示。

map m = bin[0]: pair[,] -> pair[,] -> pair[,] -> pair[,] -> pair[,] -> pair[,] -> pair[,] 

您的代碼

map[hash] = new LN(e, map[hash]); 

是產生這些，因爲e是空的，因此哈希值始終爲0。否則怎麼他們會在那裏結束？

編輯：因此，空項是用作輸入預先存在的「預告片」 ......