string - 字符串的哈希函数

Question

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

1. 具有低冲突率(即使对于短字符串也是如此)

2. 可以快速计算(O(n) 时间是必须的，但我希望它尽可能快)

3. 给定 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 上表现不错，但我想知道 如果访问数组中的随机元素太慢。

Answer 1

我建议你使用:

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;