字符串的良好哈希函数

Question

我正在尝试为字符串设想一个好的哈希函数.而且我认为总结字符串中前五个字符的unicode值可能是一个好主意(假设它有五个,否则在它结束时停止).这是一个好主意,还是一个坏主意？

我在Java中这样做,但我不认为这会产生很大的不同.

Answer 1

通常哈希不会做算术,否则stop和pots将具有相同的哈希值.

并且你不会将它限制在前n个字符,因为否则房屋和房屋将具有相同的哈希值.

通常,散列取值并乘以素数(使其更有可能生成唯一的散列)所以你可以这样做:

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(stringToEncrypt.getBytes());
String encryptedString = new String(messageDigest.digest());

Answer 3

您应该使用String.hashCode().

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

不要试图从哈希码计算中排除对象的重要部分以提高性能 - Joshua Bloch,Effective Java

仅使用前五个字符是个坏主意.想想层次名称,如URL:他们都将有相同的散列码(因为他们都开始以"http://",这意味着它们被存储在一个哈希表一样斗下,表现出可怕的性能.

这是一篇关于来自" Effective Java " 的String hashCode的战争故事:

在1.2之前的所有版本中实现的String散列函数检查最多16个字符,在整个字符串中均匀分布,从第一个字符开始.对于大型分层名称集合(例如URL),此哈希函数显示可怕的行为.

Answer 4

如果你用Java做这个,那么你为什么要这样做呢？只需调用.hashCode()字符串即可

Answer 5

GuavaHashFunction(javadoc)提供了不错的非加密散列.

Answer 6

Nick提供的这个函数很好但是如果你使用新的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

// 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 8

有传言说FNV-1是一个很好的字符串散列函数。

对于长字符串（长于大约200个字符），可以通过MD4哈希函数获得良好的性能。作为一种加密功能，它大约在15年前就被打破了，但是出于非加密目的，它仍然非常好，而且速度惊人。在Java上下文中，您将必须将16位char值转换为32位字，例如，通过将这些值分组为对。可以在sphlib中找到Java中MD4的快速实现。在课堂分配的情况下，可能会造成过大的杀伤力，但值得一试。