双重哈希的开放寻址

问题描述 投票：0回答：1

双重哈希的开放寻址

似乎无法正确理解。某些隐藏的情况下有错误（输入和输出都看不到），所以我想看看是否有人可以帮助发现错误。

我正在通过双重哈希实现一个开放寻址哈希表来执行插入和删除。下面给出哈希槽的结构，在main函数中创建了一个有37个哈希槽的哈希表

提供哈希函数。 

hash2()
是用于双重哈希的增量哈希函数。

两个函数的返回值分别是插入和删除时进行的键比较次数。插入重复键将返回 -1。如果键比较的次数大于表的大小，则表示表已满。对于删除函数，如果删除键不存在，则返回-1。删除时的key比较次数不能超过table size

#include <stdio.h>
#include <stdlib.h>

#define TABLESIZE 37
#define PRIME     13

enum Marker {EMPTY,USED,DELETED};

typedef struct _slot{
    int key;
    enum Marker indicator;
} HashSlot;

int HashInsert(int key, HashSlot hashTable[]);
int HashDelete(int key, HashSlot hashTable[]);


int hash1(int key);
int hash2(int key);

int main()
{
    int opt;
    int i;
    int key;
    int comparison;
    HashSlot hashTable[TABLESIZE];

    for(i=0;i<TABLESIZE;i++){
        hashTable[i].indicator = EMPTY;
        hashTable[i].key = 0;
    }

    printf("============= Hash Table ============\n");
    printf("|1. Insert a key to the hash table  |\n");
    printf("|2. Delete a key from the hash table|\n");
    printf("|3. Print the hash table            |\n");
    printf("|4. Quit                            |\n");
    printf("=====================================\n");
    printf("Enter selection: ");
    scanf("%d",&opt);
    while(opt>=1 && opt <=3){
        switch(opt){
        case 1:
            printf("Enter a key to be inserted:\n");
            scanf("%d",&key);
            comparison = HashInsert(key,hashTable);
            if(comparison <0)
                printf("Duplicate key\n");
            else if(comparison < TABLESIZE)
                printf("Insert: %d Key Comparisons: %d\n",key, comparison);
            else
                printf("Key Comparisons: %d. Table is full.\n",comparison);
            break;
        case 2:
            printf("Enter a key to be deleted:\n");
            scanf("%d",&key);
            comparison = HashDelete(key,hashTable);
            if(comparison <0)
                printf("%d does not exist.\n", key);
            else if(comparison <= TABLESIZE)
                printf("Delete: %d Key Comparisons: %d\n",key, comparison);
            else
                printf("Error\n");
            break;
        case 3:
            for(i=0;i<TABLESIZE;i++) printf("%d: %d %c\n",i, hashTable[i].key,hashTable[i].indicator==DELETED?'*':' ');
            break;
        }
        printf("Enter selection: ");
        scanf("%d",&opt);
    }
    return 0;
}

int hash1(int key)
{
    return (key % TABLESIZE);
}

int hash2(int key)
{
    return (key % PRIME) + 1;
}

int HashInsert(int key, HashSlot hashTable[])
{
    int hash = hash1(key);
    int i = 0;
    int comparisons = 0;

    while (hashTable[hash].indicator == USED && hashTable[hash].key != key && i < TABLESIZE) {
        hash = (hash + hash2(key)) % TABLESIZE;
        i++;
        comparisons++;
    }

    if (hashTable[hash].key == key&&hashTable[hash].indicator == USED) {
        return -1;  // Key already exists
    }

    if (i >= TABLESIZE) {
        return comparisons ;  // Table is full, count initial comparison
    }

    hashTable[hash].key = key;
    hashTable[hash].indicator = USED;
    return comparisons ;  // Count initial comparison
}

int HashDelete(int key, HashSlot hashTable[])
{
    int hash = hash1(key);
    int i = 0;
    int comparisons = 1;

    while (hashTable[hash].indicator != EMPTY && i < TABLESIZE) {
        if (hashTable[hash].indicator == USED && hashTable[hash].key == key) {
            hashTable[hash].indicator = DELETED;
            return comparisons;
        }
        hash = (hash + hash2(key)) % TABLESIZE;
        i++;
        comparisons++;
    }

    return -1;  // Key not found
}
c hash
1个回答
2
投票

插入密钥时不考虑墓碑

标记为已删除的插槽（即墓碑）意味着“链”尚未终止并且必须继续搜索密钥，直到到达 

EMPTY
插槽或用尽所有插槽。

在您的示例中删除密钥时，这是正确完成的：搜索密钥仅在到达 

EMPTY
插槽而不是 
DELETED
插槽时停止。

然而，插入钥匙时没有这样做。在这种情况下，插入可以分解为两部分

  1. 通过探测找到插入点
    这是通过在探测链中找到第一个未使用的插槽来完成的（你做对了）
  2. 在哈希表中搜索重复项
    这是通过继续搜索前面描述的密钥（你错过了）来完成的

注意，一旦所有槽至少被使用一次，每次插入都会进行最大次数的键比较（所有键都必须被搜索）
为了防止这种情况，需要重新散列/重新定位插槽以将 

DELETED
插槽恢复为 
EMPTY
这似乎超出了您的练习范围。

下面是更正后的代码，我们首先找到插入点并单独保存，然后再继续搜索重复项。

int HashInsert(int key, HashSlot hashTable[])
{
    int hash = hash1(key);
    int insertAt, i = 0;
    int comparisons = 0;

    while (hashTable[hash].indicator == USED && hashTable[hash].key != key && i < TABLESIZE) {
        hash = (hash + hash2(key)) % TABLESIZE;
        i++;
        comparisons++;
    }
    if (i >= TABLESIZE) {
        return comparisons ;  // Table is full, count initial comparison
    }

    insertAt = hash;   // Save the insertion point first
    // We will continue probing till the end (i.e. hitting an EMPTY slot)
    // to check if the key is indeed not in the hashTable

    while (hashTable[hash].indicator != EMPTY && i < TABLESIZE) {
        if (hashTable[hash].indicator == USED) {    // Do a key compare if slot is in use
            comparisons++;
            if (hashTable[hash].key == key) // Key already exists
                return -1;
        }
        hash = (hash + hash2(key)) % TABLESIZE;
        i++;
    }

    hashTable[insertAt].key = key;
    hashTable[insertAt].indicator = USED;
    return comparisons ;  // Count initial comparison
}

删除键时
comparisons
的错误计数

这是一个小错误，但是您在删除键时错误地计算了比较次数。
不应该在墓碑上进行关键比较，下面是更正后的代码。

int HashDelete(int key, HashSlot hashTable[])
{
    int hash = hash1(key);
    int i = 0;
    int comparisons = 0;    // Number of comparisons should start from 0

    while (hashTable[hash].indicator != EMPTY && i < TABLESIZE) {
        if (hashTable[hash].indicator == USED) {
            comparisons++;      // Only compare when the slot is USED
            if (hashTable[hash].key == key) {
                hashTable[hash].indicator = DELETED;
                return comparisons;
            }
        }
        hash = (hash + hash2(key)) % TABLESIZE;
        i++;
    }

    return -1;  // Key not found
}
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.