文章/答案/技术大牛

发布

社区首页 >问答首页 >String散列函数

问String散列函数
EN

Stack Overflow用户

提问于 2013-12-08 02:31:10

回答 2查看 227关注 0票数 1

我需要一个(字节)字符串的散列函数

具有较低的碰撞比(即使是短字符串)
可以快速计算(O(n)时间是必须的，但我希望它尽可能快)
给定hash(string1)和hash(string2)，计算hash(append(string1, string2))可以用O(1)完成。

到目前为止，我能想到的最好的方法是：(用Java伪代码)

public static int[] HASH_ENTROPY = new int[] {...} // 255 large prime numbers

public int hash()
    int hash = 0;
    for (int i=0; i < this.array.length; i++)
       hash += HASH_ENTROPY[this.array[i] + 128];
    return hash;

有没有更好的算法？这个程序在#1和#3中执行得很好，但是我想知道访问数组中的随机元素是否太慢了。

string

algorithm

hash

回答 2

Stack Overflow用户

发布于 2013-12-08 05:38:39

我建议你使用：

public uint32_t hash()
    uint32_t hash = 0x1f351f35; // 2x Barker code
    for (int i=0; i < this.array.length; i++) {
       char c = this.array[i];
       hash = ((hash << 1) | (hash >> 31)) + (HASH_ENTROPY[(uint8_t)(hash + c)] ^ c);
    }
    return hash;

票数 1

Stack Overflow用户

发布于 2013-12-09 16:00:28

此外，如果需要快速计算时间，可以考虑另一个哈希函数：

public uint32_t hash()
    uint32_t hash = 0x1f351f35; // 2x Barker code
    for (int i=0; i < this.array.length; i++) {
       hash += (hash << 4) + this.array[i];
    }
    return hash;

注意:以前的哈希函数使用熵数组；您可以在每个程序开始时通过随机值填充这个数组，因此当外部的人特别使用相同的散列生成多个字符串时，就会出现通用散列，抵抗外部攻击，从而产生您的服务的冲突和DOS。这个功能是快速的，但不能抵抗邪恶的攻击。

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/20449175

复制

相似问题

问String散列函数
EN

回答 2

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问String散列函数EN

回答 2

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问String散列函数
EN