什麼是設計優勢散列式節省vs增量式

Question

類似jsfiddle和tinyurl的網站不以增量順序保存。這有什麼好處嗎？

如果它是一個隨機字符串或哈希會不會很慢，因爲首先你必須檢查這樣的條目是否已經存在，如果是這樣，然後創建一個新的並重復。

增量如此高效和直觀嗎？

Answer 1

以增量順序保存肯定會更快。但是如果你的數組目前有10億個元素，你已經增加了10億個條目，並且刪除了9.5億個條目，你可能想要重用空間而不是再次增加數組的大小。無論你有多少記憶，你總有一天會用完。使用良好的散列表，您可以輕鬆地保存相同數量的數據，使用1億個元素數組，您無需調整大小。

哈希表確實需要一個很好的算法來開發哈希代碼。如果它們的大小發生巨大變化，它們可能浪費空間或導致大型數組的重複分配（這可能會嚴重干擾垃圾收集器）。但它們速度很快，並且檢查重複項是簡單的索引操作。可以在小型鏈接列表中處理少量重複項，這些列表非常快。如果你可以猜測散列表的初始大小，它會有幫助。

我一直傾向於基於二叉樹的「地圖」或「字典」。它們更慢，但更靈活，不使用巨大的數組;內存分配和釋放在一點點，可管理的位。他們可以處理大小/使用量的大幅波動。您不需要可靠的哈希碼生成器。但是如果你知道你的數據，散列表通常會更好。

Answer 2

如果底層結構是一個哈希表，檢查一個條目是否存在可以在恆定時間內完成，所以根本不會很慢。

Answer 3

外部人並不總是能夠從連續鍵區分散列。應用程序完全有可能在內部使用某種形式的順序ID，但在將其暴露給外部世界之前對其進行加密。通常不應該依靠這種方法來爲可能試圖「猜測」ID碼的攻擊者提供很大的安全性（它們基本上代表「通過隱晦的安全性」），但至少它們可以阻止人們基於事實網站似乎以某種特定的方式分配了ID。例如，一個站點可能從一臺使用順序ID的服務器開始，但可能會切換到有兩臺服務器，其中一臺順序分配奇數，另一臺順序分配偶數（兩臺服務器都從最高數量開始，被單個服務器分配）。如果連續的ID已經暴露給外部世界，那麼某個站點可能已經編碼了一個假設，即ID編號將代表時間順序。即使是一些簡單的事情，比如將一個ID乘以某個大常數（忽略溢出），以某種值異或乘以某個其他常數，就會產生ID，這可以很容易地被知道該方法的人轉換回序列號，但是會阻止任何關於訂購的假設。