Hash Table là gì? Cách hoạt động, ưu-nhược điểm và ứng dụng

Hash table (hay còn gọi là bảng băm) là một trong những cấu trúc dữ liệu mạnh mẽ và hiệu quả nhất trong khoa học máy tính. Nó cho phép bạn lưu trữ và truy cập dữ liệu một cách cực kỳ nhanh chóng, thường chỉ trong một bước duy nhất. Khả năng này biến hash table thành công cụ không thể thiếu trong nhiều ứng dụng lập trình. Hãy cùng khám phá chi tiết về cấu trúc dữ liệu thú vị này nhé!

CÓ THỂ BẠN QUAN TÂM

Xây dựng ứng dụng hiệu quả với cấu trúc dữ liệu như Hash Table cần nền tảng hạ tầng mạnh mẽ. Để đảm bảo tốc độ cao và ổn định cho ứng dụng của bạn, thuê VPS giá rẻ từ InterData là giải pháp hiệu quả. Với phần cứng chuyên dụng thế hệ mới, bộ xử lý AMD EPYC Gen 3rd, SSD NVMe U.2, băng thông cao, cùng công nghệ ảo hóa tiên tiến, bạn có được cấu hình mạnh, chất lượng cao chỉ từ 3K/Ngày. 

Hash table là gì?

Hash table (hoặc bảng băm) là một cấu trúc dữ liệu fundamental được sử dụng để lưu trữ dữ liệu dưới dạng các cặp khóa-giá trị (key-value pairs). Nó cung cấp một cách hiệu quả để ánh xạ (map) các khóa (key) tới các giá trị (value) tương ứng của chúng.

Mục đích chính của hash table là cung cấp khả năng thực hiện các thao tác cơ bản như thêm mới (insertion), tìm kiếm (searching), và xóa (deletion) dữ liệu với hiệu suất trung bình rất cao, thường được ký hiệu là O(1). Điều này có nghĩa là thời gian thực hiện các thao tác này gần như là hằng số, không tăng đáng kể khi số lượng dữ liệu trong bảng tăng lên.

Để đạt được tốc độ ấn tượng này, hash table sử dụng một "hàm băm" (hash function). Hàm băm này nhận đầu vào là một khóa (key) bất kỳ và tính toán ra một chỉ số (index) hoặc địa chỉ cụ thể trong một cấu trúc lưu trữ nền tảng, thường là một mảng (array).

Mảng nền tảng này bao gồm các vị trí lưu trữ dữ liệu, được gọi là các "bucket" hoặc "slot". Kết quả của hàm băm sẽ cho biết cặp khóa-giá trị tương ứng sẽ được lưu trữ hoặc tìm thấy tại bucket nào trong mảng này.

Hãy hình dung hash table giống như hệ thống tủ giữ đồ tại siêu thị hoặc nhà ga. Mỗi ngăn tủ (bucket) được gán một số duy nhất (index). Chiếc vé bạn nhận (key) không phải là số ngăn, nhưng nó chứa thông tin để người quản lý (hash function) nhanh chóng tính ra bạn đã cất đồ vào ngăn số bao nhiêu.

Khi bạn muốn lấy đồ của mình ra, bạn chỉ cần đưa lại chiếc vé (key). Người quản lý (hash function) lại dùng vé đó để tính toán ra đúng số ngăn (index) bạn đã cất đồ, giúp bạn lấy ra món đồ đó chỉ trong tích tắc mà không phải tốn thời gian lục soát từng ngăn một.

Trong lĩnh vực lập trình, hash table là một trong những cấu trúc dữ liệu cơ bản và mạnh mẽ nhất. Nó là nền tảng cho việc triển khai nhiều cấu trúc dữ liệu thông dụng khác trong các ngôn ngữ lập trình hiện đại, ví dụ điển hình là các kiểu dữ liệu Dictionary trong Python hay Map trong Java và C++.

Các thuật ngữ chuyên ngành:

• Cấu trúc dữ liệu (Data Structure): Là cách tổ chức và lưu trữ dữ liệu trong bộ nhớ máy tính để có thể truy cập và làm việc với chúng một cách hiệu quả.

• Cặp khóa-giá trị (Key-value pairs): Là một bộ gồm hai phần tử liên kết với nhau: khóa (key) dùng để định danh và truy cập dữ liệu, và giá trị (value) là bản thân dữ liệu cần lưu trữ. Mỗi khóa là duy nhất trong một hash table.

• Hàm băm (Hash function): Một hàm toán học hoặc thuật toán nhận đầu vào là một giá trị bất kỳ (khóa) và trả về một số nguyên có kích thước cố định, dùng làm chỉ số trong mảng (bucket).

