散列函數和餘數運算符

Question

我有一個簡單的問題困在我的腦海裏，一直困擾着我。我的教授簡單地說散列函數是關鍵％arraysize。這對每個哈希表都必須這樣嗎？還是我們決定的東西？我們是否真的爲我們創建的每個哈希表編寫哈希函數？例如，它可以是不同的，簡單地說，散列函數=密鑰。

Answer 1

通常，散列函數的域比其範圍大得多。例如，散列可能接受「所有unicode字符串長度小於2^64個字符」並輸出「16位數字」。

是的，對於少數應用程序，使用標識函數作爲散列函數是有意義的，儘管散列表開始看起來非常像普通數組。

對於散列表，一般來說，模（%）是一個不錯的選擇：它在計算上很容易，並且在通常情況下可以很好地展開。然而，它不是密碼強大的，許多應用程序都需要這樣做。

Answer 2

你有一個數組來存儲索引所引用的固定大小的結果（在問題的情況下，index = key％array_size，保證產生一個介於0和array_size-1之間的數字）。如果索引大於數組大小，則會出現問題。如果它總是少於那麼你就浪費了空間，所以散列的最後階段往往是它必須適合的數組大小的模。

當然，這並不總是導致均勻傳播因此您可以在之前修改的密鑰作爲索引。