良好的string散列函数
我试图想出一个好的散列函数的string。 我认为总结string中前五个字符的unicode值可能是一个好主意（假设它有五个，否则停止它的结束）。 这是一个好主意，还是一个坏主意？
我在Java中这样做，但我不会想象这会有很大的不同。
通常哈希不会做总和，否则stop和pots将具有相同的散列。
你不会把它限制在前n个字符，因为否则房子和房子就会有相同的散列。
一般来说，散列值取值并将其乘以一个素数（使得它更可能产生独特的散列）所以你可以这样做：
int hash = 7; for (int i = 0; i < strlen; i++) { hash = hash*31 + charAt(i); }
如果这是一个安全的事情，你可以使用Javaencryption：
import java.security.MessageDigest; MessageDigest messageDigest = MessageDigest.getInstance("SHA-256"); messageDigest.update(stringToEncrypt.getBytes()); String encryptedString = new String(messageDigest.digest());
你应该使用String.hashCode（） 。
如果你真的想自己实现hashCode：
不要试图从散列码计算中排除对象的重要部分以提高性能 – Joshua Bloch，Effective Java
只使用前五个字符是一个坏主意 。 考虑分层名称，比如URL：它们将具有相同的哈希码（因为它们全部以“http：//”开头，这意味着它们被存储在哈希映射中的同一个桶中，performance出可怕的性能。
下面是从“ Effective Java ”的String hashCode转述的战争故事：
在1.2之前的所有版本中实现的String散列函数最多检查16个字符，在整个string中均匀分布，从第一个字符开始。 对于大量的分层名称集合（如URL），此散列函数显示出糟糕的行为。
如果你在Java中这样做，那么你为什么这样做呢？ 只需在string上调用.hashCode()
番石榴的 HashFunction （ jsdoc ）提供了体面的非encryption强哈希。
Nick提供的这个函数是好的，但是如果你使用新的String（byte []字节）来进行String的转换，那么失败了。 你可以使用这个function来做到这一点。
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; }
djb2哈希函数背后的 源 逻辑 – SO
据传FNV-1是一个很好的string散列函数。
对于长string（比200个字符长），您可以从MD4哈希函数中获得良好的性能。 作为一个密码function，它在15年前就被破解了，但是对于非密码的目的来说，它仍然是非常好的，而且非常快。 在Java的上下文中，您必须将16位char值转换为32位字，例如将这些值分组成对。 Java中的MD4的快速实现可以在sphlib中find。 在课堂作业中可能是过度的，但是值得一试。
sdbm：这个algorithm是为sdbm（ndbm的一个公共域重新实现）数据库库创build的
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; }
如果你想看看行业标准的实现，我会看看java.security.MessageDigest 。
“消息摘要是安全的单向散列函数，可以获取任意大小的数据并输出固定长度的散列值。”
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(); }
这里有一个链接 ，解释了许多不同的散列函数，现在我更喜欢ELF散列函数为您的特定问题。 它需要input一个任意长度的string。
这里有一个简单的哈希函数，我用它来创build一个哈希表。 它基本上是为了获取文本文件，并将每个单词存储在一个表示字母顺序的索引中。
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的散列键。这是一个优点; 你可以很容易和快速地计算给定单词在散列表中的位置，因为它的全部按字母顺序排列，如下所示：代码可以在这里find： https ： //github.com/abhijitcpatil/general
提供以下文本作为input：有一天，阿迪克斯对杰姆说： “我宁愿你在后院开枪打锡jar，但我知道你会追赶鸟。 拍摄所有你想要的蓝色小鸟，如果你能击中他们，但记住杀死一只嘲鸟是一种罪过。“那是我唯一听过阿迪克斯说要做某件事是一种罪过的事情，我问莫迪小姐它。 “你父亲是对的，”她说。 “只有让音乐让我们享受，模仿鸟才会做一件事。 他们不吃人的花园，不要窝在玉米仓里，他们不做一件事，而是为我们唱出心声。 这就是为什么杀死一只模仿鸟是一种罪过。
这将是输出：
0 --> aa about asked and a Atticus aa 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
在为string开发一个良好的函数时，最好使用奇数。 这个函数接受一个string并返回一个索引值，到目前为止它的工作还算不错。 并且有较less的碰撞。 指数的范围从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乘以索引，因为它增加像“bear”（0 * b）+（1 * e）+（2 * a）+（3 * r）这个词会给你一个int值来玩。 上面的第一个哈希函数碰撞在“这里”和“听到”，但仍然很好给予一些很好的独特的价值。 下面的一个不会与“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; }
