良好的字符串哈希函数

Question

我正在尝试为字符串想出一个好的哈希函数。我认为总结字符串中前五个字符的 unicode 值可能是个好主意（假设它有五个，否则在结束处停止）。这是一个好主意，还是一个坏主意？

我正在用 Java 做这件事，但我认为这不会产生太大的影响。

Answer 1

通常哈希值不会求和，否则 stop 和 pots 将具有相同的哈希值。

并且您不会将其限制为前 n 个字符，因为否则 house 和 house 将具有相同的哈希值。

一般来说，散列采用值并将其乘以素数（使其更有可能生成唯一的散列），因此您可以执行以下操作：

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

Answer 2

如果是安全问题，您可以使用 Java 加密：

import java.security.MessageDigest;

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

Answer 3

您可能应该使用 String.hashCode() 。

如果你真的想自己实现 hashCode：

不要试图排除
物体的重要部分来自
哈希码计算改进
性能——Joshua Bloch，《Effective Java》

仅使用前五个字符是一个坏主意。考虑一下分层名称，例如 URL：它们都将具有相同的哈希代码（因为它们都以“http://”开头，这意味着它们存储在哈希映射中的同一个存储桶下，表现出糟糕的性能。

这里是一个战争故事，根据“Effective Java”中的字符串 hashCode 进行解释：

实现的字符串哈希函数
在 1.2 之前检查的所有版本中
最多十六个字符，均匀
在整个字符串中间隔，开始
与第一个字符。对于大型
分层名称的集合，
比如 URL，这个哈希函数
表现出可怕的行为。

Answer 4

如果您在 Java 中执行此操作，那么您为什么要这样做？只需对字符串调用 .hashCode()

Answer 5

Guava 的 HashFunction (javadoc）提供了不错的非加密-强哈希。

Answer 6

Nick提供的这个函数很好，但是如果使用new String(byte[] bytes)来转换为String，则失败。您可以使用此功能来做到这一点。

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());
}

也许这可以帮助某人

Answer 7

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

对于长字符串（例如，超过 200 个字符），您可以通过 获得良好的性能MD4 哈希函数。作为一种加密功能，它大约在 15 年前就被破解了，但对于非加密目的来说，它仍然非常好，而且速度快得惊人。在 Java 环境中，您必须将 16 位 char 值转换为 32 位字，例如将这些值分组为对。 MD4 在 Java 中的快速实现可以在 sphlib。在课堂作业中可能有点矫枉过正，但在其他方面值得一试。

Answer 8

// 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;
}

来源
djb2 哈希函数背后的逻辑 - SO

Answer 9

如果您想查看行业标准实现，我会查看 java.security.MessageDigest。

“消息摘要是一种安全的单向哈希函数，它采用任意大小的数据并输出固定长度的哈希值。”

Answer 10

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;
}

Answer 11

         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();
}

Answer 12

这将避免任何碰撞，并且在我们在计算中使用移位之前它会很快。

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

Answer 13

在尝试为字符串开发良好的哈希函数时，最好使用奇数。这个函数接受一个字符串并返回一个索引值，到目前为止它的工作效果很好。并且碰撞较少。索引范围从 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 乘以索引，因为它会增加，例如“熊”字
(0*b) + (1*e) + (2*a) + (3*r) 这会给你一个 int 值来使用。上面的第一个哈希函数在“这里”和“听到”发生冲突，但仍然擅长提供一些良好的独特值。下面的字符不会与“这里”和“听到”冲突，因为我将每个字符与索引相乘，随着索引的增加。

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;
}

Answer 14

这是一个简单的哈希函数，我将其用于构建的哈希表。它基本上用于获取文本文件并将每个单词存储在代表字母顺序的索引中。

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