c - 带链表的哈希表

Question

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

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

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

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

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)。您需要提供逻辑来评估两个键的相等/不相等，以便正确处理哈希冲突情况。

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