字符串的良好哈希函数

通常散列不会求和,否则 stop 和 pots 会有同样的杂凑。

你不会把它限制在前n个字符,因为否则house和houses会有相同的散列。

通常哈希值取一个值并乘以一个质数(使它更有可能生成唯一的哈希值),这样您就可以执行如下操作:

int hash = 7;
for (int i = 0; i < strlen; i++) {
    hash = hash*31 + charAt(i);
}

如果是安全问题,可以使用Java加密:

import java.security.MessageDigest;

MessageDigest messageDigest = MessageDigest.getInstance("SHA-256");
messageDigest.update(stringToEncrypt.getBytes());
String encryptedString = new String(messageDigest.digest());

你应该用 String.hashCode() .

如果您真的想自己实现hashcode:

不要试图排除 物体的重要部分 hash码计算的改进 性能——有效Java的Joshua Bloch

只使用前五个字符是 坏主意 . 想想层级名称,比如url:它们都有相同的散列代码(因为它们都以“http://”开头,这意味着它们存储在散列映射中的同一个bucket下,表现出糟糕的性能。

这是一个战争故事,它是从 Effective Java “:

实现的字符串哈希函数 在1.2版本之前的所有版本中 最多16个字符,平均 在整个弦上间隔,开始 第一个角色。为大 层次名称的集合, 例如url,这个散列函数 表现出可怕的行为。

如果你用Java做这件事,那你为什么要这么做呢?只要打电话 .hashCode() 在弦上

Guava's HashFunction ( javadoc )提供适当的非加密强哈希。

nick提供的这个函数很好,但是如果使用新的字符串(byte[]bytes)将转换为字符串,它将失败。你可以用这个函数来做。

private static final char[] hex = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' };

public static String byteArray2Hex(byte[] bytes) {
    StringBuffer sb = new StringBuffer(bytes.length * 2);
    for(final byte b : bytes) {
        sb.append(hex[(b & 0xF0) >> 4]);
        sb.append(hex[b & 0x0F]);
    }
    return sb.toString();
}

public static String getStringFromSHA256(String stringToEncrypt) throws NoSuchAlgorithmException {
    MessageDigest messageDigest = MessageDigest.getInstance("SHA-256");
    messageDigest.update(stringToEncrypt.getBytes());
    return byteArray2Hex(messageDigest.digest());
}

也许这能帮上忙

// djb2 hash function
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;
}

source Logic behind djb2 hash function - SO

FNV-1 据说是一个很好的字符串哈希函数。

对于长字符串(比如,超过200个字符),您可以从 MD4 哈希函数。作为一个加密函数,它在15年前就被破坏了,但是对于非加密目的,它仍然非常好,而且速度惊人。在Java上下文中,您必须转换16位。 char 将值分组成32位字,例如将这些值分组成对。可以在Java中快速实现 sphlib . 可能在课堂作业的背景下有点过火,但在其他方面值得一试。

如果你想看看行业标准的实现,我会看看 java.security.MessageDigest .

“消息摘要是安全的单向哈希函数,它接受任意大小的数据并输出固定长度的哈希值。”

sdbm:此算法是为sdbm(ndbm的公共域重新实现)数据库库创建的

static unsigned long sdbm(unsigned char *str)
{   
    unsigned long hash = 0;
    int c;
    while (c = *str++)
            hash = c + (hash << 6) + (hash << 16) - hash;

    return hash;
}

这里是 a link 这解释了许多不同的散列函数,现在我更喜欢elf散列函数来解决您的特定问题。它接受任意长度的字符串作为输入。

         public String hashString(String s) throws NoSuchAlgorithmException {
    byte[] hash = null;
    try {
        MessageDigest md = MessageDigest.getInstance("SHA-256");
        hash = md.digest(s.getBytes());

    } catch (NoSuchAlgorithmException e) { e.printStackTrace(); }
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < hash.length; ++i) {
        String hex = Integer.toHexString(hash[i]);
        if (hex.length() == 1) {
            sb.append(0);
            sb.append(hex.charAt(hex.length() - 1));
        } else {
            sb.append(hex.substring(hex.length() - 2));
        }
    }
    return sb.toString();
}

