在每个槽中创建一个带有排序链表的哈希映射

Question

我已经成功地在每个槽中制作了一个带有链表和单链表的散列图。当我使用插入时，它将新节点发送到每个链表的后面，但是当我插入一个新节点时，我需要对每个槽进行排序。我如何编辑以下 insert 函数，以便不必在之后对每个插槽进行排序，而是将其插入正确的位置开始？

void hashInsert(int key){
    int hashLoc = h(key);
    HashNode* prev = NULL;
    HashNode* entry = hTable[hashLoc];
    while(entry != NULL){
        prev = entry;
        entry = entry->next;
    }
    if(entry == NULL){
        entry = new HashNode(key);
        if(prev == NULL){
            hTable[hashLoc] = entry;
        }
        else{

            prev->next = entry;
        }
    }
    else{
        entry->value = key;
    }
}

Answer 1

保持每个插槽排序的主要技巧是插入正确的位置，在本例中，该位置恰好在第一个较大值之前。

在您的代码中，您使用以下 while 循环强制在列表末尾插入。

while(entry != NULL){
    prev = entry;
    entry = entry->next;
}

相反，我们想要修改此条件，以便我们也寻找更大的值，而不是简单地查找列表的末尾 (entry == NULL)。

while(entry != NULL && entry->value < value_to_insert){
    prev = entry;
    entry = entry->next;
}

这个经过修改的 for 循环正确地指出了放置新条目的正确位置，就在 prev 和 entry 之间。

这种情况下的另一个问题是您的插入逻辑中有几个错误。

这是你的插入逻辑：

if(entry == NULL){
    entry = new HashNode(key);
    if(prev == NULL){
        hTable[hashLoc] = entry;
    }
    else{

        prev->next = entry;
    }
}
else{
    entry->value = key;
}

主要问题是 if(entry==NULL) if 语句的 else 分支的逻辑无效。

在这种情况下，您需要创建一个新条目，修复 prev 指针并修复 next 指针。

将其重写为以下内容实际上会更简单：

new_entry = new HashNode(key);
new_entry->value = value_to_insert;
if(prev == NULL){
    hTable[hashLoc] = new_entry;
}
else{
    prev->next = new_entry;
}

new_entry->next = entry;

在每个槽中创建一个带有排序链表的哈希映射

Creating a hash map with sorted linked list in each slot

c++

hashtable

singly-linked-list