1

我正在尝试实现这个网站上定义的逻辑。步骤之一是：

  • 将每个服务器字符串散列到几个 (100-200) 无符号整数

但我对此感到困惑。谁能告诉我这意味着什么，以便我可以手动实现逻辑？

// This count is always 2 as per my current setup
int availableservers = Client.getAvailableServers().size();  

String key = "MyKey";
int keyid = key.hashCode();
int v = keyid % 1;
String valess = (String) mcc.get(key,v);
4

3 回答 3

3

您引用的文章包含指向其 SVN 代码库的链接：

svn://svn.audioscrobbler.net/misc/ketama/

在这里，他们似乎包含了一个 Java 实现：

svn://svn.audioscrobbler.net/misc/ketama/java_ketama/SockIOPool.java

在代码中，您会发现以下内容：

for(long j = 0; j < factor; j++) {
  byte[] d = md5.digest((servers[i]+"-"+j).getBytes());
  for(int h=0;h<4;h++) {
    Long k = 
        ((long)(d[3+h*4]&0xFF) << 24)
      | ((long)(d[2+h*4]&0xFF) << 16)
      | ((long)(d[1+h*4]&0xFF) << 8)
      | ((long)(d[0+h*4]&0xFF));
    buckets.put(k, servers[i]);
    log.debug( "++++ added " + servers[i] + " to server bucket" );
  }             
}

factor此代码正在为每个服务器创建一个总哈希值。请注意在散列之前将 的当前值附加j到字符串的 for 循环。server[i]

将此与 Frank Pavageau 的回答结合起来，您应该很快就会明白发生了什么。

于 2012-10-28T08:31:00.903 回答
2

我猜 ketama 哈希是使用 MD5 计算的。我在这里找到了示例实现

public static Long md5HashingAlg(String key) {
  MessageDigest md5 = null;
        try {
            MessageDigest md5 = MessageDigest.getInstance("MD5");
        } catch (NoSuchAlgorithmException e) {
            throw new IllegalStateException( "md5 algorythm found");            
        }
    }
    md5.reset();
    md5.update(key.getBytes());
    byte[] bKey = md5.digest();
    long res = ((long)(bKey[3]&0xFF) << 24) | ((long)(bKey[2]&0xFF) << 16) | ((long)(bKey[1]&0xFF) << 8) | (long)(bKey[0]&0xFF);
    return res;
}
于 2012-10-28T08:29:11.607 回答
1

邓肯是对的，只需检查源代码即可了解此特定实现的工作原理。

但是，从概念上讲，无论使用哪种散列算法，如果您需要基于相同键的多个散列，您所需要做的就是将键与多个“常量”或至少已知且可重复的值连接起来：

String key = "MyKey";
List<Integer> hashes = new ArrayList<>();
for (String s : Arrays.asList("", "extra1", "extra2")) {
    hashes.add((key + s).hashCode());
}

这相当于将散列分布在整数“连续体”周围，以重用文章的术语。所以你也可以这样做，就像你可以实现 hashCode() 一样：

String key "MyKey";
List<Integer> hashes = new ArrayList<>();
int hash = key.hashCode();
for (int i = 0; i < 100; i++) {
    hashes.add(hash);
    hash = 31 * hash + 1234567;
}
于 2012-10-28T08:38:56.157 回答