请教关于异或哈希 (Xorhash)中seed的用法

muench 发布于 2周前 | 更新于 1周前
tinyfool 等1人欣赏。
  • 用于:现有一包含一系列words的linked listA,和一个作为dictionary的linked listB. 比较list A哪些词是没有出现在list B中。

  • 思路:根据listB建一个hash table, 然后再hash list A查找。目前暂定用学校老师提起的 xorhash (Zobl & Ramakrishnan, 1997)版本解决这项作业。

  • 问题:不知道版本中seed的用法和选值

    希望指教,十分感谢。


Xorhash (Zobl & Ramakrishnan, 1997) 提供代码如下:

unsigned int xorhash(char word[], int seed, int hash_size){
    int i;
    char c;
    unsigned int h;

    h = seed;
    for(i=0;(c=string[i])!='';i++){
        h = h^((h<<5)+c+(h>>2)); 
    }
    return((unsigned int)(h%hash_size));
}

另外: 在stack over flow Dan Bernstein 提供的版本中 5381是否就等同于第一个版本中的seed? 在实际操作中这个seed的取值是否可固定?

Xorhash (Dan Bernstein, 1997) 提供代码如下:

unsigned long
hash(unsigned char *str)
{
    unsigned long hash = 5381;
    int c;

    while (c = *str++)
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

    return hash;
}
共2条回复
jokester 回复于 2周前

怎样选hash中的seed是个很复杂的问题. 作为作业我觉得可以简单地选一个效果不坏的 (比如在你测试数据中hash重复较少的).

seed一般是固定的 (考虑难度/收益/软件行为往往需要跨进程跨机器一致 等因素...)

muench 回复于 1周前

1楼 @jokester 非常感激您的回答,对本人很有帮助,谢谢您。

登录 或者 注册
相关帖子
最新帖子