• Bucket / Slot: Các vị trí hoặc ngăn chứa dữ liệu trong mảng nội bộ của hash table. Đây là nơi các cặp key-value được lưu trữ.

• O(1): Ký hiệu độ phức tạp thời gian (Time Complexity) trong khoa học máy tính. O(1) (Order of 1) biểu thị thời gian thực hiện một thuật toán hoặc thao tác là hằng số, không phụ thuộc vào kích thước của dữ liệu đầu vào. Đây là hiệu suất lý tưởng trong nhiều trường hợp.

• Dictionary / Map: Tên gọi các cấu trúc dữ liệu key-value trong các ngôn ngữ lập trình khác nhau (ví dụ: Dictionary trong Python, Map trong Java/C++). Chúng thường được triển khai dựa trên hash table để đạt hiệu suất cao.

Hash table hoạt động như thế nào?

Nguyên lý hoạt động cốt lõi của hash table dựa trên sự kết hợp giữa mảng (array) và hàm băm (hash function). Khi bạn muốn thêm, tìm kiếm hoặc xóa một cặp khóa-giá trị, hash table sẽ thực hiện các bước sau:

1. Tính toán chỉ số (Indexing): Khóa (key) của cặp dữ liệu sẽ được đưa vào hàm băm (hash function). Hàm này sẽ xử lý khóa và trả về một số nguyên, chính là chỉ số của bucket tương ứng trong mảng nền tảng nơi dữ liệu được lưu trữ hoặc tìm kiếm.

2. Thao tác trên Bucket: Dựa vào chỉ số nhận được từ hàm băm, hash table sẽ truy cập trực tiếp đến bucket tương ứng trong mảng. Tại bucket này, thao tác thêm, tìm kiếm hoặc xóa giá trị (value) liên kết với khóa (key) sẽ được thực hiện.

Quy trình này diễn ra cực kỳ nhanh chóng. Thay vì phải duyệt qua toàn bộ danh sách dữ liệu để tìm kiếm (như trong mảng hoặc danh sách liên kết thông thường, mất O(n)), hash table chỉ cần tính toán một lần bằng hàm băm và truy cập trực tiếp đến vị trí cần thiết.

Hàm băm (Hash Function) là gì?

Hàm băm (hash function) là trái tim của hash table. Nó là một thuật toán nhận đầu vào là một khóa (key) thuộc bất kỳ loại dữ liệu nào (số, chuỗi, đối tượng...) và trả về một giá trị nguyên không âm có kích thước cố định.

Ví dụ đơn giản, với một khóa là chuỗi "apple", hàm băm có thể tính toán ra chỉ số 5. Với chuỗi "banana", nó có thể ra chỉ số 12. Quan trọng là, cùng một khóa đầu vào luôn phải tạo ra cùng một chỉ số đầu ra. Tính chất này gọi là tính xác định (deterministic).

Một hàm băm tốt có khả năng phân tán các khóa khác nhau vào các chỉ số (bucket) khác nhau một cách đều đặn nhất có thể trong phạm vi mảng nền tảng. Việc phân tán đều giúp giảm thiểu tình trạng va chạm (collision), yếu tố có thể làm giảm hiệu suất của hash table.

Ví dụ về hàm băm đơn giản: Với khóa là số nguyên k và kích thước mảng m, hàm băm có thể là h(k) = k mod m. Ví dụ, nếu m=10 và k=34, h(34) = 34 mod 10 = 4. Khóa 34 sẽ được ánh xạ đến bucket có chỉ số 4.

Đối với chuỗi, hàm băm phức tạp hơn, thường dựa trên giá trị ASCII của các ký tự kết hợp với phép nhân và modulo để tạo ra chỉ số cuối cùng. Mục tiêu vẫn là phân phối khóa đều khắp mảng.

Vấn đề Va chạm (Collision) và các phương pháp xử lý

Va chạm (collision) xảy ra khi hàm băm tính toán ra cùng một chỉ số (index) cho hai hoặc nhiều khóa (key) khác nhau. Đây là điều không thể tránh khỏi hoàn toàn trong thực tế, đặc biệt khi số lượng khóa lớn hơn kích thước của mảng nền tảng.

Ví dụ: Với hàm băm h(k) = k mod 10, khóa 34 và khóa 44 đều cho cùng chỉ số 4. Nếu cả hai khóa này đều cần được lưu trữ, chúng sẽ "va chạm" tại bucket số 4.

