Java的hashCode可以爲不同的字符串生成相同的值嗎？

46

Java哈希碼是32位。它散列的可能字符串的數量是無限的。

所以是的，會有碰撞。百分比沒有意義 - 有無限數量的項目（字符串）和有限數量的可能哈希值。

來源

2012-04-11 08:26:13 Mat

+1

因此，我可以說它可以產生2^32不同的哈希值，之後它將重複哈希碼？ – Xara 2012-04-11 08:31:15

+0

如果您設法識別所有具有不同哈希碼的2^32字符串，那麼是的，不在該列表中的任何其他字符串將具有與該列表中的哈希碼相同的哈希碼。 – Mat 2012-04-11 08:32:13

+8

另一方面，這被稱爲鴿子主義原則http://en.wikipedia.org/wiki/Pigeonhole_principle – 2012-04-11 22:07:18

5

這不會直接回答你的問題，但我希望它有幫助。

以下是源代碼java.lang.String。

/** 
* Returns a hash code for this string. The hash code for a 
* <code>String</code> object is computed as 
* <blockquote><pre> 
* s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] 
* </pre></blockquote> 
* using <code>int</code> arithmetic, where <code>s[i]</code> is the 
* <i>i</i>th character of the string, <code>n</code> is the length of 
* the string, and <code>^</code> indicates exponentiation. 
* (The hash value of the empty string is zero.) 
* 
* @return a hash code value for this object. 
*/ 
public int hashCode() { 
    int h = hash; 
    int len = count; 
    if (h == 0 && len > 0) { 
    int off = offset; 
    char val[] = value; 

     for (int i = 0; i < len; i++) { 
      h = 31*h + val[off++]; 
     } 
     hash = h; 
    } 
    return h; 
}

來源

2012-04-11 08:25:31 adarshr

4

是，通過鴿子洞概念的定義，兩個不同的字符串可以產生相同的散列碼和代碼應該總是被寫入以滿足這樣的條件下（典型地，由不斷裂。）

來源

2012-04-11 08:25:40

16

YES 。很多。

請看下面的一對

「FB」和「EA」

可以返回相同的散列碼，即使在它的字符不相同。

基本上它是字符串中的字符總和乘以整數。

來源

2012-04-11 08:26:09 titogeo

+3

這是不正確的。每個字符乘以不同的數字，所以字符不一定會返回相同的值。 – assylias 2012-04-11 08:27:16

+0

對不起我的壞！用一個常見的例子糾正。 – titogeo 2012-04-11 08:33:33

+0

爲什麼他們有相同的哈希碼？他們是兩個不同的字符串...：S – Xara 2012-04-11 09:26:54

5

是的，兩個字符串可能具有相同的哈希碼 - 如果查看Wikipedia article，您會看到"FB"和"Ea"具有相同的哈希碼。方法合同中沒有任何內容說明應該使用hashCode()來進行比較，您希望使用equals()。

自從Java 1.2以來，String通過using a product sum algorithm over the entire text of the string實現了hashCode()。

來源

2012-04-11 08:30:21 Marcelo

7

如果有可能那麼它的可能性是多少％？

這不是一個特別有意義的問題。然而，除非在函數中存在一些系統偏差，否則任何兩個不同（不相等）的字符串具有相同的哈希碼的概率將是1^2^32。

這假定字符串是從所有可能的字符串值集合中隨機選取的。如果您以各種方式限制集合，則概率將與上述數量不同。（例如，「FB」 /「EA」衝突的存在，意味着在集合中的所有2個字母串的碰撞的概率高於常規。）

另一個要注意的是隨機選擇2^32個不同字符串（來自大得多的無偏集字符串集合）的機會是沒有散列衝突的很小的。要理解爲什麼，請閱讀Birthday Paradox上的Wikipedia頁面。實際上，只有在選擇或生成字符串時，才能在一組2^32個不同的字符串中獲得散列衝突。（甚至通過選擇隨機生成的字符串來形成該組將是計算上昂貴的。）

來源

2012-04-11 08:41:03

+0

所以，我可以說，對於2^32個不同的字符串，哈希碼功能將始終產生不同的哈希碼？ – Xara 2012-04-11 09:18:17

+0

@Zara - 不，你不能。 2^32中的1是概率的度量。想想看。假設你使用所有具有相同哈希碼的字符串填充2^32字符串的集合... – 2012-04-11 10:46:35

+1

@Zara其實它甚至說得相反！有2^32個不同的字符串，你很可能會碰撞（甚至幾個..）。 – jorey 2012-04-12 01:20:28

2

隨機碰撞的百分比應該是最小的。但是，如果您從外部源散列字符串，攻擊者可以輕鬆創建具有相同散列碼的數十萬個字符串。在一個Java HashMap中，這些都將映射到同一個存儲桶並有效地將地圖轉換爲鏈接列表。地圖的訪問時間將與地圖大小成比例，而不是常數，從而導致拒絕服務攻擊。

請參閱此頁上的Effective DoS attacks against Web Application Plattforms瞭解更多信息鏈接到演示文稿。

來源

2012-04-11 11:28:20

7

是的，這是完全可能的。具有與集合中某個其他字符串相同的哈希碼的字符串（或其他一些對象類型 - 只是假設您將在此示例中使用字符串）的概率取決於該集合的大小（假設所有字符串都在該集合是獨一無二的）。概率分佈如下：

隨着一組大小約9,000，你就會有兩個字符串的1％的機率在集合
隨着一組大小約30,000用哈希碰撞，兩個字符串與集合中的哈希碰撞的機率爲10％
對於一組大小爲〜77,000的集合，您將有50％的機會與集合中的哈希碰撞兩個字符串

作出的假設是：

的哈希碼功能沒有偏見
在上述一系列每個字符串是唯一

本網站解釋清楚：http://eclipsesource.com/blogs/2012/09/04/the-3-things-you-should-know-about-hashcode/ （請看「第二件事你應該知道」）

來源

2014-06-19 11:47:30 user3514416

+0

他們在那裏測試過的字符串的字符集是什麼？ – 2015-09-09 12:32:27

Java的hashCode可以爲不同的字符串生成相同的值嗎？

回答

相關問題