可接受的類型在HashTable中作爲鍵使用

Question

我必須承認對HashTables的工作原理只有基本的瞭解，儘管從我所知道的事情來看似乎相當簡單。我的問題是這樣的：傳統的看法似乎是使用簡單的基本值類型，例如HashTable中的鍵的整數。然而，字符串也經常被使用，儘管在很多語言中它們被實現爲引用類型。我覺得一般不是鼓勵使用複雜的參考類型;我猜這是因爲這樣做需要更慢的哈希函數？但那爲什麼如此常用字符串？畢竟，在內部不是一個字符串[]數組（再次，在大多數語言中）？最後，哪些值類型通常被認爲是在HashTable中用作鍵的「最好」（或甚至是「可接受的」）選擇？是否有任何常用的選項被認爲是「不好的」（可能是字符串）？

Answer 1

最好hash keys是那些

1. 具有良好的（如在低collisions）哈希值（見Object.GetHashCode爲.NET，Object.hashcode對Java）
2. 有快速比較（當有哈希衝突的） 。

所有這一切，我認爲在大多數情況下字符串是很好的散列鍵，因爲有很多優秀的字符串散列實現。

Answer 2

只要提供了合適的散列函數，所有類型都將作爲關鍵字。畢竟，哈希表只是一個線性數組。哈希函數採用某種類型的鍵並計算哈希表數組（稱爲存儲區）中存儲值的索引（儘管存在一些碰撞問題）。

所以真正棘手的部分是找到一個散列函數。當然，它應該具有某些屬性，如計算簡單，混亂（幾乎相同的鍵應映射到完全不同的哈希表桶），確定性（相同的鍵意味着相同的哈希表桶），一致性（所有可能的鍵均勻映射到桶）或者外觀性（應該使用散列表的所有桶）。

看起來像整數這樣的簡單類型定義這樣一個函數更容易。

Answer 3

大多數字符串實現，雖然它們可能在託管環境中顯示爲引用類型，但它們的實現通常是不可變類型。

散列函數的作用是將大量的狀態映射到較少數量的狀態。

這就是爲什麼字符串散列對測試字符串相等性有好處的原因。您可以將該值映射到數組的索引，並快速查找有關該值的一些信息。您不需要將每個字符與其他每個字符串中的其他字符進行比較。你可以說任何事情都是一樣的。這是關於減少或以某種有用的方式指紋任意數量的字節。

這是關於您在哈希表中使用的密鑰類型的討論變得無效的原因，因爲它是將該值映射到較小的狀態空間以及如何在內部使用它以使其有用。一個整數通常是硬件友好的，但32位並不是一個真正的大空間，並且可能在該空間內發生衝突以進行任意輸入。最後，當你確實使用散列表時，計算散列值的代價與將每個值與其他每個可能位置中的每個值進行比較所用的時間無關（假設你的散列值表包含數百個項目）。

Answer 4

如果你使用一個複雜類型作爲鍵，然後：

• 這將是很難的哈希表實施，商品組合成桶進行快速檢索;它將如何決定如何將一系列哈希分組到一個桶中？
• 哈希表可能需要知道該類型以便選擇一個存儲桶。
• 存在對象屬性更改的風險，導致項目以錯誤桶爲結尾。哈希必須是不可變的。

通常使用整數，因爲它們很容易分割成對應於存儲區的範圍，它們是值類型，因此是不可變的，而且它們相當容易生成。

Answer 5

這不是串與整數或值對比基準的問題，但可變鍵與鍵不變。只要鍵是不可變的（因此它們的散列值永遠不會改變），它們就可以索引一個散列表。例如，Java中的字符串是不可變的，因此非常適合作爲散列表鍵。順便說一句，如果一個數據類型足夠簡單，以便總是按值傳遞（比如標量），那麼它當然是OK的。

但現在想象一下，你使用了一個可變類型;如果你給我一個這些對象的引用作爲關鍵字，我將計算它的散列值，然後把它放在我的一個散列表桶中。但是，當您稍後修改對象時，我將無法通知;並且該對象現在可能駐留在錯誤的存儲桶中（如果其散列值不同）。

希望這會有所幫助。