任何人都可以解釋這個散列函數背後的邏輯嗎？

任何人都可以解釋這個散列函數背後的邏輯嗎？任何人都可以解釋這個散列函數背後的邏輯嗎？

static int hash(int h) { 
    h ^= (h >>> 20)^(h >>> 12); 
    return h^(h >>> 7)^(h >>> 4); 
}

我通過key.hashCode()這個函數給我的哈希值。根據這個值和數組大小，我計算數組的索引。我只是不瞭解此方法中使用的運算符。

這個^運算符在這種情況下做什麼。它是否檢查！=
什麼是無符號右移>>>做？我們在Java中沒有Unsigned int的權利？
如何爲這個函數選擇20,12,7和4的值？是否預先定義了或用戶定義？

傳遞給該散列函數的key.hashCode()是79847235。任何人都可以解釋裏面會發生什麼，以返回最終的哈希值。

來源

2013-09-25 Shane

無符號右移（>>>），不像簽署右移（>>），將負數轉換爲正數前預先執行右移操作，確保結果返回無符號正整數。右移，例如h >>> 20，實質上是指返回地址爲h/Math.pow(2,20)的整數。
例如，對於您的輸入79847235，由於它是正數，無符號右移和有符號右移都會返回正整數。 79847235>>>20將因此預成型：
Math.floor(79847235/Math.pow(2,20))其返回76。
接下來h >>> 12爲79847235是：
Math.floor(79847235/Math.pow(2,12))返回19493
（這是更大的，因爲我們通過一個較小的數除以）。
現在我們在76和19493上執行exclusive OR。
例如1^0是1
1^1是0
如果我們想要的，其中包括，我們不得不使用一個具有包容性或者被|
因此1|1是1
1|0是0
等

1001100是76
100110000100101二進制表示的19493
二進制表示的exclusive OR操作應該是這樣的：

000000001001100（ 76二進制）
100110000100101（二進制19493）
---------------
100110001101001（我們的結果：19561）

我們幾乎對我們的第一個行來完成：
我們拿到的這款：
h ^= (h >>> 20)^(h >>> 12);
下來到：
h ^= 19561

這是一樣的：
h = h^19561

填寫我們的價值h這是79847235：
79847235^19561是79827754
h = 79827754
要記住，我們的h新值現在是79827754
這是非常重要的

下一行：
return h^(h >>> 7)^(h >>> 4);

h>>>7是Math.floor(79827754/Math.pow(2,7))返回623654
h>>>4爲Math.floor(79827754/Math.pow(2,4))返回現在4989234

的括號的方式進行，我們有：
return h^623654^4989234;
這是很重要從左到右進行預成型。
填寫h和重組：
return (79827754^623654)^4989234;

79827754^623654是：
100110000100001001100101010（二進制79827754）
000000010011000010000100110（623654二進制）
---------------------------
100110010111001011100001100（二進制80451340）

最後，我們有：
return 80451340^4989234;

80451340^4989234是：
100110010111001011100001100（二進制80451340）
000010011000010000100110010（二進制4989234）
---------------------------
100100001111011011000111110（76002878二進制）

因此，我們的最終結果是：
return 76002878;

隨時檢查我的答案，我已經仔細檢查了我的工作。
由於排他性按位或的性質，可能很難預測散列函數的結果是大於還是小於我們的參數。例如：
11^2是9
17^2是19（比我們的參數11小）（大於我們的參數17）

來源

2013-09-26 00:49:39 Ultimater

已存在一個同樣的問題和答案，我掛：HTTP：//計算器。 com/questions/9335169/understanding-strange-java-hash-function。由於這也是一個重複我想知道你爲什麼回答.... –

Ultimater，謝謝你的答案。我真的很想知道，爲什麼它特別是20,12,7和4.他們如何衡量隨機性。這裏的大多數答案都會介紹隨機性等等。它是如何創造這種隨機性的？爲什麼右邊的位置必須是20，爲什麼不能是21或19？你能解釋一下嗎？對不起，如果我錯過了一些基本的東西。 –

你也可以使用其他數字。如果您通過函數運行每個數字0到100 quadrillion，您會發現無論在函數中使用什麼數字，輸出中都不會有重複。這是因爲異或的性質。 2^5 = 7。 7^5 = 2。 2^7 = 5。如果你在循環中運行'i^2'（var i = 0; i <100; i ++）'並將結果存儲在一個數組中。你會看到該數組將包含每個數字0到99而不重複。 http://jsfiddle.net/e9v2D/。因此，無論使用什麼數字，它都不會包含由於異或的觸發器行爲而導致的重複，如2,5和7所示。 – Ultimater

看一看下面：

Bitwise and Bit Shift Operators 

~  Unary bitwise complement 
<<  Signed left shift 
>>  Signed right shift 
>>>  Unsigned right shift 
&  Bitwise AND 
^  Bitwise exclusive OR 
|  Bitwise inclusive OR

相關的unsigned right shift見：unsigned right Shift '>>>' Operator in Java

此外，對於>>>我認爲：

的>>>運算符將表達式1的位正好等於表達式2中指定的位數。零點從左側填充。被丟棄的位數被丟棄。所以這種轉變並不尊重標誌。

那麼，這功能做...

（H >>> 20）除以2小時至20。電源（它變爲20倍向右）。而且，這意味着如果你的電話號碼是負號，它不會繼續如此。
（h >>> 12）將h除以2的12次冪（它向右移動12次）...再次與負數相同。
然後將兩個結果進行XOR，然後再與原始H進行異或運算。
以下更多XORing繼續計算最終的散列值。

編輯：注意到了這一點已接受的答案了廣泛的分析來：Understanding strange Java hash function

來源

2013-09-25 23:38:28

任何人都可以解釋這個散列函數背後的邏輯嗎？

回答

相關問題