哈希表混亂 - 哈希表需要多少空間才能獲得良好（例如加密）哈希函數？

Question

我正在學習哈希表，哈希映射等。我剛剛在C中實現了一個哈希表，操作如下：操作：insert(HTable, key),delete(HTable, key),initialize(HTable)和search(HTable, key)。

我想問一下。由於在一個（適當的）哈希表中，計算出的散列索引可能非常大，這是不是意味着消耗的空間會像INT_MAX（當然仍然是O（n））或更多？我的意思是給定我們想要存儲在散列表中的輸入元素（即將其插入），insert（）函數將調用散列函數，然後計算散列索引以便元素進入。因此，它將使用散列函數來找到這個索引。

當我們使用散列函數對元素進行操作時，散列索引可能變得非常大。有了合適的密碼散列函數，這個指數可能會變得很大（他們使用300位數的素數--Diffie Hellman公鑰密碼系統等），對嗎？我知道在正常的散列函數（比如初學者用來學習的平凡的函數）中，我們應用mod操作以便元素適合散列表的邊界，但是這樣做可能會限制散列函數的潛力？

因此，爲了將元素唯一映射到哈希表，我們必須使用一個巨大的哈希表。這些密碼散列表如何實現？他們必須是完全安全的，對吧？即使是「cryptographichashfunction」上的Stack Overflow標籤，也很難找到兩個映射到相同元素的輸入（因此碰撞的可能性很小）。這不需要通過一個巨大的數組來存儲在內存中（或磁盤）？因此，內存消耗會很大。

當然，時間複雜性不是問題。我們只是看到散列表/數組的起始地址添加索引，只是去內存中獲取值（O（1） - 哈希表的搜索原理）。

我在哪裏錯了嗎？有什麼我失蹤？我希望我明確自己。所以最後，我想就此確認。一個好的散列函數是否需要一個巨大的數組（哈希表），以及如此大量的內存才能正確實現？有太多的空間是正確的，還是有我不完全得到的東西？謝謝。

Answer 1

一般來說，用於散列表的密碼散列值是而不是。而是使用快速散列。在該散列值中，只有很多位可以用​​來調整表的大小。如果多個鍵值映射到相同的索引，則這些值與附加信息一起存儲以在兩者之間進行選擇。

不要求散列輸出是唯一的;散列函數輸出將會過大，並且所需的表格肯定不適合內存。除此之外，密碼哈希通常很慢。

加密哈希函數通常是從也用於對稱分組密碼的操作構建而成的。這意味着在大量循環中使用混合和按位運算符。模塊化算術，如用於例如RSA是而不是使用。

你似乎沒有得到的主要原因是生成的索引不需要是唯一的。有其他方法可以區分關鍵值。