c - 带链表的哈希表

Question

我在学校练习时遇到了麻烦。

我必须使用这种结构实现哈希表:

struct Book {
char * title;
char * author;
int price;
struct Book * next;
}

所以我必须创建一个函数 initTable() 来创建我的哈希表，它是一个包含 1000 个元素的结构书表。所以我的功能是:

struct Book* initTable(){
struct Book *tab = malloc(sizeof(struct Book) * 1000);
return tab;
}

请注意，该函数应该返回我的表的第一个元素。但是我不知道这个语法是否正确。

所以我的问题是:

1. 语法正确吗？

2. 如何在表格中导航？例如，如果我想转到表格的第 50 个单元格，我该怎么办？

然后，如果我的哈希表中存在冲突，我必须创建一个链接列表，将我的元素放入冲突的位置。但是我表的每个单元格都是一个结构而不是这个结构的指针，所以我不明白如何链接我的元素。

Answer 1

哈希表旨在在恒定时间内通过键查找集合中的条目。在实现方面，这通常由对象指针的“隐藏”数组(不是对象本身)组成。然后，您需要一个将键转换为数组查找索引(整数)的散列函数。例如:

ValueObjectType **createHashTable(int hashSize)
{
    ValueObjectType **table = malloc( sizeof(ValueObjectType *) * hashSize);
    return table;
}

void hashInsert(ValueObjectType **hashTable, KeyObjectType key, ValueObjectType *value)
{
    int arrayIndex = hashingFunction(key);
    if ( hashTable[arrayIndex] != NULL ) traverseLinkedListAndAdd(...);
    else hashTable[arrayIndex] = value;
}

ValueObjectType *lookupByKey(ValueObjectType **hashTable, KeyObjectType key)
{
    int arrayIndex = hashingFunction(key);
    return traverseLinkedListAndReturnObjectWithKey(...);        
}

散列函数通常涉及获取一个或多个关键元素(可以是任何类型)并将它们转换为单个整数值，然后通过对散列数组大小取模将其转换为数组索引。

Book 结构中链表的目的是处理散列冲突。哈希冲突发生在插入时，因为给定的键已经存在于哈希中(在这种情况下，您应该用新对象替换值对象引用)或者因为哈希函数的非唯一性。当后者发生时，链表用于存储具有不同键的多个条目，这些键散列到相同的数组索引(通常通过遍历列表，如果看到键相等则替换列表的元素，否则添加新对象最后)。

在上面的示例代码中，我有一个单独的键对象，但为了评估键的相等性，它需要包含在对象本身中(我怀疑在你的情况下键是标题和作者的某种组合) ，或包装在元结构中(例如包含指向键和值的指针的“KeyValue”结构，您将散列而不是 ValueObjectType)。您需要提供逻辑来评估两个键的相等性/不相等性，以便正确处理哈希冲突情况。

我在这里未指定散列函数、链表导航和关键相等逻辑，因为这显然是您的导师希望您学习如何做的。