Nếu không có cách xử lý va chạm, dữ liệu mới sẽ ghi đè lên dữ liệu cũ hoặc không thể được lưu trữ đúng cách. Do đó, các hash table cần có cơ chế hiệu quả để quản lý tình huống này.

Có hai phương pháp xử lý va chạm phổ biến:

1. Xử lý va chạm bằng Xâu chuỗi (Separate Chaining): Phương pháp này giải quyết va chạm bằng cách biến mỗi bucket trong mảng nền tảng thành một con trỏ (pointer) tới một danh sách liên kết (linked list) hoặc một cấu trúc dữ liệu khác (như cây nhị phân tìm kiếm cân bằng).
   Khi va chạm xảy ra, cặp key-value mới sẽ được thêm vào danh sách liên kết tại bucket tương ứng. Khi tìm kiếm, sau khi tính toán chỉ số bucket, hash table sẽ duyệt qua danh sách liên kết tại bucket đó để tìm đúng khóa cần thiết.
   Ví dụ minh họa: Bucket số 4 có thể chứa danh sách liên kết (34, value34) -> (44, value44).

2. Xử lý va chạm bằng Địa chỉ mở (Open Addressing / Probing): Thay vì sử dụng cấu trúc dữ liệu phụ tại mỗi bucket, Open Addressing tìm kiếm một bucket trống khác trong chính mảng nền tảng để lưu trữ dữ liệu bị va chạm.
   Khi va chạm xảy ra tại bucket i, hash table sẽ sử dụng một quy tắc "thăm dò" (probing) để tìm bucket trống tiếp theo. Các quy tắc thăm dò phổ biến bao gồm:

   • Linear Probing: Kiểm tra các bucket kế tiếp i+1, i+2, i+3,... (với phép toán modulo để quay vòng nếu vượt quá kích thước mảng).

   • Quadratic Probing: Kiểm tra các bucket theo một hàm bậc hai i+1^2, i+2^2, i+3^2,....

   • Double Hashing: Sử dụng một hàm băm thứ hai để xác định khoảng cách bước nhảy khi thăm dò.

3. Khi tìm kiếm, nếu bucket đầu tiên được tính toán bị va chạm, hash table cũng sẽ sử dụng quy tắc thăm dò tương ứng để tìm kiếm bucket chứa khóa mong muốn.

Việc lựa chọn phương pháp xử lý va chạm và chất lượng của hàm băm có ảnh hưởng lớn đến hiệu suất thực tế của hash table, đặc biệt trong trường hợp xấu nhất.

Ưu điểm và Nhược điểm của Hash table

Hash table mang lại nhiều lợi ích đáng kể nhưng cũng có những hạn chế cần cân nhắc khi sử dụng.

Ưu điểm nổi bật

Ưu điểm lớn nhất và quan trọng nhất của hash table chính là tốc độ truy xuất dữ liệu cực kỳ nhanh chóng.

• Thời gian truy cập O(1) trung bình: Hash table có khả năng thêm mới, tìm kiếm và xóa một cặp khóa-giá trị với độ phức tạp thời gian trung bình là O(1). Điều này là lý tưởng trong lập trình. Giả sử bạn có hàng triệu mục dữ liệu, việc tìm một mục cụ thể trong hash table trung bình chỉ mất... một bước (tính hàm băm và truy cập bucket), không phụ thuộc vào số triệu mục đó. So với việc duyệt tuyến tính qua mảng hoặc danh sách liên kết (O(n)), hash table nhanh hơn rất nhiều. So với cây tìm kiếm nhị phân cân bằng (O(log n)), hash table trung bình vẫn nhanh hơn.

• Hiệu quả trong việc lưu trữ và truy xuất dữ liệu theo khóa: Khi bài toán của bạn liên quan đến việc ánh xạ các khóa đến các giá trị và cần truy xuất nhanh dựa trên khóa (ví dụ: tìm kiếm thông tin của sinh viên dựa trên mã số sinh viên), hash table là lựa chọn hàng đầu.

Nhược điểm cần lưu ý

Bên cạnh ưu điểm, hash table cũng có những nhược điểm cần được quản lý cẩn thận:

• Hiệu suất có thể suy giảm trong trường hợp xấu nhất (O(n)): Nếu hàm băm kém chất lượng hoặc dữ liệu đầu vào được phân phối không đều, dẫn đến nhiều va chạm tại cùng một hoặc một vài bucket, hiệu suất của hash table có thể giảm đáng kể. Trong trường hợp xấu nhất (ví dụ: tất cả khóa đều va chạm và được lưu trong một danh sách liên kết dài tại một bucket duy nhất), việc tìm kiếm có thể phải duyệt toàn bộ danh sách đó, khiến độ phức tạp trở thành O(n).

