BÀI TOÁN : 

Viết mã nguồn Python minh họa trọn vẹn cách tự xây dựng một Bảng băm (Hash Table) từ đầu, cùng cơ chế xử lý đụng độ bằng phương pháp Tách chuỗi (Chaining) để quản lý và tìm kiếm thông tin của 10 loại quả trong xưởng chế biến.

Mã nguồn Python

class FruitHashTable:

    def __init__(self, capacity=5):
        # Tạo mảng lưu trữ gồm 5 ô (Bucket). Ban đầu mỗi ô chứa 1 list rỗng.
        self.capacity = capacity
        self.buckets = [[] for _ in range(self.capacity)]

    def _hash_function(self, fruit_name: str) -> int:
        """Hàm băm: Chuyển tên quả thành chỉ số ô nhớ (Index)"""
        # Bước 1: Tính tổng mã ASCII của các ký tự trong tên quả
        ascii_sum = sum(ord(char) for char in fruit_name)

        # Bước 2: Dùng phép chia lấy dư (Modulo) để đưa giá trị về phạm vi [0, capacity - 1]
        index = ascii_sum % self.capacity
        return index

    def insert(self, fruit_name: str, quantity_kg: float, price_per_kg: int):
        """Thêm hoặc cập nhật thông tin loại quả vào Bảng băm - O(1)"""
        index = self._hash_function(fruit_name)
        bucket = self.buckets[index]

        # Kiểm tra xem loại quả này đã có trong Bucket chưa
        for i, item in enumerate(bucket):
            if item["name"] == fruit_name:
                # Cập nhật thông tin nếu đã tồn tại
                bucket[i] = {
                    "name": fruit_name,
                    "qty": quantity_kg,
                    "price": price_per_kg,
                }
                return

        # Nếu chưa có, thêm vào danh sách tại ô đó (xử lý đụng độ băm)
        bucket.append(
            {"name": fruit_name, "qty": quantity_kg, "price": price_per_kg}
        )

    def search(self, fruit_name: str):
        """Tìm kiếm thông tin loại quả - Trung bình O(1)"""
        index = self._hash_function(fruit_name)
        bucket = self.buckets[index]

        # Chỉ kiểm tra trong đúng ô (Bucket) đã băm ra
        for item in bucket:
            if item["name"] == fruit_name:
                return item

        return None  # Không tìm thấy


# ==============================================================================
# DEMO THỰC HÀNH VỚI 10 LOẠI QUẢ TRONG XƯỞNG CHẾ BIẾN
# ==============================================================================

# 1. Khởi tạo Bảng băm cố định 5 ô nhớ để quan sát hiện tượng đụng độ
fruit_system = FruitHashTable(capacity=5)

# 2. Danh sách 10 loại quả trong xưởng
fruits_data = [
    ("Xoài Cát", 1500, 35000),
    ("Thanh Long", 2200, 18000),
    ("Sầu Riêng", 800, 120000),
    ("Măng Cụt", 600, 50000),
    ("Bưởi Da Xanh", 1100, 40000),
    ("Dứa", 3000, 12000),
    ("Nhãn Ido", 1800, 25000),
    ("Vải Thiều", 2500, 30000),
    ("Cam Sành", 2000, 22000),
    ("Chanh Dây", 900, 15000),
]

# Nạp dữ liệu vào Bảng băm
for name, qty, price in fruits_data:
    fruit_system.insert(name, qty, price)

# 3. Hiển thị sơ đồ phân bố dữ liệu trong bộ nhớ RAM (Buckets)
print("=" * 60)
print("SƠ ĐỒ LƯU TRỮ TRONG BỘ NHỚ RAM (5 BUCKETS):")
print("=" * 60)
for idx, bucket in enumerate(fruit_system.buckets):
    items_in_bucket = [item["name"] for item in bucket]
    print(f"Bucket [{idx}]: {items_in_bucket}")

# 4. Thực hành tìm kiếm tức thì O(1)
print("\n" + "=" * 60)
print("KẾT QUẢ TÌM KIẾM THÔNG TIN:")
print("=" * 60)

search_targets = ["Măng Cụt", "Cam Sành", "Táo Nhập Khẩu"]

for target in search_targets:
    target_index = fruit_system._hash_function(target)
    result = fruit_system.search(target)

    if result:
        print(f"➕ Tìm thấy '{target}':")
        print(
            f"   - Vị trí ô nhớ (Index): {target_index} (Tính từ Hash Function)"
        )
        print(
            f"   - Tồn kho: {result['qty']} kg | Giá nhập: {result['price']:,} VNĐ/kg\n"
        )
    else:
        print(f"❌ Không tìm thấy '{target}' trong xưởng.")
        print(f"   - Vị trí ô nhớ tính toán: {target_index} (Ô này rỗng/không chứa {target})\n")

2. Tại sao việc tìm kiếm lại đạt tốc độ $O(1)$?

Khi gọi hàm search("Măng Cụt"):

1. Bước 1: _hash_function("Măng Cụt") thực hiện phép toán ASCII % 5 $\rightarrow$ Trả về ngay lập tức chỉ số Index = 1.

2. Bước 2: Chương trình nhảy thẳng tới Bucket [1] (bỏ qua hoàn toàn các Bucket 0, 2, 3, 4).

3. Bước 3: Duyệt qua danh sách cực ngắn gồm 2 phần tử ['Thanh Long', 'Măng Cụt'] tại ô 1 để lấy kết quả.

Nhờ không phải so sánh với cả 10 loại quả, tốc độ tìm kiếm giảm thiểu đáng kể và đạt trung bình $O(1)$.