---
tags: 資料結構, 第八章, HASHING
---
# 資料結構 第八章 雜湊

## 一、符號抽象資料型態
### (一)操作
#### 一般我們使用表格會操作的符號
1、確定表中是否有特定名稱
2、檢查該名稱的屬性
3、修改該名稱的屬性
4、插入新名稱及屬性
5、刪除名稱及其屬性
### (二)抽象資料型態
【變數設定】
for all name belong to Name, attr belong to Attribute, symtab belong to SymbolTable, max_size belong to integer.
1、SymTab Create(max_size):創建一個空的表格大小為max_size
2、Boolean IsIn(symtab, name) 前提假設name存在此表格中則回傳True，前提假設不成立則回傳False。
3、Attribute Find(symtab, name):前提假設name存在此表格中則回傳對應的屬性，前提假設不成立則回傳 屬性空 (null attribute)。
4、SymTab Insert(symtab, name, attr):前提假設name存在此表格中則利用attr替代現有的屬性，前提假設不成立則插入(neme,attr)(名稱及屬性)於表格
5、SymTab Delete(symtab, name):前提假設name不存在此表格中則return(沒有任何操作)，前提假設不成立則從表格中刪除(neme,attr)(名稱及屬性)。
## 二、靜態雜湊
### (一)雜湊表
#### 1、定義:
(1)雜湊方法:
是使用一個雜湊方程式(hashing function)作為值與位址的對應。輸入透於方程式計算後找到所對應位址在做存取。
(2)基本名詞介紹
a、桶子(buckets):將雜湊表中分成多個桶子(索引)可儲存資料。
b、槽(slots):為一個桶子內可以儲存的空間。
(3)負載因子or負載密度
負載因子= n / (sb)。
n:資料數量 s:槽 b:桶子
(4)雜湊表:由s個槽組成桶子，再由b個桶子所組成則為雜湊表(每個槽可存一筆資料)
### 2、圖示:
則搜尋、輸入、刪除皆為O(1)
### (二)雜湊函式
#### 1、Mid-square(平方取中法)
將輸入的值平方後再取中間的部分。
#### 2、Division(除法取餘數)
一般會除以桶子的數量再取餘數，如此一來皆可以對應到唯一的桶子。
#### 3、Folding(摺疊法)
Ex:12320324111220
分成: X1:123 X2:203 X3:241 X4:112 X5:20
##### (1)Shift folding(移動折疊)
123+203+241+112+20 = 699
##### (2)Boundary at the folding(邊界折疊)
先將偶數反向再相加 (X2=302 X4=211)
123+302+241+211+20=897
#### 4、Digit Analysis(位數值分析)
因資料都是事先已知，則可以選定特定基底，然後分析每個資料之同一位數值
找出所對應的位址較分散的方式。

>參考範例:國立聯合大學 資訊管理學系 演算法課程 (陳士杰)
### (三)溢位處理
#### 1、Linear Open Addressing(線性探勘or線性開放尋址)
##### (1)步驟
將元素插入雜湊表，如果雜湊地址處的槽為空，則將新元素插入該槽。
但是，如果將新元素雜湊到一個滿的桶中，則必須找到另一個桶儲存。
解決方案則是將新元素放入最接近的未滿的桶中。
我們將這種解決溢出的方法稱為線性探測或線性開放尋址。
##### (2)圖示:
#### 2、Chaining
##### (1)步驟:
具有相同雜湊位址的資料存放在同一個桶子中，使用link list 方式串聯，屬於close addressing mode
##### (2)圖示:

##### (3)

#### 3、比較

| 分離鏈接(Separate Chaining) | 開放定址(Open Addressing) |
| -------- | -------- |
| 實作簡單 |碰撞需要額外計算 |
| 空間不受限制 |空間會滿 |
| 適合不知道資料插入刪除有多少時 | 適合知道資料出現頻率時 |
| 使用鏈結使用額外空間 |無鏈結無使用額外空間 |
| 較浪費空間(沒映射到位址就會一直是空) | 有效利用空間(碰撞後可以補至其他未映射的空間) |
| 鏈結暫存效能較差 | 效能較佳因為都在同一個表格(空間)中 |

### (四)溢位分析

#### 討論chain平均複雜度
假設有m個桶子，n筆資料，負載密度a(平均link長度) = n / m 【chain沒有槽的問題】
平均搜尋桶子內的link時間:(最短為1(第一個就查到)+最長為 a)/2
= 1+(a/2)

## 三、動態雜湊
### (一)目錄(資料夾)雜湊
假設一個link可以存2筆資料

(a)只插入a0,b0,c2,a1,b1,c3
a0,b0:最後2個bit為00
c2:最後2個bit為10
a1,b1:最後2個bit為01
c3:最後2個bit為11
【沒有任何一個點，超過２筆資料無溢位】

---
假設c5 110 101
(b)在剛剛a0,b0,c2,a1,b1,c3再多插入c5
c5:最後2個bit為01【此時產生溢位，3筆資料】
【目錄(資料夾) double(2^3) 改成看最後3個bit】
a0,b0:最後2個bit為00
c2:最後2個bit為10
a1,b1:最後3個bit為001
c5:最後3個bit為101
c3:最後2個bit為11

---
(c)在剛剛a0,b0,c2,a1,b1,c3,c5再多插入c1
c1:最後3個bit為001【此時產生溢位，3筆資料】
【目錄(資料夾) double(2^4) 改成看最後4個bit】
a0,b0:最後2個bit為00
c2:最後2個bit為10
a1,c1:最後4個bit為0001
b1:最後3個bit為001
c5:最後3個bit為101
c3:最後2個bit為11

---
### (二)評估目錄(資料夾)雜湊
#### 1、遇到overflow會加大目錄(資料夾)並不影響其他未溢位的資料。
#### 2、溢位處理的優點:
##### (1)增加的空間其實沒有很大
##### (2)更新的話只有局部更新不用全部更新。

### (三)沒有(少)目錄(資料夾)雜湊
沒有目錄雜湊，跟第一種方式比較缺少了link，改成直接存取。
溢位時則新增一格新的位置並重新rehash，因並非目錄故為『沒有目錄』。

//個人理解為(少目錄)因為功能有些相似目錄，比較好理解溢位時的處理。

> 參考資料:Fundamentals of Data Structures in C by Ellis Horowitz, Sartaj Sahni, Susan Anderson-Freed