ตารางแฮชจัดการการชนกัน ตัวประกอบการโหลด และการเปลี่ยนขนาดอย่างไร

Question

Accepted Answer

คีย์ที่แตกต่างกันสองตัวสามารถแฮชไปยัง**ที่เก็บข้อมูลเดียวกัน** — **การชนกัน** ตารางแฮชยังคงอยู่ที่ O(1) โดยเฉลี่ยโดยการแก้ไขการชนกันและ**เปลี่ยนขนาด**ก่อนที่ที่เก็บข้อมูลจะเต็มไปหมด ซึ่งควบคุมโดย**ตัวประกอบการโหลด**

## การแก้ไขการชนกัน

```text
Separate chaining: each bucket holds a list
  [3] -> ("cat",9) -> ("rat",2)   # both hashed to 3

Open addressing: probe to the next free slot
  hash=3 taken -> try 4 -> try 5 ... (linear probing)
```

## ตัวประกอบการโหลดและการเปลี่ยนขนาด

```text
load factor α = number_of_entries / number_of_buckets
α rises -> more collisions -> slower lookups
When α exceeds a threshold (e.g. 0.75):
  -> allocate a bigger array (usually 2x)
  -> REHASH every existing key into new buckets
```

```python
# Conceptual resize
def _resize(self):
    old = self.buckets
    self.buckets = [None] * (len(old) * 2)
    for entry in all_entries(old):
        self._insert(entry.key, entry.value)   # rehash into new array
```

## ความซับซ้อน

| การดำเนินการ | เฉลี่ย | กรณีที่เลวร้ายที่สุด |
|---|---|---|
| ค้นหา / แทรก / ลบ | O(1) | O(n) |
| การเปลี่ยนขนาดครั้งเดียว | — | O(n) |
| แทรก (amortized ด้วยการเปลี่ยนขนาด) | O(1) | — |

การเปลี่ยนขนาดคือ O(n) แต่เกิดขึ้นไม่บ่อย ดังนั้นจึง**ลดลงเหลือ O(1)** ต่อการแทรก

## การแลกเปลี่ยน

- **การลูกโซ่:** ง่าย ลดคุณภาพอย่างนุ่มนวล แต่ใช้ตัวชี้เพิ่มเติมและมีข้อเสียของ cache locality ที่ไม่ดี
- **การสร้างที่อยู่แบบเปิด:** เป็นมิตรกับแคช และกะทัดรัด แต่มีความอ่อนไหวต่อตัวประกอบการโหลดสูงและต้องมีการลบอย่างระมัดระวัง (tombstones)

## ทำไมจึงสำคัญ

ระเบียบภายในเหล่านี้อธิบายว่า*ทำไม*แผนที่แฮชจึงมีความเร็วโดยเฉลี่ยแต่อาจกระโดดไปที่ O(n) — สำคัญสำหรับโค้ดที่ไวต่อประสิทธิภาพและการป้องกันการโจมตีแบบตรรมชาติ (hash-flooding)

การเข้าใจตัวประกอบการโหลดยังอธิบายปุ่มการปรับแต่งหน่วยความจำ/ความเร็วที่เปิดเผยโดยไลบรารีจริง

การดำเนินการ	เฉลี่ย	กรณีที่เลวร้ายที่สุด
ค้นหา / แทรก / ลบ	O(1)	O(n)
การเปลี่ยนขนาดครั้งเดียว	—	O(n)
แทรก (amortized ด้วยการเปลี่ยนขนาด)	O(1)	—