Hash Table

อยากรู้เร็ว ๆ ว่าข้อมูลชิ้นหนึ่งอยู่ในคอลเลกชันหรือไม่ — hash table ทำได้ในเวลา Θ(1) โดยเฉลี่ย

ทำไมต้องมี hash table

ตัวอย่าง: ระบบลานจอดรถบันทึกทะเบียนรถเข้า–ออก อยากเช็คว่ารถคันนี้อยู่ในลานหรือไม่

Direct-address table

เอาค่า key ไปเป็น index ของ array ตรง ๆ

void insert(int key, String data) { a[key] = data; }
void delete(int key)              { a[key] = null; }
String search(int key)            { return a[key]; }

ค้นหาได้ O(1) แต่มีปัญหาใหญ่:

วิธีบรรเทา: แม็ป key ให้เล็กลงก่อน

key อยู่ในช่วง 150000–159999
array index = key - 150000       // เหลือ 0–9999

นี่คือรูปแบบง่ายที่สุดของ hash function

Hashing คืออะไร

• Hashing = การแม็ปข้อมูลชุดใหญ่ที่มีความยาวไม่คงที่ (เรียกว่า key) ให้เป็นค่าชุดเล็กที่มีความยาวคงที่
• Hash table คือโครงสร้างข้อมูลที่ใช้ hash function แม็ป key ไปหา value
• ใช้ใน associative array, database index, cache, set

key  →  [ hash function ]  →  hash value (index ในตาราง)

Hash function

f(key) = key % 10

11000 % 10 = 0
11001 % 10 = 1
…
11339 % 10 = 9

แล้วถ้ามี 1 กับ 11 ล่ะ? ทั้งคู่ได้ index 1 เหมือนกัน — เรียกว่า collision (การชนกัน)

Hash function ที่ไม่ดี

hash(053920299) = 39
hash(053943811) = 31

Perfect hash function = แม็ปแบบหนึ่งต่อหนึ่ง ไม่มี collision เลย ทำได้ต่อเมื่อรู้ key ทั้งหมดล่วงหน้า (Minimal perfect hash = ขนาดตารางเท่ากับจำนวน key พอดี)

Uniform / Division / Multiplication

Uniform hash function

ถ้า key กระจายสม่ำเสมอในช่วง [0, X) และตารางมีขนาด m

hash(key) = key × (m / X)

X = 10, m = 5, key = 5
hash(5) = 5 × 5/10 = 2

Division method (นิยมที่สุด)

hash(key) = key % m

Multiplication method

ให้ A เป็นเศษส่วน 0 < A < 1

hash(key) = m × ( key×A - ⌊key×A⌋ )   // เอาเฉพาะส่วนทศนิยมของ key×A

Hashing สตริง

ข้อมูลจริงมักไม่ใช่ตัวเลข เช่นชื่อคน ทะเบียนรถ เลขพาสปอร์ต — ต้องแปลงเป็นตัวเลขก่อน

int hash1(String str){
    int sum = 0;
    for(int i = 0; i < str.length(); i++){
        // บวกค่า ASCII
        sum += str.charAt(i);
    }
    return sum % SIZE_OF_TABLE;
}

hash1("Tan Ah Teck")
 = (84+97+110+32+65+104+32+84+101+99+107) % 11
 = 915 % 11
 = 0

Adian  → 65+100+105+97+110 = 477
Diana  → 68+105+97+110+97  = 477
Nadia  → 78+97+100+105+97  = 477

แก้ด้วยการ "เลื่อน" ผลรวมก่อนบวกตัวถัดไป ให้ตำแหน่งมีผลต่อค่า:

int hash2(String str){
    int sum = 0;
    for(int i = 0; i < str.length(); i++){
        sum = (sum * 37) + str.charAt(i);
    }
    return sum % SIZE_OF_TABLE;
}

Adian → 127,033,209
Diana → 132,898,473
Nadia → 151,238,781      // ต่างกันแล้ว

Collision resolution — ภาพรวม

Separate Chaining

ช่องที่ชนกันเก็บเป็น linked list ต่อกันไป

f(key) = key % 10

index 0:  10  →  null
index 1:   1  →  11  →  null
index 3:  43  →  53  →  null

Linear Probing

ชนแล้วเลื่อนไปช่องว่างถัดไปเรื่อย ๆ วนกลับมาต้นตารางเมื่อถึงช่องสุดท้าย

A[0]=14  A[1]=21  A[2]=1  A[3]=35  A[4]=18

ค้นหา 35: เริ่มที่ 0 แล้วไล่ไปเรื่อย ๆ เจอที่ probe ที่ 4

ค้นหา 8 (hash = 1): ไล่จนเจอช่องว่าง จึงสรุปว่าไม่มี — ใช้ 5 probes

เวลาแทรกค่าใหม่ ถ้าเจอช่องที่ถูกทำเครื่องหมาย deleted ต้องไล่ตรวจต่อให้แน่ใจว่าไม่มีค่าเดิมอยู่แล้ว จากนั้นค่อยใส่ในช่องว่างช่องแรกที่เจอ

Quadratic Probing

ชนแล้วกระโดดเป็นระยะกำลังสอง

hash(key)
(hash(key) + 1)  % m
(hash(key) + 4)  % m
(hash(key) + 9)  % m
…
(hash(key) + k²) % m

ใส่ 18 → 18%7 = 4  → A[4]
ใส่ 3  → 3%7  = 3  → A[3]
ใส่ 38 → 38%7 = 3  → ชน!
       (3+1)%7 = 4     → ชนอีก (18 อยู่)
       (3+4)%7 = 0     → ว่าง → ลง A[0]

Double Hashing

ใช้ hash ตัวที่สองกำหนดระยะกระโดด ทำให้ key ต่างกันมีลำดับ probe ต่างกัน

hash(key)
(hash(key) + 1 × hash2(key)) % m
(hash(key) + 2 × hash2(key)) % m
(hash(key) + 3 × hash2(key)) % m
…

hash2 เรียกว่า secondary hash function

Load factor (∝)

∝ = n / m

n = จำนวน key ทั้งหมดที่ใส่ในตาราง
m = ขนาดตาราง (จำนวนช่อง)

• บอกว่าตารางแน่นแค่ไหน
• ใน separate chaining ∝ คือความยาวเฉลี่ยของ linked list