1

我正在复习哈希表的工作原理,因此我了解哈希函数如何计算唯一的(出于此问题的目的)哈希表值以与存储值一起使用,因此当搜索存储值时哈希函数给计算机哈希表值。

好的,现在我们有了哈希表的值,但是这样更好吗?在找到匹配的哈希表值之前,我们是否仍然需要遍历?

4

3 回答 3

2

哈希函数将用于直接映射到数组中的索引。所以没有搜索或迭代完成

于 2012-11-20T20:46:58.373 回答
1

哈希表存储在一个数组中。哈希值映射到数组索引。根据实现,哈希值要么是数组索引,要么是一个更大范围的数字,取模数组的大小。

然后,一旦它查看数组中的那个点,它必须检查那里的值是否匹配,因为多个值可能具有相同的哈希值。通常,它实际上导航所有已散列到散列表中同一位置的值的链接列表。这是一个比完整列表短得多的列表(特别是如果哈希表的大小与其中的数据量成正比)。

于 2012-11-20T20:49:49.430 回答
0

有很多不同的哈希表,每个都有不同的实现细节,但最简单的哈希表使用哈希码作为数组的索引:

#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;
}

现在这个简单的哈希支持对字符串的快速查找。它不能很好地处理冲突,散列函数很糟糕,还有许多其他问题,但它会起作用。

于 2012-11-20T20:53:22.403 回答