第 8 章　雜湊

8.1　符號表抽象資料型態

符號表上要支援的運算：(1) 判斷某一名稱是否在表中；(2) 擷取此名稱的屬性；(3) 修改此名稱的屬性；(4) 插入一個新的名稱和屬性；(5) 刪除一個名稱和屬性。

structure SymbolTable(SymTab) is
  objects: a set of name-attribute pairs, where the names are unique.
  functions:
    for all name in Name, attr in Attribute, symtab in SymbolTable,
    max_size in integer.

    SymTab    Create(max_size)          ::= create the empty symbol table
                                            whose maximum capacity is max_size.
    Boolean   IsIn(symtab, name)        ::= if (name is in symtab)
                                            return TRUE
                                            else return FALSE.
    Attribute Find(symtab, name)        ::= if (name is in symtab)
                                            return the corresponding attribute
                                            else return null attribute.
    SymTab    Insert(symtab, name, attr)::= if (name is in symtab)
                                            replace its existing attribute with attr
                                            else insert the pair (name, attr)
                                            into symtab.
    SymTab    Delete(symtab, name)      ::= if (name is not in symtab)
                                            return
                                            else delete (name, attr) from symtab.

end SymbolTable

結構 8.1：抽象資料型態 symbol table

8.2　靜態雜湊

8.2.1　雜湊表

8.2.2　雜湊函數

四種均勻雜湊函數

為什麼除法的 $M$ 要取質數 —— 課本的完整推導

8.2.3　溢位處理

「在靜態雜湊表中有兩種方法可偵測碰撞和溢位的發生；每種方法使用不同的資料結構來表示雜湊表。本節我們要討論最簡單的方法，稱為線性開放定址（linear open addressing）或線性探測（linear probing），下一節則介紹鏈結串列（chaining）。」

線性開放定址 (Linear Open Addressing)

int transform(char *key)
{
/* simple additive approach to create a natural number
that is within the integer range */
   int number = 0;
   while (*key)
      number += *key++;
   return number;
}

int hash(char *key)
{
/* transform key to a natural number, and return this
result modulus the table size */
   return(transform(key) % TABLE_SIZE);
}

程式 8.2：建立一個雜湊函數

圖 8.2：加法轉換（13 個桶，每桶一槽）—— 最後一個識別字 function 和 if 雜湊到相同的桶中。利用循環轉動，下一個可用的桶為 ht[0]，就是我們要放 function 的位置。

void linear_insert(element item, element ht[])
{
/* insert the key into the table using the linear probing
technique, exit the function if the table is full */
   int i, hash_value;
   hash_value = hash(item.key);
   i = hash_value;
   while (strlen(ht[i].key)) {
      if (!strcmp(ht[i].key, item.key)) {
         fprintf(stderr,"Duplicate entry\n");
         exit(1);
      }
      i = (i+1) % TABLE_SIZE;
      if (i == hash_value) {
         fprintf(stderr,"The table is full\n");
         exit(1);
      }
   }
   ht[i] = item;
}

程式 8.3：線性插入一個雜湊表中 —— 注意 i == hash_value 這個「繞了一圈回到原點」的滿載偵測

二次探測與重複雜湊

鏈結串列 (chaining)

#define MAX_CHAR 10          /* max number of characters */
#define TABLE_SIZE 13        /* max number of hash buckets */
#define IS_FULL(ptr) (!(ptr))
typedef struct list *list_pointer;
typedef struct list {
        char key[MAX_CHAR];
        /* other fields */
        list_pointer link;
        };
list_pointer hash_table[TABLE_SIZE];

「因為有 $M$ 個串列，$M$ 為所需要的表大小，我們在每一串列之前加上一個標頭節點。這些標頭節點僅需要一個鏈結欄位，所以比其他的節點還小。我們保持標頭節點以升冪順序 $0, \ldots, m-1$ 排列，使得我們可以隨機存取串列。」

8.2.4　溢位處理技術的理論評估

圖 8.7：擷取每一識別字的桶存取之平均次數（摘自 V. Lum, P. Yuen 和 M. Dodd, CACM, 1971, Vol. 14, No. 4）—— 各欄值為搜尋八個不同雜湊表的平均存取桶的次數，該八個雜湊表分別有 33,575、24,050、4909、3072、2241、930、762 和 500 個識別字。

R := R * 5
R := low order r+2 bits of R
S(i) := R / 4

8.3　動態雜湊

8.3.1　使用目錄的動態雜湊法

trie 與目錄的對應關係

typedef struct {
        char *key;              /* pointer to string */
        /* other fields */
        } brecord;
int global_depth;   /* trie height */
paddr directory[DIRECTORY_SIZE]; /* pointers to pages */

paddr hash(char *, short int);
paddr buddy(paddr);
short int pgsearch(char *, paddr);
int convert(paddr);
void enter(brecord, paddr);
void pgdelete(char *, paddr);
paddr find(brecord, char *);
void insert(brecord, char *);
int size(paddr);
void coalesce(paddr, paddr);
void delete(brecord, char *);

動態雜湊的宣告 —— 注意 global_depth 就是「目前需要幾個位元」，以及 buddy()：「Take an address of a page and returns the page's buddy, i.e., the leading bit is complemented」（夥伴分頁，合併時用）

8.3.2　無目錄的動態雜湊

if (hash(key,r) < q)
   page = hash(key,r+1);
else
   page = hash(key,r);
if needed, then follow overflow pointers;

程式 8.6：修改後的雜湊函數 —— q 是「已經分裂過的分頁數」的分界點

8.4　精選參考文獻

本章重點回顧