理解散列碼

散列函數在實現散列表中很重要。我知道在java 對象有它的哈希碼，它可能是從弱哈希函數生成的。理解散列碼

下面是一個片段，是「補充哈希函數」

static int hash(Object x) { 
    int h = x.hashCode(); 

    h += ~(h << 9); 
    h ^= (h >>> 14); 
    h += (h << 4); 
    h ^= (h >>> 10); 
    return h; 
}

任何人可以幫助解釋什麼是哈希算法的基本理念？生成非重複的整數？如果是這樣，這些按位運算如何執行？

來源

2010-06-25 SecureFish

你通常試圖用散列算法做什麼是將一個大的搜索關鍵字轉換成一個小的非負數，這樣你就可以在某個表的某個地方查找關聯的記錄，並且比M log2 N（其中M是「比較」的成本，N是「表」中項目的數量））是典型的二進制搜索（或樹搜索）。

如果你足夠幸運有一個完美的散列，你知道你的（已知！）按鍵的任何元素將被散列到一個獨特的，不同的值。對於需要查找語言關鍵字的編譯器而言，完美的哈希值得關注。

在現實世界中，你有不完美的散列，其中幾個鍵都散列到相同的值。沒關係：你現在只需要將密鑰與一小組候選匹配（散列到那個值的那個）比較，而不是一個大集合（全表）。傳統上稱爲「桶」。您使用散列算法選擇一個存儲桶，然後爲存儲桶本身使用其他一些可搜索的數據結構。（如果桶中元素的數目已知，或者安全地預期爲非常小，則線性搜索不是不合理的。二元搜索樹也是合理的。）

您示例中的按位操作看起來很像簽名分析移位寄存器，它試圖將長的唯一位模式壓縮成短而唯一的模式。

來源

2010-06-25 21:33:49

散列函數是任何明確定義的過程或數學函數，它將大量可能可變大小的數據量轉換爲小數據，通常是一個可用作數組索引的整數。由散列函數返回的值稱爲散列值，散列碼，散列總和，校驗和或簡單散列。（wikipedia）

使用更多「人類」語言對象散列是基於對象屬性的簡短緊湊值。這就是說，如果你有兩個對象以某種方式變化 - 你可以期望他們的散列值是不同的。好的散列算法爲不同的對象產生不同的值。

來源

2010-06-25 21:36:17

一個好的散列函數也應該爲類似的值創建_very_不同的散列值。即使元素A和元素B在一個位上不同，他們的哈希應該是非常不同的。 – Piotr 2010-06-25 21:56:10

我一直很喜歡這個寫法：http：//www.eternallyconfuzzled。COM/TUTS /算法/ jsw_tut_hashing.aspx – Joe 2010-06-25 22:51:30

該代碼試圖通過混合位來提高散列值的質量。

總體效果是，對於給定的x.hashCode（），希望可以在整個整數範圍內更好地分配散列值。如果您開始使用糟糕的哈希碼實現，但是通過這種方式改善哈希碼，某些算法的性能會提高。

例如，Java中一個不起眼的Integer的hashCode（）只返回整數值。雖然這對許多目的都很好，但在某些情況下，您需要更好的哈希代碼，因此通過這種函數添加哈希代碼將顯着改善它。

來源

2010-06-25 23:19:00 mikera

基本上，你試圖用哈希函數實現的事情是給哈希代碼中的所有位大概有50％的機會被關閉或給定一個特定的項目被哈希。這樣，無論你的散列表有多少個「桶」（或換句話說，你爲了確定桶號而採取了多少底部位） - 如果每位與隨機的可能的，那麼一個物品將總是被分配給一個基本上隨機的桶。

現在，在現實生活中，很多人使用散列函數並不好。他們有一些一些隨機性，但不是全部。例如，想象一下如果你有一個散列函數，它的位6-7有偏見 - 比方說在一個對象的典型散列碼中，他們有75％的機會被設置。在這個編制的例子中，如果我們的哈希表有256個桶（即桶編號來自哈希碼的0-7位），那麼我們丟掉8-31位確實存在的隨機性，部分桶會傾向於被填滿（即那些數量爲6和7的桶）。

補充散列函數基本上試圖散佈散列代碼中的任意隨機性在大量的位上。因此，在我們的假設例子中，這個想法將會是，來自比特8-31的一些隨機性將與較低比特混合在一起，並稀釋比特6-7的偏差。它仍然不會完美，但比以前更好。

來源

2010-06-26 02:17:36

如果你正在生成一個哈希表，那麼當你編寫你的哈希函數時，你希望得到的主要事情是確保一致性，而不一定要創建完全獨特的值。

例如，如果您有一個大小爲10的散列表，則不需要反覆散列3的散列函數。否則，該特定存儲桶將強制搜索時間O（n）。你需要一個散列函數來返回它，例如：1，9，4，6，8 ......並確保你的桶不會比其他桶重得多。

對於您的項目，我建議您使用衆所周知的散列算法，如MD5或更好的SHA，並使用您需要的前k位，然後丟棄其餘部分。這些都是經過時間考驗的功能，作爲程序員，您可以很聰明地使用它們。

來源

2010-06-26 02:23:43 SHC

這可能是你想要的，只要你堅持在doc，這在我自己的話描述的general contract什麼：

如果調用100（N）次的hashCode的對象上，所有的時間必須返回相同的值，至少在程序執行過程（隨後的程序執行可以返回不同的一個）
如果o1.equals(o2)爲真，則o1.hashCode() == o2.hashCode()必須爲真也
如果o1.equals(o2)爲假，則o1.hashCode() == o2.hashCode()可以是真的，但我t幫助它不是。

就是這樣。

根據你的類的性質，hashCode（）e可能非常複雜或非常簡單。例如String類可能有數百萬個實例需要非常實用，並使用素數來降低衝突的可用性。

如果你的班級確實有一個連續的數字，那也沒關係，你沒有理由每次都把它複雜化。

來源

2010-06-26 02:39:09 OscarRyz

回答

相關問題