hashtable - 为什么计算机不必进行比较搜索来查找哈希表值？

Question

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

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

Answer 1

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

Answer 2

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

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

Answer 3

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

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

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