🗂️ Bảng băm (Hash Table)

Mảng cho bạn truy cập O(1) - nhưng chỉ khi biết trước chỉ số (index). Nếu muốn tra cứu bằng một thứ khác - tên người, mã sinh viên, một chuỗi bất kỳ - bạn buộc phải duyệt qua từng phần tử để so sánh, tốn O(n). Hash table giải quyết đúng vấn đề này: nó cho phép tra cứu theo một “khóa” (key) tuỳ ý mà vẫn giữ được tốc độ gần O(1), bằng một mẹo đơn giản - biến key thành một con số, rồi dùng con số đó làm chỉ số mảng.

Ghi chú

Hash table còn được gọi là hash map, dictionary (Python), hoặc associative array. Trong hầu hết ngôn ngữ, nó là cấu trúc dữ liệu bạn dùng “mặc định” mỗi khi cần tra cứu nhanh theo key: dict trong Python, Map/HashMap trong Kotlin/Java, Dictionary trong Swift.

Hàm băm biến key thành chỉ số

Mọi hash table đều dựa trên một hàm băm (hash function): nhận vào một key (chuỗi, số, hay bất kỳ kiểu dữ liệu nào), trả về một con số nguyên. Từ con số đó, lấy phần dư cho dung lượng mảng (capacity) để ra chỉ số cần lưu:

index = hash(key) % capacity

Python

person = {}
person["name"] = "John"   # Python tự tính hash("name"), tìm ô tương ứng để lưu
print(person["name"])     # tính lại hash("name"), nhảy thẳng đến đúng ô -> O(1)

C++

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

int main() {
    unordered_map<string, string> person;
    person["name"] = "John";   // C++ tự tính hash("name"), tìm ô tương ứng để lưu
    cout << person["name"] << endl;  // tính lại hash("name"), nhảy thẳng đến đúng ô -> O(1)
    return 0;
}

Java

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, String> person = new HashMap<>();
        person.put("name", "John");   // Java tự tính hash("name"), tìm ô tương ứng để lưu
        System.out.println(person.get("name"));  // tính lại hash("name"), nhảy thẳng đến đúng ô -> O(1)
    }
}

Kotlin

fun main() {
    val person = HashMap<String, String>()
    person["name"] = "John"   // Kotlin tự tính hash("name"), tìm ô tương ứng để lưu
    println(person["name"])   // tính lại hash("name"), nhảy thẳng đến đúng ô -> O(1)
}

Dart

void main() {
  var person = <String, String>{};
  person["name"] = "John";   // Dart tự tính hash("name"), tìm ô tương ứng để lưu
  print(person["name"]);     // tính lại hash("name"), nhảy thẳng đến đúng ô -> O(1)
}

Vì bước “nhảy thẳng đến đúng ô” không phụ thuộc số lượng phần tử đang có trong bảng, việc thêm, tìm, xóa đều đạt độ phức tạp trung bình O(1) - khác hẳn với việc phải dò tuần tự trong mảng hay linked list.

Xung đột: khi hai key trỏ về cùng một ô

Không gian các key có thể có (mọi chuỗi, mọi số) gần như vô hạn, trong khi số ô của mảng luôn hữu hạn. Theo nguyên lý chuồng bồ câu (pigeonhole), sớm muộn sẽ có hai key khác nhau cho ra cùng một index - gọi là xung đột (hash collision). Đây không phải lỗi thiết kế mà là điều không thể tránh khỏi; vấn đề chỉ là xử lý nó thế nào.

Hai cách xử lý phổ biến:

Separate chaining (nối chuỗi): mỗi ô không chứa trực tiếp một cặp key-value, mà chứa một danh sách nhỏ các cặp bị rơi vào cùng ô đó. Khi tra cứu, tính index xong thì duyệt qua danh sách ngắn ấy để tìm đúng key.

Python

