良好的字符串散列函数

Question

我想为字符串想好散列函数。我认为总结字符串中前五个字符的unicode值可能是个好主意（假设它有五个字符，否则停止它的结束位置）。这是一个好主意，还是一个坏主意？

我在Java中这样做，但我不会想象这会有很大的不同。

Answer 1

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

并且您不会将其限制为前n个字符，因为否则房屋和房屋将具有相同的散列。

一般hashs取值和一个素数相乘（使得它更容易产生独特的哈希值），所以，你可以这样做：

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

Answer 2

如果你在Java中这样做，那么为什么你正在做？只需拨打.hashCode()的字符串

Answer 3

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

Answer 4

你或许应该使用String.hashCode()。

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

不要试图排除 对象的显著部分从 的哈希码计算，以提高性能 - 约书亚布洛赫有效的Java

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

这里有一个战争的故事从“Effective Java”转述对String的hashCode：

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

Answer 5

如果它是一个安全的事情，你可以使用Java加密：

import java.security.MessageDigest; 

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

Answer 6

如果你想看到的行业标准实现，我想看看java.security.MessageDigest。

“消息摘要是安全的单向散列函数，可以获取任意大小的数据并输出固定长度的散列值。“

Answer 7

FNV-1被传言是字符串好的哈希函数。

对于长字符串（长于比方说，约200字），你可以得到很好的表现出来的MD4散列函数。作为密码函数，它在大约15年前就被破解了，但是对于非加密目的，它仍然非常好，而且速度惊人。在Java的上下文中，你必须将16位的值转换为32位的字，例如通过将这些值分组成对，在Java中快速实现MD4可以在sphlib中找到。可能在教室任务的上下文中过度使用，但其他值得一试。

Answer 8

Nick提供的这个函数很好，但是如果你使用新的String（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()); 
} 

可能这可以帮助别人

Answer 9

Guava's HashFunction（jsdoc）提供体面的非加密散列强。

Answer 10

  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 11

它是一个好主意，当尝试开发一个良好的字符串函数时使用奇数。这个函数接受一个字符串并返回一个索引值，到目前为止它的工作很不错。并且具有较少的碰撞。该指数范围从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解析长字（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; 
} 

Answer 12

这里的a link解释了许多不同的散列函数，现在我希望为自己的特定问题的ELF散列函数。它需要输入任意长度的字符串。

Answer 13

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

给予下列文字输入：阿迪克斯有一天对杰姆说：“我宁愿你在后院打锡罐，但我知道你会在鸽子后去 。拍摄所有你想要的蓝色鸟，如果你可以击中它们，但是 记得杀死一只嘲鸟是一种罪过。“那是我唯一一次听到阿迪克斯说过做某件事是一种罪过，我问小姐 Maudie关于它。 “你父亲是对的，”她说。 “模仿鸟不要 做一件事，除了让我们享受音乐。他们不吃东西吃人家的花园，不要窝在玉米床上，他们不会做一件事 但为我们唱出心声。这就是为什么杀死一只 模仿鸟是一种罪过。

这将是输出：

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