Hash table

Bài Big-O nói containsKey của HashMap chỉ tốn một bước, dù map có một triệu key. Tìm trong ArrayList thì phải so từng phần tử. HashMap nhanh hơn vì bên trong nó là một hash table.

Khái niệm

🗳️ Hash table (bảng băm): một array các ô (bucket), mỗi key được xếp vào đúng một ô để khi tìm chỉ cần xem ô đó.

🎲 Hàm băm (hash function): hàm biến một key thành một con số, dùng con số đó để chọn ô chứa key.

🚧 Va chạm (collision): hai key khác nhau được hàm băm đưa vào cùng một ô.

HashMap<K, V> và HashSet<E> của Java đều là hash table.

Ví dụ

Một bản HashMap tối giản lưu tồn kho theo tên, dùng hàm băm rất đơn giản là độ dài tên chia lấy dư cho số ô:

// Main.java
void main() {
    MiniMap stock = new MiniMap();
    stock.put("Bút bi", 120);
    stock.put("Vở", 0);
    stock.put("Balo", 8);
    System.out.println(stock.get("Vở"));   // 0
}

// Entry.java
class Entry {
    private String key;
    private int value;

    public Entry(String key, int value) {
        this.key = key;
        this.value = value;
    }

    public String getKey() { return key; }
    public int getValue() { return value; }
    public void setValue(int value) {
        this.value = value;
    }
}

// MiniMap.java
import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;

class MiniMap {
    private final List<List<Entry>> buckets =
        new ArrayList<>();

    public MiniMap() {
        for (int i = 0; i < 4; i++) {
            buckets.add(new ArrayList<>());
        }
    }

    public int bucketOf(String key) {
        return key.length() % buckets.size();
    }

    public void put(String key, int value) {
        List<Entry> bucket = buckets.get(bucketOf(key));
        for (Entry e : bucket) {
            if (e.getKey().equals(key)) {
                e.setValue(value);
                return;
            }
        }
        bucket.add(new Entry(key, value));
    }

    public int get(String key) {
        for (Entry e : buckets.get(bucketOf(key))) {
            if (e.getKey().equals(key)) {
                return e.getValue();
            }
        }
        throw new NoSuchElementException(key);
    }
}

buckets là list 4 ô, mỗi ô là một list các cặp key-value. Constructor tạo sẵn list rỗng cho từng ô.
bucketOf là hàm băm: "Vở" dài 2 ký tự, 2 % 4 bằng 2, nên nằm ở ô 2.
put và get chỉ duyệt đúng một ô. Mỗi ô chỉ có vài phần tử nên gần như là O(1). Key so bằng equals, không so bằng ==.
Không có key thì ném NoSuchElementException. HashMap thật thì trả null, như bài Map của khoá Java Core.

Sau ba lần put: Bút bi và Vở cùng rơi vào ô 2

Hàm băm thật của Java là method hashCode(), dùng mọi ký tự của key, nên các key rải đều ra các ô. Khi số phần tử quá nhiều so với số ô, HashMap tự gấp đôi số ô và xếp lại, giống ArrayList đổi sang array lớn hơn.

Thử ngay

Thay thân main bằng đoạn in ra ô của từng sản phẩm:

MiniMap table = new MiniMap();
System.out.println(table.bucketOf("Bút bi"));
System.out.println(table.bucketOf("Vở"));
System.out.println(table.bucketOf("Balo"));
System.out.println(table.bucketOf("Thước"));
System.out.println(table.bucketOf("Máy tính"));

Đoán trước khi chạy: ngoài "Bút bi" và "Vở", còn cặp nào rơi vào cùng một ô?

Xem kết quả

"Bút bi" (6 ký tự) và "Vở" (2 ký tự) cùng ở ô 2. "Balo" (4) và "Máy tính" (8) cùng ở ô 0.

Đó là va chạm: tìm trong ô này phải so từng key trong list của ô. Nếu mọi key rơi vào một ô, hash table chậm như duyệt list, O(n).

Lỗi hay gặp

Dùng object của class làm key. Bài Kiểu nguyên thuỷ và kiểu tham chiếu của khoá Java Core đã cho thấy hai object khác nhau thì không bằng nhau, dù dữ liệu giống hệt. Mặc định, HashMap cũng băm và so key theo tham chiếu.

// SAI — tạo object mới thì không tìm lại được
// Main.java
void main() {
    Map<ProductCode, Long> prices = new HashMap<>();
    prices.put(new ProductCode("PEN-01"), 5000L);
    System.out.println(prices.containsKey(
        new ProductCode("PEN-01")));   // false
}

// ProductCode.java
class ProductCode {
    private String sku;

    public ProductCode(String sku) {
        this.sku = sku;
    }
}

// ĐÚNG — dùng chính mã String làm key
Map<String, Long> prices = new HashMap<>();
prices.put("PEN-01", 5000L);
System.out.println(prices.containsKey("PEN-01"));
// true

Muốn dùng class làm key thì class đó phải @Override hai method equals và hashCode để so theo dữ liệu. String đã làm sẵn việc này.

Tóm tắt

