字典(Dictionary) 抽象資料結構

在字典裡，有個物品，每一樣東西都會跟隨著一個(假設物品和物品之間，不會有相同的)，我們可以透過去找出我們想要的物品，而在字典這個資料結構，支援了以下三種操作

• Insert : 把一個物品插入到
• Delete : 把一個物品從中移除
• Search : 輸入一個，如果有對應到的物品，回傳該物品，如果找不到對應的物品，則回傳NULL。

在字典中，如果我們使用Search搜尋不到對應到的物品，我們是沒有辦法像是二元搜尋樹一樣，找到前一個物品或是下一個物品的。

我們要解決上面這個字典的問題，我們可以使用AVL tree，他可以使Insert, Delete, Search這三個操作的時間複雜度均為，但我們希望在Search這個操作，我們希望能夠達到的時間。

在python中，就存在dictionary這種資料結構，而他的底層細節即是使用雜湊表(hash table)的方式實現的

名詞解釋:

• satellite data(衛星數據)與key(鍵值): 以C語言作為舉例，假設我們定義學生為一個結構(struct)如下:

sturct student{
    int age;
    char* name;
    int ID;
};

如果我們想要對學生以年紀(age)進行排序，那麼對於排序來說，age就是排序的關鍵字，或是鍵值(key)，而name和ID就稱為satellite data(衛星數據)。可以想像成排序時，name和ID等satellite data是跟隨age這個key進行排序。

Direct-address tables(直接尋址表)

運用直接尋址表，可以讓我們在時間內完成Search的操作。

我們可以想像，我們開出了一個很大的陣列，而這個陣列中存放許多元素，每一個元素對應到的index當作是元素對應到的key，如圖所示。

假設有一個集合存在有個元素，，每一個元素皆為keys(對應到陣列的index)，且這些keys彼此之間相互獨立。

令為一直接循址表(以陣列的形式存在)，記為，其中中每一個位置(槽, slot)，對應到集合中的key，也就是集合中的元素。

會指向集合中key值為的元素，如果不存在，則NULL

表示所有關鍵字(key)的集合，表示該關鍵字有對應到的元素的關鍵字(key)集合，為直接循址表，透過去查詢到欲尋找的元素，和集合就是集合的index。

假設我們有一條紀錄，他的key為15，那我們就去查詢(呼叫Search)是否存在某一條紀錄的key為15，如果存在，則存在，並回傳，否則為NULL。
而以下為SEARCH, INSERT, DELETE的虛擬碼

DIRECT-ADDRESS-SEARCH(T, k)
return T[k]

DIRECT-ADDRESS-INSERT(T, x)
T[x.key]=x

DIRECT-ADDRESS-DELETE(T,x)
T[x.key] = NULL

而上面這些操作，都只需要的時間

但是在實務上，會遇到兩個問題

1. 如果是一個很大的數值，那我們就必須要開一個超大的陣列。
2. 誠如上面的學生排序問題，如果我們將學生姓名作為key，那會變得非常麻煩。(可以將字串轉成ASCII儲存，或是使用類似prehash的技術)

因為上面我的使用陣列的index作為元素關聯的key。我們希望我們能夠保存數據的同時，讓表的規模越小越好。

在陣列中，每一個空格我們可以把它稱為的一個槽(slot)。

雜湊表(Hash table)與雜湊函數(Hash function)

為了避免掉直接循址表需要開出超級大的陣列這個問題，我們可以使用雜湊函數(Hash function)這項技術進行處理，使用雜湊函數去運算出key。也就是我們希望把一堆構成的集合，變成一個比較小的集合

在使用直接循址的方式時，具有關鍵字的元素會被存放在中，也就是的槽。而使用雜湊的方式，元素是存放在雜湊函數運算出的結果。由關鍵字透過雜湊函數計算出槽所在的位置，也就是，這裡雜湊函數會將元素為關鍵字的集合映射(Mapping)到雜湊表上，而的值會比直接循址中集合的大小來的小的許多。

而此時我們可以說運算出的值是關鍵字的雜湊值(Hashing)。

概念上就是有用到的有個，而整個Table的大小為，我們希望

上面的操作我們會發現一件事情，如果關鍵字經過雜湊函數後得到的雜湊值和其他關鍵字得到的雜湊值相同時，他們會存取到相同的數值，發生這樣的情況，我們稱為衝突(collision)。例如一個Table中，有兩筆資料存到同一個slot中。

會發生衝突的原因，在於我們給的關鍵字可以任意數值($U$集合中)，但是我們產生出的雜湊值需要在一定的範圍內，也就是在的index內，因此會發生衝突。舉例如下:

