URL的完美哈希函数

Question

有人知道一种适用于大多数URL的64位整数的完美哈希函数吗？

- Kristopher Ives

---

如果这是一个完美的哈希表，按照定义它会有良好的性能表现。 - Ira Baxter

为什么不能使用任何基本的字符串哈希函数？URL只是字符串，对我来说看起来与其他字符串非常相似。如果桶的数量与负载因子相比合理，任何好的字符串哈希函数都应该表现出极高的性能。 - Ira Baxter

@Ira Baxter 抱歉，我的意思是相对于可接受的URL模式，在哈希大小方面表现良好。据我所知，“完美哈希函数”可以在某些输入情况下执行无冲突的映射。 - Kristopher Ives

...对于某些输入。是的，但URL有大量的组合；你是否想要完美哈希的一个小的、有限大小的子集？如果没有，那么你将无法得到完美的哈希函数。真正的问题是，这很重要吗？你没有回答为什么基本的字符串哈希对你不起作用的问题。 - Ira Baxter

@Ira Baxter 你可能想看看http://en.wikipedia.org/wiki/Perfect_hash_function - Kristopher Ives

Answer 1

如果您事先不知道要查询的键集，则无法创建完美的哈希函数。如果您知道，那么您可以使用类似于gperf或cmph的工具为您生成完美的哈希函数。

http://cmph.sourceforge.net/

我认为你不需要使用完美哈希函数，只需使用任何合理的哈希函数，如 murmur hash 或 bob jenkins hash，并结合哈希表实现，例如 __gnu_cxx::hash_map 或来自 google 的 dense_hash_map 和 sparse_hash_map。请注意，保留 HTML 标签。

http://code.google.com/p/google-sparsehash/ http://sites.google.com/site/murmurhash/ http://burtleburtle.net/bob/hash/doobs.html

- Davi

Answer 2

在http://lambdajones.com/b52上发现了这个被标记为"C语言中的Base52 URL缩短器完美哈希函数"的内容。

  const char *b52idx[52] = {
  "0", "1", "2", "3", "4", "5", "6", "7", "8", "9",
  "B", "C", "D", "F", "G", "H", "J", "K", "L", "M",
  "N", "P", "Q", "R", "S", "T", "V", "W", "X", "Y",
  "Z", "b", "c", "d", "f", "g", "h", "j", "k", "l",
  "m", "n", "p", "q", "r", "s", "t", "v", "w", "x",
  "y", "z"
};

#define X 0xff
const int b52map[128] = {
   X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X,
   X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X,
   X, X, X, X, X, X, X, X, X, X, X, X, X, X, X, X,
// 0  1  2  3  4  5  6  7  8  9
   0, 1, 2, 3, 4, 5, 6, 7, 8, 9, X, X, X, X, X, X,
//       B  C  D     F  G  H     J  K  L  M  N
   X, X,10,11,12, X,13,14,15, X,16,17,18,19,20, X,
// P  Q  R  S  T     V  W  X  Y  Z
  21,22,23,24,25, X,26,27,28,29,30, X, X, X, X, X,
//       b  c  d     f  g  h     j  k  l  m  n
   X, X,31,32,33, X,34,35,36, X,37,38,39,40,41, X,
// p  q  r  s  t     v  w  x  y  z
  42,43,44,45,46, X,47,48,49,50,51, X, X, X, X, X
};

#ifdef __GNUC__
#define likely(x) __builtin_expect((x),1)
#else
#define likely(x) (x)
#endif

/*
  valid from 00000 -> zzzzz, good for 380204032 urls
  returns the integral short url id
*/
unsigned long long b52(const char *c) {
  unsigned long long x = 0;
  unsigned long long y = 0;
  unsigned long long z = 0;

  x |= b52map[c[0]] << 24 | b52map[c[1]] << 18 | \
       b52map[c[2]] << 12 | b52map[c[3]] << 6  | b52map[c[4]];

  y += (x/64) * 12;
  if (x > 4095) y += 624 * (x/4096);
  if (x > 262143) y += 32448 * (x/262144);
  if (x > 16777215) y += 1687296 * (x/16777215);

  if (likely((z = x - y) < 380204033)) return z;
  else return 380204033;
}

void b52inc(char *id) {
  int x[5] = {
    b52map[id[0]], b52map[id[1]], b52map[id[2]],b52map[id[3]], b52map[id[4]]
  };
  int y = 5;

  // search for the first character we can increment (51 == 'z')
  // increment from the b52idx table and update id
  while (y--) if (x[y] < 51) break;
  id[y] = *b52idx[++x[y]];

  // if we passed over id's 'z's above, roll them over
  while (y++ < 5) if (x[y] == 51) id[y] = '0';
}

- Kristopher Ives