class HashMapChaining:
    def __init__(self, capacity=8):
        self.buckets = [[] for _ in range(capacity)]  # mỗi ô là 1 danh sách

    def _index(self, key):
        return hash(key) % len(self.buckets)

    def put(self, key, value):
        bucket = self.buckets[self._index(key)]
        for pair in bucket:
            if pair[0] == key:      # key đã tồn tại -> cập nhật
                pair[1] = value
                return
        bucket.append([key, value])  # key mới -> thêm vào cuối danh sách

    def get(self, key):
        bucket = self.buckets[self._index(key)]
        for k, v in bucket:
            if k == key:
                return v
        return None

C++

#include <vector>
#include <string>
#include <functional>
using namespace std;

class HashMapChaining {
public:
    HashMapChaining(int capacity = 8) : buckets(capacity) {}  // mỗi ô là 1 danh sách

    void put(const string& key, const string& value) {
        auto& bucket = buckets[index(key)];
        for (auto& pair : bucket) {
            if (pair.first == key) {      // key đã tồn tại -> cập nhật
                pair.second = value;
                return;
            }
        }
        bucket.push_back({key, value});   // key mới -> thêm vào cuối danh sách
    }

    string get(const string& key) {
        auto& bucket = buckets[index(key)];
        for (auto& pair : bucket) {
            if (pair.first == key) {
                return pair.second;
            }
        }
        return "";
    }

private:
    vector<vector<pair<string, string>>> buckets;

    int index(const string& key) {
        return hash<string>{}(key) % buckets.size();
    }
};

Java

import java.util.ArrayList;
import java.util.List;

public class HashMapChaining {
    private List<List<Object[]>> buckets;

    public HashMapChaining(int capacity) {
        buckets = new ArrayList<>();
        for (int i = 0; i < capacity; i++) {
            buckets.add(new ArrayList<>());  // mỗi ô là 1 danh sách
        }
    }

    private int index(String key) {
        return Math.floorMod(key.hashCode(), buckets.size());
    }

    public void put(String key, String value) {
        List<Object[]> bucket = buckets.get(index(key));
        for (Object[] pair : bucket) {
            if (pair[0].equals(key)) {      // key đã tồn tại -> cập nhật
                pair[1] = value;
                return;
            }
        }
        bucket.add(new Object[]{key, value});  // key mới -> thêm vào cuối danh sách
    }

    public String get(String key) {
        List<Object[]> bucket = buckets.get(index(key));
        for (Object[] pair : bucket) {
            if (pair[0].equals(key)) {
                return (String) pair[1];
            }
        }
        return null;
    }
}

Kotlin

class HashMapChaining(capacity: Int = 8) {
    private val buckets = MutableList(capacity) { mutableListOf<Pair<String, String>>() }  // mỗi ô là 1 danh sách

    private fun index(key: String): Int = Math.floorMod(key.hashCode(), buckets.size)

    fun put(key: String, value: String) {
        val bucket = buckets[index(key)]
        for (i in bucket.indices) {
            if (bucket[i].first == key) {      // key đã tồn tại -> cập nhật
                bucket[i] = key to value
                return
            }
        }
        bucket.add(key to value)  // key mới -> thêm vào cuối danh sách
    }

    fun get(key: String): String? {
        val bucket = buckets[index(key)]
        for ((k, v) in bucket) {
            if (k == key) return v
        }
        return null
    }
}

Dart

class HashMapChaining {
  late List<List<List<dynamic>>> buckets;

  HashMapChaining({int capacity = 8}) {
    buckets = List.generate(capacity, (_) => []);  // mỗi ô là 1 danh sách
  }

  int _index(String key) => key.hashCode % buckets.length;

  void put(String key, String value) {
    var bucket = buckets[_index(key)];
    for (var pair in bucket) {
      if (pair[0] == key) {      // key đã tồn tại -> cập nhật
        pair[1] = value;
        return;
      }
    }
    bucket.add([key, value]);  // key mới -> thêm vào cuối danh sách
  }

  String? get(String key) {
    var bucket = buckets[_index(key)];
    for (var pair in bucket) {
      if (pair[0] == key) return pair[1];
    }
    return null;
  }
}

Open addressing (địa chỉ mở): không dùng danh sách phụ, mà khi một ô đã có người ở, thử ô kế tiếp theo một quy luật nào đó cho đến khi tìm được ô trống - cách đơn giản nhất là linear probing: thử lần lượt index + 1, index + 2, …

