Bảng băm (hash table)

1class HashTable:2    def __init__(self, size=8):3        self.size = size4        self.buckets = [[] for _ in range(size)]5
6    def _index(self, key):7        # Hash the key to a bucket; different keys can collide8        return sum(ord(ch) for ch in key) % self.size9
10    def set(self, key, value):11        bucket = self.buckets[self._index(key)]12        for i, (k, _) in enumerate(bucket):13            if k == key:14                bucket[i] = (key, value)  # update existing key15                return16        bucket.append((key, value))  # chain on collision17
18    def get(self, key):19        for k, v in self.buckets[self._index(key)]:20            if k == key:21                return v22        raise KeyError(key)23
24    def delete(self, key):25        bucket = self.buckets[self._index(key)]26        for i, (k, _) in enumerate(bucket):27            if k == key:28                del bucket[i]29                return30        raise KeyError(key)31
32
33table = HashTable()34table.set("apple", 3)35table.set("banana", 7)36table.set("cherry", 5)37
38print("apple  ->", table.get("apple"))39print("banana ->", table.get("banana"))40table.set("apple", 10)41print("apple  ->", table.get("apple"))42table.delete("banana")43print("bucket sizes:", [len(b) for b in table.buckets])

1class HashTable {2    constructor(size = 8) {3        this.size = size;4        this.buckets = Array.from({ length: size }, () => []);5    }6
7    // Fold character codes into a bucket index8    hash(key) {9        let h = 0;10        for (const ch of key) h = (h * 31 + ch.charCodeAt(0)) % this.size;11        return h;12    }13
14    set(key, value) {15        const bucket = this.buckets[this.hash(key)];16        const pair = bucket.find(([k]) => k === key);17        if (pair) pair[1] = value;18        else bucket.push([key, value]); // Separate chaining on collision19    }20
21    get(key) {22        const bucket = this.buckets[this.hash(key)];23        const pair = bucket.find(([k]) => k === key);24        return pair ? pair[1] : undefined;25    }26
27    delete(key) {28        const bucket = this.buckets[this.hash(key)];29        const index = bucket.findIndex(([k]) => k === key);30        if (index === -1) return false;31        bucket.splice(index, 1);32        return true;33    }34}35
36const table = new HashTable();37table.set("apple", 3);38table.set("banana", 7);39table.set("cherry", 5);40table.set("apple", 4);41console.log("apple ->", table.get("apple"));42console.log("banana in bucket", table.hash("banana"));43table.delete("cherry");44console.log("cherry after delete:", table.get("cherry"));

1public class Main {2    static class Entry {3        String key; int value;4        Entry next; // chain for keys sharing a bucket5        Entry(String key, int value) { this.key = key; this.value = value; }6    }7
8    static final int CAPACITY = 8;9    static Entry[] buckets = new Entry[CAPACITY];10
11    static int index(String key) { return Math.abs(key.hashCode()) % CAPACITY; }12
13    static void put(String key, int value) {14        int i = index(key);15        for (Entry e = buckets[i]; e != null; e = e.next) {16            if (e.key.equals(key)) { e.value = value; return; }17        }18        Entry entry = new Entry(key, value);19        entry.next = buckets[i]; // prepend to the chain20        buckets[i] = entry;21    }22
23    static Integer get(String key) {24        for (Entry e = buckets[index(key)]; e != null; e = e.next) {25            if (e.key.equals(key)) return e.value;26        }27        return null;28    }29
30    static void remove(String key) {31        int i = index(key);32        Entry prev = null;33        for (Entry e = buckets[i]; e != null; prev = e, e = e.next) {34            if (e.key.equals(key)) {35                if (prev == null) buckets[i] = e.next;36                else prev.next = e.next;37                return;38            }39        }40    }41
42    public static void main(String[] args) {43        put("apple", 3); put("banana", 7); put("cherry", 5);44        System.out.println("apple -> " + get("apple"));45        put("apple", 10); // update in place46        System.out.println("apple -> " + get("apple"));47        remove("banana");48        System.out.println("banana -> " + get("banana"));49    }50}

1#include <iostream>2#include <string>3#include <vector>4
5struct HashTable {6    static constexpr int CAPACITY = 8;7    // Separate chaining: each bucket holds (key, value) pairs8    std::vector<std::vector<std::pair<std::string, int>>> buckets{CAPACITY};9
10    size_t hash(const std::string& key) const {11        size_t h = 0;12        for (char c : key) h = h * 31 + static_cast<unsigned char>(c);13        return h % CAPACITY;14    }15
16    void set(const std::string& key, int value) {17        auto& bucket = buckets[hash(key)];18        for (auto& entry : bucket) {19            if (entry.first == key) {20                entry.second = value;  // update existing key21                return;22            }23        }24        bucket.push_back({key, value});25    }26
27    const int* get(const std::string& key) const {28        for (const auto& entry : buckets[hash(key)]) {29            if (entry.first == key) return &entry.second;30        }31        return nullptr;32    }33
34    void erase(const std::string& key) {35        auto& bucket = buckets[hash(key)];36        for (size_t i = 0; i < bucket.size(); ++i) {37            if (bucket[i].first == key) {38                bucket.erase(bucket.begin() + i);39                return;40            }41        }42    }43};44
45int main() {46    HashTable table;47    table.set("apple", 3);48    table.set("banana", 7);49    table.set("apple", 4);  // overwrites the old value50    for (const std::string& key : {"apple", "banana", "grape"}) {51        const int* value = table.get(key);52        if (value != nullptr) std::cout << key << " = " << *value << "\n";53        else std::cout << key << " not found\n";54    }55    table.erase("banana");56    std::cout << "banana after erase: "57              << (table.get("banana") ? "found" : "not found") << "\n";58    return 0;59}

1#include <stdio.h>2#include <stdlib.h>3#include <string.h>4
5#define CAPACITY 86
7// Separate chaining: each bucket is a linked list of entries8typedef struct Entry {9    char key[16];10    int value;11    struct Entry* next;12} Entry;13
14Entry* buckets[CAPACITY];15
16unsigned int hash(const char* key) {17    unsigned int h = 5381;  // djb2, then modulo the bucket count18    for (; *key; key++) h = h * 33 + (unsigned char)*key;19    return h % CAPACITY;20}21
22void set(const char* key, int value) {23    unsigned int i = hash(key);24    for (Entry* e = buckets[i]; e != NULL; e = e->next) {25        if (strcmp(e->key, key) == 0) {26            e->value = value;  // update existing key27            return;28        }29    }30    Entry* e = malloc(sizeof(Entry));31    strcpy(e->key, key);32    e->value = value;33    e->next = buckets[i];34    buckets[i] = e;35}36
37int* get(const char* key) {38    for (Entry* e = buckets[hash(key)]; e != NULL; e = e->next) {39        if (strcmp(e->key, key) == 0) return &e->value;40    }41    return NULL;42}43
44void removeKey(const char* key) {45    Entry** link = &buckets[hash(key)];46    while (*link != NULL) {47        if (strcmp((*link)->key, key) == 0) {48            Entry* old = *link;49            *link = old->next;50            free(old);51            return;52        }53        link = &(*link)->next;54    }55}56
57void printBuckets(void) {58    for (int i = 0; i < CAPACITY; i++) {59        printf("bucket %d:", i);60        for (Entry* e = buckets[i]; e != NULL; e = e->next) {61            printf(" (%s=%d)", e->key, e->value);62        }63        printf("\n");64    }65}66
67int main(void) {68    set("apple", 3);69    set("banana", 7);70    set("apple", 4);  // overwrites the old value71    set("grape", 9);72    printBuckets();73    int* value = get("apple");74    printf("get(apple): %d\n", value ? *value : -1);75    removeKey("banana");76    printf("banana after remove: %s\n", get("banana") ? "found" : "not found");77    return 0;78}