動態(dynamic)和靜態雜湊(static hashing)的區別

在資料結構中，雜湊是一種使用稱為雜湊函式的特殊函式將大量資料項對映到較小表的技術，以實現更快的訪問。有時資料結構非常龐大，幾乎不可能透過所有級別搜尋所有索引值來訪問最終的資料塊。這就是雜湊的用武之地。它所做的是直接計算資料記錄在磁碟上的位置，而不使用索引結構。每個記錄的地址是使用雜湊演算法確定的，該演算法將主鍵值轉換為記錄地址。因此，有兩類可用的索引使用雜湊函式-動態雜湊和靜態雜湊。...

什麼是靜態雜湊(static hashing)？

靜態雜湊是一種雜湊方法，其中為檔案分配固定數量的bucket來儲存記錄。儲存桶的數量是預先分配的，因此當提供搜尋鍵值時，雜湊函式總是計算相同的地址。一個檔案的頁面可以被看作是一個bucket集合，包含一個主頁面和額外的溢位頁面。對於靜態雜湊，定位機制是雜湊函式，不涉及資料結構。在這裡，索引項是隨機的，每個bucket中的索引項的數量大致相同。然而，這項計劃也有某些缺點。如果bucket的初始數目太小，檔案會增長，那麼效能會因為bucket溢位而下降。另一方面，如果規模過大，則會為預期增長分配大量空間，並浪費大量空間。

什麼是動態雜湊(dynamic hashing)？

另一方面，動態雜湊是一種用於剋服靜態雜湊（如桶溢位）限制的技術。與靜態雜湊不同，它允許桶的數量動態變化，以適應資料庫檔案的增長或收縮。它允許根據需要修改hash函式，這對於大小不斷增長和縮小的資料庫是很好的。在新增和刪除行時，它會相應地更改bucket的數量，以最小化bucket的溢位。它將溢位記錄的處理動態地嵌入到主地址空間中，以避免溢位儲存桶的控制代碼管理。動態雜湊的兩種常用形式是線性雜湊和可擴充套件雜湊。可擴充套件雜湊是一種流行的技術，它透過將一個bucket一分為二來處理bucket溢位，在新舊bucket之間分發記錄。線性雜湊是另一種流行的動態雜湊形式，它允許雜湊檔案透過分配新的儲存桶來動態地增長或收縮。

動態和靜態雜湊的區別

技術

–靜態雜湊是一種雜湊方法，其中為檔案分配固定數量的儲存桶以儲存記錄，這意味著檔案使用的雜湊函式中儲存桶地址的數量是固定的。在這裡，索引項是隨機的，每個bucket中的索引項的數量大致相同。另一方面，動態雜湊允許儲存桶的數量動態變化，以適應資料庫檔案的增長或收縮。

演出

–如果bucket的初始數目太小並且檔案增長，那麼效能會因為bucket溢位而下降。另一方面，如果規模過大，則會為預期增長分配大量空間，並浪費大量空間。另一方面，動態雜湊允許動態修改雜湊函式，這有利於資料庫大小的增長和收縮。在新增和刪除行時，它會相應地更改bucket的數量，以最小化bucket的溢位。

實施

–靜態雜湊使用固定的雜湊函式將所有可能的搜尋鍵值集劃分為子集，然後將每個子集對映到一個bucket。另一方面，動態雜湊使用對映的第二階段來確定與某個搜尋鍵值相關聯的bucket。可擴充套件雜湊和線性雜湊的對映方式非常不同。

動態與靜態雜湊：比較圖

總結

靜態雜湊中儲存桶的數量是固定的，具有不同搜尋關鍵字值的記錄指向同一個儲存桶，在這種情況下可能會發生衝突。如果需要在具有多個鍵的bucket中查詢特定記錄，則必須按順序搜尋整個bucket。有時候，一個bucket包含的記錄比它能包含的要多。因此，在這種情況下，必須呼叫一些溢位處理技術。在這種情況下，將使用動態雜湊，它使用一個動態更改的函式，該函式允許分配的bucket數隨著行的新增和刪除而在大小上增長和收縮。它透過將溢位記錄動態嵌入主地址來顯式處理bucket的溢位。