良好的字符串散列函數

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