假設我們定義hash function為，假設，則如果我們要放入57和65這兩個item，則經過hash function,,，這兩個數值會存入到hash table中相同的slot，而這就是衝突。

衝突定義:

鏈接法(chaining)

鏈接法，概念為如果有超過一個以上的元素經過hash function後，儲存到同樣的slot，則在該slot使用linked list(鏈結串列)將資料全部儲存在槽(slot)中，如下圖所示

在使用這樣的方法後，雜湊表$T$上的字典操作大概如下

CHAINED-HASH-INSERT(T, x)
insert x at the head of list T[h(x.key)]

CHAINED-HASH-SEARCH(T, k)
search for an element with key k in list T[h(k)]

CHAINED-HASH-DELETE
delete x from the list T[h(x.key)]

插入和刪除的操作皆為(假設為雙向鏈結串列)，在最壞的情況下，就是所有資料都在同一個槽裡面，而這時候Search的操作就會是，那雜湊表的效率就跟鏈結串列的效率差不多了，但是在實務上，最壞情況幾乎不會發生，他的平均情況是非常好的。

鏈接法效率分析

上面提到，Search的最差情況就是所有元素都在同一個槽(slot)中，而Search的時間會取決於鏈結串列的長度。我們假設有一個具有個槽位的雜湊表，總共有個元素，有個元素要放入個槽位。

接著再做出一個假設，所有的再經過雜湊函數運算後，他們被映射到雜湊表中每一個槽的機率皆是相等的，機率皆為，且每一次均為獨立事件，我們可以估計在使用鏈接法的情況下，中每一個槽的鏈結串列平均長度為(每一個元素映射到槽的機率為，總共個元素)，而我們會稱他為雜湊表的裝載因子(load factor)，會簡稱為。可以大於，等於，或是小於1，如果，則，也就是當，成立。

我們發現到使用雜湊表，它的效率取決於雜湊函數將分布在中個槽位的均勻程度，我們在上面假設了每一個元素出現在個槽位的機率皆是相等的，且為獨立事件，我們稱這個假設為簡單均勻雜湊(simple uniform hashing)

雜湊表每一個槽的平均長度，可以使用期望值以下面形式表示

對於, 的鏈結串列長度以表示，則，並且的期望值為。

而當我們使用Search尋找為的元素，會有兩種情況，第一種為在中沒有找到一個元素的key為，第二種為成功找到key為的元素。

• 在第一次尋找不成功的情況下，我們要遍歷鏈結串列的平均長度為，而假設計算雜湊函數需要的時間，則Search平均所需要的時間。
• 在第一次就成功尋找到，我們需要考慮到每一個槽中的鏈結串列被尋找到的機率並不是均等的，所含元素越多的鏈結串列，被尋找到的機率越大。但是，Search的期望值仍然為。

證明 : 假設欲尋找的元素是n個元素中任意一個，且每一個元素被尋找到的機率皆均等。在一次就成功尋找到元素的情況下，我們需要遍歷的元素數量為前面的元素數量加1，因為之前的元素都是在之後插入在鏈接串列中，為了確保之前的元素都有被遍歷到，對所在的鏈結串列，對以前插入到鏈結串列元素數量的期望值加1，在對所有個元素取平均，得到平均情況的機率。

令為插入到鏈結串列中第個元素，並設。對於和，定義指示器隨機變數，表示經過雜湊函數，出現在雜湊表中同一個slot的情況，如果為真則，反之為0。在前面的簡單均勻雜湊的假設之下，，發生兩個經過雜湊函數映射到雜湊表中同一個slot機率的期望值，因此，在一次成功就尋找到元素，期望遍歷過的元素總數的期望值可以用以下式子進行表示:

n個元素選一個，遍歷整個Hash table()，每個Hash table需要檢查的元素數量()

因此，一次成功尋找到元素所需要的全部時間就是遍歷元素個數的期望值加上計算雜湊函數的時間。

因此，成功一次就尋找到元素和第一次沒有成功尋找到，他們的平均情況皆為

經過上面的證明，得到當每一個slot中皆為雙向鏈結串列時，Insert, Delete, Search的操作皆為的時間可以完成。當然，上面這些證明是基於這是一個簡單均勻雜湊的條件下。

不是hash table都會是，實際上是取決於裝載因子(如果有很多元素，但Hash table很小，那他必定不會是常數時間，如果能夠保證Hash table隨著元素的數量增長，才能夠說他是常數時間)。Hash table之所以好用，就是因為我們可以在常數時間內完成動態集合的字典操作。

參考資料:Introduction to algorithms 3rd