3

在我的 C 程序中，我在一个结构中分配了四个 8 位 ( char ) 变量。如果我想对这些数字进行哈希处理以创建索引数组的键（代表整个结构），我该怎么办？（在程序中有很多这样的结构；因为我经常需要在符号表中搜索它们是否存在，如果我不想创建其他的，我不知道使用哪种哈希算法，如果我'想要做一个键索引搜索）。

我考虑过一种散列方法，它采用四个数字，将它们转换为十六进制数字，将它们连续放置，然后将输出的数字转换为十进制数字。

但是我需要一些不那么“沉重”的东西……这种方法似乎太虚荣了，我认为它不太适合创建数组索引。

是吗？如果可能的话，是否还有另一种哈希函数，它占用的内存也少于 32 位？

4

4 回答 4

2

一种可能性（我不认为 OP 正在描述）是将 4 个 char 值组合成一个 32 位整数，然后用哈希表的大小（可能是质数）对其进行修改：

unsigned int combined = (c1 << 24 ) | (c2 << 16 ) | (c3 << 8 ) | (c4);
unsigned int hashval = combined % hashtablesize;

它当然取决于 4 个单独字节的实际预期值，但这种类型的散列相当有效并且通常具有良好的分布。最好用预期的数据集测试生成的哈希值，以确保分布有点均匀。

于 2012-05-16T17:29:33.713 回答
2

您可能想看看这个散列函数列表。

为了实现哈希表（我想这是您的目标），您需要一个具有雪崩效应的哈希函数来避免类似输入值的过多哈希冲突。

当然，您可以使用任何函数将您的字符转换为任意整数表示，但如果此表示对于不同的输入没有变化，则您实际上具有链表的性能（想象使用表大小为的其他建议之一256 并且没有任何结构在字节 4 上变化）。您对 32 位哈希有什么顾虑？当然你会使用hash%tablesize索引？

通常您也不会使用加密散列函数（例如 md5、sha-1）。只需选择一种非加密散列函数（例如 Pearson/Jenkins 散列）。

/* jenkins hash, copied from http://en.wikipedia.org/wiki/Jenkins_hash_function */
uint32_t jenkins_one_at_a_time_hash(char *key, size_t len)
{
  uint32_t hash, i;
  for(hash = i = 0; i < len; ++i)
  {
    hash += key[i];
    hash += (hash << 10);
    hash ^= (hash >> 6);
  }
  hash += (hash << 3);
  hash ^= (hash >> 11);
  hash += (hash << 15);
  return hash;
}

旁注：当您拥有良好的哈希值分布时，还要确保哈希表的大小足够大。随着数组的占用率（负载因子）接近 1，您将观察到性能下降，因为哈希冲突的可能性会增加。

于 2012-05-16T19:11:07.367 回答
0

为什么不将结构放入数组中？

#include <stdio.h>

typedef struct {
  char a,b,c,d;
} item;
item items[20];

int main(int argc, char *argv[])
{
  items[0].a = 4;
  items[0].b = 6;
  items[0].c = 1;
  items[0].d = 3;
  // ...
  items[4].a = 12;
  // ...
  printf("%d %d %d %d\n", items[0].a, items[0].b, items[0].c, items[0].d);
  return 0;
}

显然，这是内存占用较少的解决方案，因为数据直接存储在主数组中，因此不需要散列索引，因为数组的索引可以在不消耗内存的情况下完成这项工作。

当然，您可以使用指针、一些 C++ 向量功能等。但这是最简单有效的方法。

唯一需要注意的是，您必须知道数组的大小（您将拥有多少项目）或不超过 XXX 的最大值......

于 2012-05-16T17:36:21.657 回答
0

如果可能的话，是否还有另一种哈希函数，它占用的内存也少于 32 位？

这是一个虚幻的问题。键是一个数组索引——它不存储在任何地方，它是在查找时计算的。C 中的数组是连续的块，根据数组的开头和类型的大小乘以索引来访问各个元素。

对于键，只需将值转换为无符号的 32 位类型（不要只使用int或unsigned int，因为大小不一定是 32 位）：

#include <inttypes.h>
char x[4] = { 'A', 'B', 'C', 'D' };
uint32_t *key = (uint32_t*)&x;

然后根据表格大小做模数。

于 2012-05-16T17:54:45.297 回答