我正在复习哈希表的工作原理,因此我了解哈希函数如何计算唯一的(出于此问题的目的)哈希表值以与存储值一起使用,因此当搜索存储值时哈希函数给计算机哈希表值。
好的,现在我们有了哈希表的值,但是这样更好吗?在找到匹配的哈希表值之前,我们是否仍然需要遍历?
我正在复习哈希表的工作原理,因此我了解哈希函数如何计算唯一的(出于此问题的目的)哈希表值以与存储值一起使用,因此当搜索存储值时哈希函数给计算机哈希表值。
好的,现在我们有了哈希表的值,但是这样更好吗?在找到匹配的哈希表值之前,我们是否仍然需要遍历?
哈希函数将用于直接映射到数组中的索引。所以没有搜索或迭代完成
哈希表存储在一个数组中。哈希值映射到数组索引。根据实现,哈希值要么是数组索引,要么是一个更大范围的数字,取模数组的大小。
然后,一旦它查看数组中的那个点,它必须检查那里的值是否匹配,因为多个值可能具有相同的哈希值。通常,它实际上导航所有已散列到散列表中同一位置的值的链接列表。这是一个比完整列表短得多的列表(特别是如果哈希表的大小与其中的数据量成正比)。
有很多不同的哈希表,每个都有不同的实现细节,但最简单的哈希表使用哈希码作为数组的索引:
#define TABLESIZE 1000
char **gHashTable[TABLESIZE];
void clearHashTable() {
memset(gHashTable, 0, sizeof(gHashTable));
}
int calculateHashCode(char *string) {
int val = 0;
for (int i = 0; string[i] != '\0'; ++i)
val += string[i];
return val;
}
void insertInHash(char *string) {
int hashCode = calculateHashCode(string);
gHashTable[hashCode % TABLESIZE] = string;
}
int isInHashTable(char *string) {
int hashCode = calculateHashCode(string);
return gHashTable[hashCode % TABLESIZE] != 0;
}
现在这个简单的哈希支持对字符串的快速查找。它不能很好地处理冲突,散列函数很糟糕,还有许多其他问题,但它会起作用。