制作哈希表

1 回答

• 0

  哈希表具有恒定的大小

  ...不一定 - 哈希表可以支持调整大小，但这往往是在相当戏剧性和侵入性的块中完成的，你可以在其中推理哈希表，就像它在前后都是恒定大小一样 .

  ...相当于其哈希函数输出大小可存储的最大值键值对大小桶大小溢出桶大小 . 因此，例如，如果散列函数产生16位哈希值且桶大小为4且值为32位则则为2 ^ 16 * 4 * 6 = 1572864或1.5MB加上溢出 .

  一点也不 . 计算大小的更好方法是说有一定大小的N值，并且你想要保持容量：大小比例介于3：1和5：4之间：表内存使用率为：N * sizeof（Value ）*比率 .

  散列值中的位数仅与之相关，因为它表示您可以散列到的不同桶的最大数量：如果您尝试使用更大的表，那么您将获得比使用更广泛的散列函数更多的冲突位哈希值 . 如果您的哈希函数中的位数多于您需要的位数，那么这不是问题，例如，使用当前表大小的模数来查找您的存储桶： hashed_to_bucket = hash_value % num_buckets .

  这实质上会使哈希表成为一种压缩查找表 .

  这是查看哈希表的好方法 .

  如果散列函数发生更改，则必须重新评估整个表 . 否则它只是添加空插槽的东西 .

  绝对重新评估/重新生成 . 否则添加到空槽只是不良后果之一 .

  此外，哈希表可以包含其散列大小可以解决的最大单位（因此对于16位散列，其为65536）但是如果没有多次冲突就能很好地执行，那么它必须要少得多 .

  如上所述，那个（例如65536）并不是一个硬性最大值，但应该避免"to perform well without collisions" . 为了表现良好 does not 必须要少得多：如果它是一个高质量的16位散列函数，任何高达65536的东西都是完美的 .

  好的，这是我试图索引的东西:(最多）1亿对，64位整数键和96位值 . 键是对象ID（主要是短序列，但可以遍布整个地方），值是对象的位置长度 . 读/写同样重要且非常频繁 . 我调查的其他选项是各种树，但我不喜欢它们的原因是因为在我看来，我将不得不做很多稀疏的读/写来查找数据或每次重构树进去 .

  可能......很大程度上取决于您的访问模式 . 例如，如果您碰巧尝试按照“短序列”访问密钥，那么往往将它们放在内存/磁盘附近的数据组织模型会有所帮助 . 某些类型的树结构做得很好，你有时也可以破解你的哈希函数来做它（但需要 balancer 它碰撞倾向） .

  在我看来，我需要一个带有奇怪位数的哈希，我想到~38因为它只是我可以存储在单个磁盘上的最大值，并且应该足够舒适100百万 . 这个奇怪的位数是闻所未闻的吗？我想我可能会在CPU之前出现磁盘活动方式的瓶颈 .

  不是这样......你有64位整数键 - 需要64位或更大的散列 . 也就是说，32位散列也可能很好 - 产生40亿个不同的值，大于你的1亿个键 .

  那里有关于如何为我的特定情况设计一个好的哈希函数的文章吗？谷歌搜索给了我一个常见方法的概述，但我正在寻找它们背后的解释 .

  不是我知道的 .

  我应该知道的任何其他一般提示/陷阱？

  对于提示...我会说开始简单（例如，使用散列函数返回密钥不变并使用具有哈希表容量的模数为素数，或者使用任何常见哈希，如果您正在获取哈希表实现，使用例如2个幂的桶数并测量你的碰撞率：它告诉你在改善你的散列方面需要付出多少努力 .

  在你的情况下获得“理想的，随机的”散列的一种非常简单的方法是拥有8个256个32位整数的表 - 用硬编码的随机数初始化（你可以谷歌搜索随机数下载网站） . 给定任何64位密钥，只需将其切成8个字节，然后将每个字节用作连续表中的密钥，对您查找的32位值进行异或 . 然后，64个输入位中的任何一个中的单个位差将以相等的概率影响散列值中的所有32位 .

  uint32_t table[8][256] = { ...add some random numbers... };
  
  uint32_t h(uint64_t n)
  {
      uint32_t result = 0;
      unsigned char* p = (unsigned char*)&n;
  
      for (int i = 0; i < 8; ++i)
          result ^= table[i][*p++];
  
      return result;
  }
  

  回复于 2024-04-20T22:30:54+08:00