Chú ý

Càng nhiều xung đột, chuỗi trong mỗi ô càng dài (hoặc phải dò càng nhiều ô), khiến độ phức tạp trung bình O(1) trượt dần về O(n) ở trường hợp xấu nhất. Vì vậy hash table luôn tự mở rộng dung lượng (resize) khi tỷ lệ số phần tử/capacity - gọi là load factor - vượt một ngưỡng nhất định (thường quanh 0.75), rồi băm lại toàn bộ key sang bảng lớn hơn để giữ số lượng xung đột ở mức thấp.

Một hàm băm tốt cần gì?

• Phân bố đều: các key khác nhau nên rải đều khắp các ô, tránh dồn cục gây xung đột nhiều.
• Tính nhanh: hash table tồn tại để nhanh, nên bản thân phép băm không được trở thành nút thắt cổ chai.
• Ổn định: cùng một key luôn cho cùng một giá trị băm, ở mọi lần gọi.

Hàm băm dùng cho hash table thông thường (nhân, XOR, dịch bit…) khác hẳn mục tiêu với các thuật toán băm mật mã như MD5, SHA-256 - loại sau được thiết kế để khó bị đảo ngược và khó cố ý tạo xung đột, nên chậm hơn nhiều và không phù hợp làm hàm băm cho hash table.

Vì sao key phải là kiểu bất biến?

Một hệ quả quan trọng của cách hash table hoạt động: key phải là kiểu dữ liệu bất biến (immutable), hoặc ít nhất là kiểu mà giá trị hash của nó không đổi trong suốt vòng đời làm key.

Lý do: vị trí lưu một key trong bảng được quyết định bởi hash(key) tại thời điểm thêm vào. Nếu sau đó bạn sửa đổi nội dung của key khiến giá trị hash thay đổi, hash table sẽ tìm sai ô khi tra cứu lại - vì nó tính hash mới, trong khi dữ liệu vẫn nằm ở ô ứng với hash cũ.

Python

# list là kiểu mutable -> không dùng được làm key
cache = {}
key = [1, 2]
# cache[key] = "value"  # TypeError: unhashable type: 'list'

# tuple là bất biến -> dùng được làm key
cache[(1, 2)] = "value"
print(cache[(1, 2)])  # "value"

C++

#include <iostream>
#include <map>
#include <vector>
using namespace std;

int main() {
    // vector là kiểu mutable -> nếu sửa nội dung sau khi dùng làm key sẽ tra cứu sai
    map<vector<int>, string> cache;
    vector<int> key = {1, 2};
    // Không nên làm điều này: key có thể bị sửa đổi về sau
    // cache[key] = "value";

    // dùng std::pair làm key thì an toàn hơn (ít bị sửa đổi ngoài ý muốn)
    map<pair<int, int>, string> cache2;
    cache2[{1, 2}] = "value";
    cout << cache2[{1, 2}] << endl;  // "value"
    return 0;
}

Java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        // ArrayList là kiểu mutable -> không nên dùng làm key (hashCode thay đổi nếu sửa nội dung)
        Map<Object, String> cache = new HashMap<>();
        List<Integer> key = new ArrayList<>(List.of(1, 2));
        // cache.put(key, "value");  // hoạt động nhưng RỦI RO nếu key bị sửa đổi sau đó

        // List.of() là bất biến -> dùng được làm key an toàn
        cache.put(List.of(1, 2), "value");
        System.out.println(cache.get(List.of(1, 2)));  // "value"
    }
}

Kotlin

fun main() {
    // MutableList là kiểu mutable -> không nên dùng làm key (hashCode thay đổi nếu sửa nội dung)
    val cache = HashMap<Any, String>()
    val key = mutableListOf(1, 2)
    // cache[key] = "value"  // hoạt động nhưng RỦI RO nếu key bị sửa đổi sau đó

    // List bất biến (listOf) dùng được làm key an toàn
    cache[listOf(1, 2)] = "value"
    println(cache[listOf(1, 2)])  // "value"
}

Dart