• Không duy trì thứ tự dữ liệu: Các cặp khóa-giá trị trong hash table không được lưu trữ theo bất kỳ thứ tự cụ thể nào (ví dụ: theo thứ tự thêm vào hay theo thứ tự của khóa). Nếu bạn cần duyệt dữ liệu theo một thứ tự nhất định, hash table không phải là cấu trúc phù hợp.

• Yêu cầu khóa có thể băm được (Hashable): Khóa được sử dụng trong hash table phải là kiểu dữ liệu có thể băm được (immutable trong nhiều ngôn ngữ như chuỗi, số). Các đối tượng có thể thay đổi (mutable) thường không thể dùng làm khóa vì giá trị băm của chúng có thể thay đổi sau khi thêm vào bảng, dẫn đến việc không thể tìm lại được.

• Cần ước lượng kích thước hoặc tốn chi phí mở rộng (Resizing/Rehashing): Để đạt hiệu suất tốt, hash table thường cần được khởi tạo với kích thước mảng nền tảng phù hợp. Nếu số lượng dữ liệu vượt quá sức chứa hoặc tỷ lệ lấp đầy quá cao, hash table cần phải thực hiện quá trình mở rộng (resizing) và băm lại (rehashing) toàn bộ dữ liệu vào mảng mới lớn hơn. Quá trình này tốn kém về mặt thời gian.

Ứng dụng thực tế của Hash table trong lập trình

Hash table là một trong những cấu trúc dữ liệu được ứng dụng rộng rãi nhất trong thế giới lập trình hiện đại nhờ vào tốc độ truy xuất vượt trội của nó.

Sử dụng làm nền tảng cho Dictionary/Map

Đây là ứng dụng phổ biến nhất. Hầu hết các ngôn ngữ lập trình đều cung cấp một cấu trúc dữ liệu dạng key-value được xây dựng dựa trên hash table.

• Python: Kiểu dữ liệu dict (dictionary) của Python được triển khai bằng hash table. Bạn dùng nó để lưu trữ các cặp khóa-giá trị và truy cập nhanh chóng: my_dict = {'apple': 1, 'banana': 2}, print(my_dict['apple']).

• Java: HashMap và Hashtable trong Java sử dụng nguyên lý hash table. Chúng cung cấp giao diện Map để làm việc với các cặp key-value.

• C++: std::unordered_map trong C++ Standard Library là một implementation của hash table.

• C#: Dictionary<TKey, TValue> trong C# cũng dựa trên hash table.

Các cấu trúc dữ liệu này cực kỳ hữu ích khi bạn cần lưu trữ dữ liệu mà mối quan tâm chính là truy xuất nhanh một giá trị dựa trên khóa duy nhất của nó.

Xây dựng hệ thống Cache

Cache là một bộ nhớ đệm dùng để lưu trữ tạm thời các dữ liệu thường xuyên được truy cập để tăng tốc độ. Hash table là cấu trúc lý tưởng để xây dựng cache.

Khi một yêu cầu đến, hệ thống cache dùng hash table để kiểm tra xem dữ liệu đã có trong cache chưa (kiểm tra nhanh dựa trên khóa là ID hoặc URL của dữ liệu). Nếu có, dữ liệu được trả về ngay lập tức (O(1) trung bình). Nếu không, hệ thống mới truy xuất từ nguồn chậm hơn (ví dụ: database), sau đó lưu vào cache bằng hash table để phục vụ lần sau nhanh hơn.

Ví dụ: Bộ nhớ cache của trình duyệt web sử dụng hash table để lưu trữ các trang web hoặc hình ảnh đã truy cập gần đây. Khi bạn truy cập lại, trình duyệt kiểm tra cache trước.

Tối ưu tìm kiếm (Indexing) trong cơ sở dữ liệu

Trong các hệ quản trị cơ sở dữ liệu (Database Management Systems - DBMS), hashing thường được sử dụng để xây dựng các chỉ mục (index) nhằm tăng tốc độ truy vấn dữ liệu.

Thay vì phải quét toàn bộ bảng dữ liệu để tìm kiếm một bản ghi dựa trên một cột (ví dụ: tìm thông tin khách hàng dựa trên số điện thoại), cơ sở dữ liệu có thể tạo một hash index trên cột đó. Hash index về cơ bản là một hash table lưu trữ ánh xạ từ giá trị của cột (khóa) đến vị trí vật lý của bản ghi trong bộ nhớ hoặc trên đĩa.