Hash table là array các ô. Hàm băm chọn ô cho từng key.
Tra, thêm, xoá theo key trung bình là O(1).
Va chạm là chuyện bình thường. Mọi key cùng một ô thì chậm thành O(n).
Key là object của class thì so theo tham chiếu, trừ khi class override equals và hashCode.

Khái niệm

🗳️ Hash table (bảng băm): một array các ô (bucket), mỗi key được xếp vào đúng một ô để khi tìm chỉ cần xem ô đó.

🎲 Hàm băm (hash function): hàm biến một key thành một con số, dùng con số đó để chọn ô chứa key.

🚧 Va chạm (collision): hai key khác nhau được hàm băm đưa vào cùng một ô.

HashMap<K, V> và HashSet<E> của Java đều là hash table.

Ví dụ

Một bản HashMap tối giản lưu tồn kho theo tên, dùng hàm băm rất đơn giản là độ dài tên chia lấy dư cho số ô:

// Main.java
void main() {
    MiniMap stock = new MiniMap();
    stock.put("Bút bi", 120);
    stock.put("Vở", 0);
    stock.put("Balo", 8);
    System.out.println(stock.get("Vở"));   // 0
}

// Entry.java
class Entry {
    private String key;
    private int value;

    public Entry(String key, int value) {
        this.key = key;
        this.value = value;
    }

    public String getKey() { return key; }
    public int getValue() { return value; }
    public void setValue(int value) {
        this.value = value;
    }
}

// MiniMap.java
import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;

class MiniMap {
    private final List<List<Entry>> buckets =
        new ArrayList<>();

    public MiniMap() {
        for (int i = 0; i < 4; i++) {
            buckets.add(new ArrayList<>());
        }
    }

    public int bucketOf(String key) {
        return key.length() % buckets.size();
    }

    public void put(String key, int value) {
        List<Entry> bucket = buckets.get(bucketOf(key));
        for (Entry e : bucket) {
            if (e.getKey().equals(key)) {
                e.setValue(value);
                return;
            }
        }
        bucket.add(new Entry(key, value));
    }

    public int get(String key) {
        for (Entry e : buckets.get(bucketOf(key))) {
            if (e.getKey().equals(key)) {
                return e.getValue();
            }
        }
        throw new NoSuchElementException(key);
    }
}

buckets là list 4 ô, mỗi ô là một list các cặp key-value. Constructor tạo sẵn list rỗng cho từng ô.
bucketOf là hàm băm: "Vở" dài 2 ký tự, 2 % 4 bằng 2, nên nằm ở ô 2.
put và get chỉ duyệt đúng một ô. Mỗi ô chỉ có vài phần tử nên gần như là O(1). Key so bằng equals, không so bằng ==.
Không có key thì ném NoSuchElementException. HashMap thật thì trả null, như bài Map của khoá Java Core.

Sau ba lần put: Bút bi và Vở cùng rơi vào ô 2

Thử ngay

Thay thân main bằng đoạn in ra ô của từng sản phẩm:

MiniMap table = new MiniMap();
System.out.println(table.bucketOf("Bút bi"));
System.out.println(table.bucketOf("Vở"));
System.out.println(table.bucketOf("Balo"));
System.out.println(table.bucketOf("Thước"));
System.out.println(table.bucketOf("Máy tính"));

Đoán trước khi chạy: ngoài "Bút bi" và "Vở", còn cặp nào rơi vào cùng một ô?

Xem kết quả

"Bút bi" (6 ký tự) và "Vở" (2 ký tự) cùng ở ô 2. "Balo" (4) và "Máy tính" (8) cùng ở ô 0.

Đó là va chạm: tìm trong ô này phải so từng key trong list của ô. Nếu mọi key rơi vào một ô, hash table chậm như duyệt list, O(n).

Lỗi hay gặp

// SAI — tạo object mới thì không tìm lại được
// Main.java
void main() {
    Map<ProductCode, Long> prices = new HashMap<>();
    prices.put(new ProductCode("PEN-01"), 5000L);
    System.out.println(prices.containsKey(
        new ProductCode("PEN-01")));   // false
}

// ProductCode.java
class ProductCode {
    private String sku;

    public ProductCode(String sku) {
        this.sku = sku;
    }
}

// ĐÚNG — dùng chính mã String làm key
Map<String, Long> prices = new HashMap<>();
prices.put("PEN-01", 5000L);
System.out.println(prices.containsKey("PEN-01"));
// true

Muốn dùng class làm key thì class đó phải @Override hai method equals và hashCode để so theo dữ liệu. String đã làm sẵn việc này.

Tóm tắt

Hash table là array các ô. Hàm băm chọn ô cho từng key.
Tra, thêm, xoá theo key trung bình là O(1).
Va chạm là chuyện bình thường. Mọi key cùng một ô thì chậm thành O(n).
Key là object của class thì so theo tham chiếu, trừ khi class override equals và hashCode.

Khái niệm

Ví dụ

Thử ngay

Lỗi hay gặp

Tóm tắt

Tự kiểm tra

Hash table

Khái niệm

Ví dụ

Thử ngay

Lỗi hay gặp

Tóm tắt

Tự kiểm tra