void main() {
  // List là kiểu mutable -> không dùng trực tiếp được làm key (so sánh theo identity, không theo nội dung)
  var cache = {};
  var key = [1, 2];
  // cache[key] = "value";  // hoạt động nhưng RỦI RO: tra cứu lại bằng [1, 2] khác sẽ không tìm thấy

  // dùng một chuỗi bất biến đại diện cho (1, 2) làm key thì an toàn
  cache["1,2"] = "value";
  print(cache["1,2"]);  // "value"
}

Chú ý

Đây cũng là lý do vì sao trong Python, dict yêu cầu key phải “hashable” (có __hash__), và các kiểu mutable như list, dict, set không định nghĩa __hash__ - Python chủ động chặn lỗi này ngay từ đầu thay vì để bạn gặp bug âm thầm lúc runtime.

Hai ứng dụng kinh điển

Two Sum - tìm hai số trong mảng có tổng bằng target. Thay vì so mọi cặp (O(n²)), lưu lại những gì đã thấy để tra cứu tức thời:

Python

def two_sum(nums, target):
    seen = {}   # giá trị đã thấy -> chỉ số của nó
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:       # tra cứu O(1) thay vì quét lại từ đầu
            return [seen[complement], i]
        seen[num] = i
    return []

C++

#include <vector>
#include <unordered_map>
using namespace std;

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> seen;  // giá trị đã thấy -> chỉ số của nó
    for (int i = 0; i < (int)nums.size(); i++) {
        int complement = target - nums[i];
        auto it = seen.find(complement);
        if (it != seen.end()) {    // tra cứu O(1) thay vì quét lại từ đầu
            return {it->second, i};
        }
        seen[nums[i]] = i;
    }
    return {};
}

Java

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>();  // giá trị đã thấy -> chỉ số của nó
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (seen.containsKey(complement)) {   // tra cứu O(1) thay vì quét lại từ đầu
                return new int[]{seen.get(complement), i};
            }
            seen.put(nums[i], i);
        }
        return new int[0];
    }
}

Kotlin

fun twoSum(nums: IntArray, target: Int): IntArray {
    val seen = HashMap<Int, Int>()  // giá trị đã thấy -> chỉ số của nó
    for (i in nums.indices) {
        val complement = target - nums[i]
        if (seen.containsKey(complement)) {   // tra cứu O(1) thay vì quét lại từ đầu
            return intArrayOf(seen[complement]!!, i)
        }
        seen[nums[i]] = i
    }
    return intArrayOf()
}

Dart

List<int> twoSum(List<int> nums, int target) {
  var seen = <int, int>{};  // giá trị đã thấy -> chỉ số của nó
  for (int i = 0; i < nums.length; i++) {
    int complement = target - nums[i];
    if (seen.containsKey(complement)) {   // tra cứu O(1) thay vì quét lại từ đầu
      return [seen[complement]!, i];
    }
    seen[nums[i]] = i;
  }
  return [];
}

Đếm tần suất - đếm số lần xuất hiện của mỗi phần tử, chỉ cần một lượt duyệt:

Python

def frequency_count(arr):
    freq = {}
    for num in arr:
        freq[num] = freq.get(num, 0) + 1
    return freq

C++

#include <unordered_map>
#include <vector>

std::unordered_map<int, int> frequency_count(const std::vector<int>& arr) {
    std::unordered_map<int, int> freq;
    for (int num : arr) {
        freq[num]++;
    }
    return freq;
}

Java

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static Map<Integer, Integer> frequencyCount(int[] arr) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : arr) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }
        return freq;
    }
}

Kotlin

fun frequencyCount(arr: IntArray): MutableMap<Int, Int> {
    val freq = mutableMapOf<Int, Int>()
    for (num in arr) {
        freq[num] = (freq[num] ?: 0) + 1
    }
    return freq
}

Dart

Map<int, int> frequencyCount(List<int> arr) {
  final freq = <int, int>{};
  for (final num in arr) {
    freq[num] = (freq[num] ?? 0) + 1;
  }
  return freq;
}

Mẫu số chung: bất cứ khi nào cần “tra cứu xem đã gặp/đếm được bao nhiêu lần”, hash table gần như luôn là lựa chọn đầu tiên.