Khi bạn thực hiện truy vấn tìm kiếm theo cột đã được đánh hash index, hệ thống sẽ dùng hàm băm để tìm ngay đến vị trí của bản ghi, giúp truy vấn nhanh hơn đáng kể so với không dùng index hoặc dùng các loại index khác trong một số trường hợp.

Triển khai tập hợp (Set)

Một tập hợp (Set) là một cấu trúc dữ liệu chỉ lưu trữ các phần tử duy nhất và không quan tâm đến thứ tự. Hash table là một cách hiệu quả để triển khai Set.

Để thêm một phần tử vào Set, hash table dùng hàm băm của phần tử đó để kiểm tra xem nó đã tồn tại trong bảng chưa (kiểm tra sự duy nhất). Nếu chưa có, nó mới thêm phần tử đó vào. Thao tác kiểm tra sự tồn tại (membership testing, ví dụ: element in my_set) cũng rất nhanh nhờ hash table.

Ví dụ: Kiểu dữ liệu set trong Python cũng được triển khai dựa trên hash table.

So sánh Hash table với các cấu trúc dữ liệu khác

Để thấy rõ hơn ưu điểm của hash table, chúng ta cùng so sánh nó với hai cấu trúc dữ liệu cơ bản khác là Mảng (Array) và Danh sách liên kết (Linked List) dựa trên các thao tác phổ biến.

Hash table vs. Array (Mảng)

Mảng là một tập hợp các phần tử được lưu trữ liên tiếp trong bộ nhớ, có thể truy cập trực tiếp bằng chỉ số (index).

• Truy cập theo chỉ số: Mảng truy cập theo chỉ số cực nhanh, O(1). Hash table không truy cập trực tiếp bằng chỉ số người dùng cung cấp, mà phải thông qua hàm băm để tính ra chỉ số nội bộ, nên không thể so sánh trực tiếp về mặt này.

• Tìm kiếm theo giá trị: Để tìm một giá trị cụ thể trong mảng chưa sắp xếp, bạn phải duyệt qua từng phần tử (Linear Search), tốn thời gian O(n). Hash table, ngược lại, tìm kiếm theo khóa (không phải giá trị) với hiệu suất O(1) trung bình, nhanh hơn rất nhiều. Nếu mảng đã sắp xếp, tìm kiếm nhị phân là O(log n), vẫn chậm hơn O(1) trung bình của hash table.

• Thêm/Xóa: Thêm hoặc xóa phần tử ở giữa mảng liên tiếp đòi hỏi dịch chuyển các phần tử khác, tốn O(n). Trong hash table, thêm/xóa theo khóa trung bình là O(1) tại bucket tương ứng.

Hash table vượt trội hơn mảng khi cần tìm kiếm, thêm, xóa dữ liệu dựa trên giá trị (khóa) thay vì chỉ số.

Hash table vs. Linked List (Danh sách liên kết)

Danh sách liên kết là tập hợp các nút (node), mỗi nút chứa dữ liệu và con trỏ đến nút kế tiếp.

• Tìm kiếm theo giá trị: Để tìm một giá trị trong danh sách liên kết, bạn phải duyệt từ đầu danh sách đến khi tìm thấy, tốn O(n). Hash table tìm kiếm theo khóa là O(1) trung bình.

• Thêm/Xóa: Thêm hoặc xóa một nút trong danh sách liên kết là O(1) nếu bạn đã có con trỏ đến vị trí đó. Tuy nhiên, nếu cần tìm kiếm vị trí đó trước khi thêm/xóa, chi phí sẽ là O(n) cho bước tìm kiếm. Hash table thêm/xóa theo khóa là O(1) trung bình.

Hash table nhanh hơn danh sách liên kết rất nhiều trong các thao tác tìm kiếm, thêm, xóa khi bạn chỉ có khóa mà không có con trỏ trực tiếp đến vị trí dữ liệu.

Thao tác

Array (chưa sắp xếp)

Linked List

Hash Table (Trung bình)

Truy cập theo chỉ số

O(1)

O(n)

N/A (truy cập theo khóa)

Tìm kiếm theo giá trị

O(n)

O(n)

O(1)

Thêm/Xóa

O(n)

O(1) (nếu có pointer), O(n) (nếu tìm kiếm)

O(1)

Bảng trên cho thấy rõ ràng lợi thế về tốc độ của hash table (trung bình O(1)) trong các thao tác cốt lõi so với mảng và danh sách liên kết khi làm việc với dữ liệu truy xuất theo khóa.

Nguồn tham khảo: InterData (2025). Hash Table (Bảng Băm) là gì? Toàn tập về cấu trúc & hoạt động