这样可以避免任何碰撞,而且在计算中使用移位之前,速度会很快。

 int k = key.length();
    int sum = 0;
    for(int i = 0 ; i < k-1 ; i++){
        sum += key.charAt(i)<<(5*i);
    }

在为字符串开发一个好的hast函数时,使用奇数是一个好主意。这个函数接受一个字符串并返回一个索引值,到目前为止它的工作还不错。碰撞更少。指数范围在0-300之间,甚至可能更大,但我到目前为止还没有得到任何更高的指数,即使是用“机电工程”这样的长词。

int keyHash(string key)
{
    unsigned int k = (int)key.length();
    unsigned int u = 0,n = 0;

    for (Uint i=0; i<k; i++)
    {
        n = (int)key[i];
        u += 7*n%31;
    }
    return u%139;
}

另一件事,你可以做的是将int parse中的每个字符乘以索引,就像单词“bear”一样。 (0*b)+(1*e)+(2*a)+(3*r),这会给你一个int值。上面的第一个散列函数在“here”和“hear”处发生冲突,但仍然擅长给出一些好的惟一值。下面的一个不会与“here”和“hear”冲突,因为随着索引的增加,我会将每个字符与索引相乘。

int keyHash(string key)
{
    unsigned int k = (int)key.length();
    unsigned int u = 0,n = 0;

    for (Uint i=0; i<k; i++)
    {
        n = (int)key[i];
        u += i*n%31;
    }
    return u%139;
}

这里有一个简单的哈希函数,我用它来创建一个哈希表。它的基本功能是获取文本文件并将每个单词存储在表示字母顺序的索引中。

int generatehashkey(const char *name)
{
        int x = tolower(name[0])- 97;
        if (x < 0 || x > 25)
           x = 26;
        return x;
}

这基本上是根据单词的第一个字母进行哈希运算。所以,以“a”开头的单词将得到0的散列键,“b”将得到1,依此类推,“z”将是25。数字和符号的散列键为26。这提供了一个优势;您可以方便快速地计算给定单词在哈希表中的索引位置,因为它都是按字母顺序排列的,如下所示: 代码可以在这里找到: https://github.com/abhijitcpatil/general

输入以下文本: 阿提库斯有一天对杰姆说:“我宁愿你朝后院的罐头罐开枪,但我知道你会去的。” 追鸟。如果你能击中所有的蓝鸟 记住,杀死知更鸟是一种罪恶。那是我唯一一次 有没有听过阿提库斯说做某事是一种罪恶,我问过小姐 莫迪说的。她说:“你父亲是对的。”嘲鸟不会 做一件事除了做音乐给我们欣赏。他们不吃东西 人民花园,不要在玉米窝里筑巢,他们不会做一件事 但为我们唱出他们的心。这就是为什么杀死一个 嘲鸟。

这将是输出:

0 --> a a about asked and a Atticus a a all after at Atticus
1 --> but but blue birds. but backyard
2 --> cribs corn can cans
3 --> do don’t don’t don’t do don’t do day
4 --> eat enjoy. except ever
5 --> for for father’s
6 --> gardens go
7 --> hearts heard hit
8 --> it’s in it. I it I it’s if I in
9 --> jays Jem
10 --> kill kill know
11 --> 
12 --> mockingbird. music make Maudie Miss mockingbird.”
13 --> nest
14 --> out one one only one
15 --> people’s
16 --> 17 --> right remember rather
18 --> sin sing said. she something sin say sin Shoot shot said
19 --> to That’s their thing they They to thing to time the That to the the tin to
20 --> us. up us
21 --> 
22 --> why was was want
23 --> 
24 --> you you you’ll you
25 --> 
26 --> “Mockingbirds ” “Your ‘em “I’d