双星阵列

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。否则怎么他们会在那里结束？

编辑：因此，空项是用作输入预先存在的“预告片” ......