字符串的好散列函数

小开

最佳答案

通常散列不做求和，否则 stop和 pots将具有相同的散列。

你不会把它限制在第一个 n 个字符，因为否则 house 和 house 会有相同的 hash。

一般来说，散列取值并乘以一个质数(这样更有可能产生唯一的散列) ，所以你可以这样做:

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

小开

如果你在 Java 中这样做，那么你为什么要这样做呢? 只要在字符串上调用 .hashCode()

小开

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

小开

您可能应该使用 HashCode ()。

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

不要试图排斥物体的重要部分要改进的哈希码计算性能——约书亚 · 布洛赫，高效 Java

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

下面是“ 有效的爪哇”中字符串 hashCode 的一个战争故事:

实现的 String 散列函数在1.2审核前的所有版本最多十六个字，均匀在整个字符串的间隔，开始第一个字符。为大等级名称的集合, 例如 URL，这个散列函数表现出可怕的行为。

小开

如果是安全方面的问题，你可以使用 Java 加密:

import java.security.MessageDigest;


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

小开

如果您希望看到行业标准实现，我将查看 Java.security. MessageDigest。

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

小开

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

对于长字符串(比如长于大约200个字符) ，可以使用 MD4散列函数获得良好的性能。作为一个加密函数，它在大约15年前就被破解了，但是对于非加密目的，它仍然非常好，而且速度惊人地快。在 Java 的上下文中，您必须将16位的 char值转换为32位的单词，例如将这些值分组成对。可以在 Sphlib中找到 Java 中 MD4的快速实现。可能在课堂作业的背景下有些夸张，但是其他方面值得一试。

小开

Nick 提供的这个函数很好，但是如果使用新的 String (byte [] byte)进行到 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());
}

也许这能帮到别人

小开

番石榴的 HashFunction (Javadoc)提供了不错的非加密强散列。

小开

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

小开

在尝试为字符串开发一个好的 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;
}

你可以做的另一件事就是把每个字符整型解析乘以索引，就像“ bear”一样 (0 * b) + (1 * e) + (2 * a) + (3 * r)这会给你一个整型值。上面的第一个散列函数在“ 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;
}

小开

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

小开

下面是一个简单的散列函数，我用它来构建一个散列表。它的基本功能是获取一个文本文件，并将每个单词存储在一个表示字母顺序的索引中。

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。这样做有一个好处，你可以轻松快速地计算出一个给定的单词在哈希表中的索引位置，因为它全部都在一个字母顺序中，比如: 代码可以在这里找到: < a href = “ https://github.com/abhiitcpatil/general”rel = “ nofollow norefrer”> 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