Trong thế giới lập trình, việc quản lý và truy cập dữ liệu hiệu quả là vô cùng quan trọng. Một trong những công cụ mạnh mẽ nhất giúp làm điều này chính là Hash Table (Bảng băm) – một cấu trúc dữ liệu cho phép tra cứu cực nhanh. Bài viết này sẽ cùng bạn khám phá chi tiết Hash Table từ định nghĩa đến nguyên lý hoạt động, các vấn đề thường gặp và ứng dụng thực tế.
VPS GIÁ RẺ - UY TÍN - CHẤT LƯỢNG CAO
Xây dựng các ứng dụng hiệu quả và tốc độ cao, tận dụng cấu trúc dữ liệu mạnh mẽ như Hash Table, đòi hỏi một nền tảng hạ tầng tương xứng để vận hành mượt mà. Để triển khai code của bạn trong môi trường ổn định với cấu hình mạnh mẽ, thuê VPS giá rẻ tại InterData là lựa chọn chất lượng, uy tín. Dịch vụ cung cấp phần cứng chuyên dụng thế hệ mới (bộ xử lý AMD EPYC Gen 3th, SSD NVMe U.2), băng thông cao, dung lượng được tối ưu cùng công nghệ ảo hóa tiên tiến, mang đến tốc độ cao và sự ổn định bạn cần, với giá chỉ từ 3K/Ngày.
Hash table là gì?
Hash table, hay còn gọi là bảng băm, là một cấu trúc dữ liệu được thiết kế để lưu trữ và truy xuất dữ liệu dưới dạng các cặp khóa-giá trị (key-value pairs). Nó hoạt động giống như một cuốn từ điển kỹ thuật số, nơi mỗi “từ” (khóa) liên kết trực tiếp đến “nghĩa” của nó (giá trị).
Mục tiêu chính của hash table là cung cấp khả năng truy cập dữ liệu nhanh chóng và hiệu quả. Với hash table, việc tìm kiếm, thêm mới hoặc xóa bỏ một phần tử chỉ mất một khoảng thời gian gần như không đổi, bất kể số lượng dữ liệu lớn đến đâu.
Điều này tạo nên sự khác biệt lớn so với các cấu trúc dữ liệu tuyến tính như mảng (array) hoặc danh sách liên kết (linked list). Trong các cấu trúc đó, việc tìm kiếm một phần tử thường yêu cầu duyệt qua nhiều hoặc thậm chí toàn bộ danh sách, dẫn đến hiệu suất giảm khi dữ liệu tăng lên.
Bí mật đằng sau tốc độ “tra cứu tức thời” của hash table nằm ở kỹ thuật gọi là băm (hashing). Kỹ thuật này sử dụng một hàm đặc biệt để biến khóa của dữ liệu thành một chỉ mục, giúp xác định vị trí lưu trữ dữ liệu đó.
Cụ thể, khi bạn muốn thêm một cặp khóa-giá trị vào hash table, nó sẽ sử dụng một hàm băm (hash function) để tính toán chỉ mục (index) từ khóa đó. Cặp dữ liệu sau đó được lưu trữ tại vị trí chỉ mục này trong mảng nội bộ của hash table.
Tương tự, khi muốn truy xuất giá trị từ một khóa, hash table lại chạy hàm băm với khóa đó để có được cùng chỉ mục. Nhờ chỉ mục này, nó có thể truy cập trực tiếp vào vị trí tương ứng trong mảng và lấy giá trị liên kết.
Tại sao cần sử dụng Hash Table?
Hash table là cần thiết vì nó cung cấp hiệu suất vượt trội trong việc thực hiện các thao tác cơ bản như thêm, xóa và đặc biệt là tìm kiếm dữ liệu dựa trên một khóa duy nhất. Tốc độ này cực kỳ quan trọng trong nhiều ứng dụng thực tế đòi hỏi phản hồi nhanh.
Hãy tưởng tượng bạn có một danh sách hàng triệu bản ghi và cần tìm một bản ghi cụ thể dựa trên ID duy nhất (khóa). Nếu dùng mảng hay danh sách liên kết thông thường, bạn có thể phải kiểm tra từng bản ghi một cho đến khi tìm thấy, rất tốn thời gian và tài nguyên, đặc biệt khi dữ liệu ngày càng nhiều.
Hash table giải quyết vấn đề này bằng cách biến khóa thành chỉ mục thông qua hàm băm. Thay vì duyệt tuần tự, nó tính toán vị trí trực tiếp và truy cập dữ liệu chỉ trong một “bước nhảy” (hoặc rất ít bước trung bình), giúp bỏ qua phần lớn dữ liệu không liên quan, tiết kiệm đáng kể thời gian xử lý.
Tốc độ “tra cứu tức thời” này là yếu tố then chốt trong các hệ thống cần hiệu suất cao như cơ sở dữ liệu, bộ nhớ đệm (cache), hoặc các thuật toán yêu cầu kiểm tra sự tồn tại của phần tử một cách liên tục và hiệu quả.
Nguyên lý hoạt động của Hash Table
Nguyên lý hoạt động của hash table xoay quanh ba thành phần chính: cặp khóa-giá trị cần lưu trữ, một hàm băm để xử lý khóa, và một mảng (thường gọi là các bucket hoặc slot) nơi dữ liệu thực sự được lưu trữ vật lý.
Khi một cặp khóa-giá trị mới được đưa vào hash table (thao tác chèn), hash table sẽ lấy phần khóa (ví dụ: tên người, số ID sản phẩm, địa chỉ email) và truyền nó vào hàm băm đã được định nghĩa trước.
Hàm băm này sẽ thực hiện các phép tính toán phức tạp và trả về một giá trị số nguyên. Giá trị số nguyên này chính là mã băm (hash code) của khóa đầu vào. Mã băm này là duy nhất cho cùng một khóa với cùng một hàm băm.
Mã băm (hash code) có thể là một số nguyên rất lớn. Để ánh xạ nó vào các vị trí hợp lệ trong mảng nội bộ của hash table, hash table thường sử dụng phép toán modulo (%) với kích thước hiện tại của mảng. Công thức đơn giản là index = hash_code % array_size.
Chỉ mục (index) cuối cùng thu được sau phép toán modulo cho biết “bucket” hoặc vị trí nào trong mảng sẽ là nơi cặp khóa-giá trị đó được lưu trữ. Dữ liệu (bao gồm cả khóa và giá trị) sau đó được đặt vào vị trí đã tính toán này.
Quá trình tìm kiếm dữ liệu cũng diễn ra tương tự. Khi bạn cung cấp một khóa để tìm kiếm, hash table sẽ sử dụng cùng hàm băm đó để tính toán mã băm từ khóa, sau đó áp dụng phép toán modulo để có được chỉ mục dự kiến.
Sau khi có chỉ mục, hash table truy cập trực tiếp đến vị trí đó trong mảng. Tại đây, nó sẽ kiểm tra xem có phần tử nào có khóa trùng khớp với khóa đang tìm kiếm hay không và trả về giá trị tương ứng nếu tìm thấy.
Hàm băm (Hash Function) là gì và vai trò của nó
Hàm băm (hash function) là một thuật toán nhận đầu vào là dữ liệu có kích thước tùy ý (chính là khóa) và tạo ra đầu ra là một chuỗi bit hoặc một số nguyên có kích thước cố định, gọi là mã băm (hash code).
Vai trò cốt lõi của hàm băm trong hash table là tạo ra một “đại diện” số cho mỗi khóa. Đại diện số này sau đó được sử dụng để tính toán vị trí lưu trữ dữ liệu trong mảng nội bộ, giúp truy cập dữ liệu nhanh chóng.
Một hàm băm tốt cần có vài đặc tính quan trọng để đảm bảo hash table hoạt động hiệu quả. Đầu tiên, nó phải có tính xác định (deterministic): cùng một khóa luôn luôn phải tạo ra cùng một mã băm mỗi lần gọi hàm.
Thứ hai, hàm băm nên có khả năng phân tán các khóa khác nhau thành các mã băm khác nhau một cách đồng đều nhất có thể trên toàn bộ phạm vi giá trị đầu ra. Tính phân tán đồng đều (uniform distribution) rất quan trọng.
Việc phân tán mã băm đồng đều giúp giảm thiểu khả năng xảy ra đụng độ (collision) – tình huống hai khóa khác nhau lại tạo ra cùng mã băm. Ít đụng độ hơn thường dẫn đến hiệu suất truy xuất nhanh hơn và ổn định hơn trong hash table.
Ví dụ, một hàm băm đơn giản cho chuỗi ký tự có thể là tính tổng giá trị ASCII của các ký tự. Tuy nhiên, hàm này dễ gây đụng độ (ví dụ “ab” và “ba”). Các hàm băm phức tạp hơn như SHA-256 hoặc MD5 (trong mã hóa) hoặc các hàm được thiết kế chuyên biệt cho cấu trúc dữ liệu được sử dụng trong thực tế.
Hàm băm lý tưởng là hàm băm hoàn hảo (perfect hash function) không gây ra bất kỳ đụng độ nào cho tập hợp khóa đã biết, nhưng điều này chỉ khả thi với các tập khóa cố định và nhỏ.
Đụng độ (Collision) trong Hash Table là gì?
Đụng độ (collision) là tình huống không mong muốn xảy ra trong hash table khi hai hoặc nhiều khóa khác nhau được hàm băm xử lý và cho ra cùng một mã băm (hash code), dẫn đến việc chúng cùng muốn lưu trữ hoặc truy xuất tại cùng một chỉ mục trong mảng nội bộ.
Vấn đề đụng độ này gần như không thể tránh khỏi hoàn toàn trong các hash table thực tế, đặc biệt là khi số lượng dữ liệu (khóa) lớn hơn nhiều so với số lượng vị trí (bucket) trong mảng. Điều này là do nguyên lý Chuồng Bồ Câu (Pigeonhole Principle) – khi có nhiều “chim bồ câu” (khóa) hơn “chuồng” (bucket), ít nhất một chuồng phải chứa nhiều hơn một chim.
Nếu không được xử lý đúng cách, đụng độ có thể dẫn đến việc dữ liệu bị ghi đè (nếu mỗi bucket chỉ chứa được một phần tử) hoặc không thể tìm thấy dữ liệu mong muốn khi truy xuất. Điều này làm mất đi tính chính xác và độ tin cậy của hash table.
Ngoài ra, việc có quá nhiều đụng độ tập trung tại một hoặc một vài chỉ mục cụ thể (gọi là clustering) có thể làm suy giảm đáng kể hiệu suất của hash table. Thay vì truy xuất O(1), việc xử lý đụng độ có thể buộc hash table phải thực hiện các thao tác phức tạp hơn, đưa hiệu suất về gần O(n) trong trường hợp xấu nhất.
Mục tiêu của việc xử lý đụng độ là để mỗi phần tử vẫn có thể được lưu trữ và truy xuất một cách chính xác và hiệu quả ngay cả khi nhiều khóa cùng băm về một vị trí ban đầu trong mảng.
Các phương pháp xử lý đụng độ phổ biến
Để duy trì hiệu suất cao và tính chính xác khi xảy ra đụng độ, hash table cần áp dụng các kỹ thuật xử lý đụng độ (collision resolution techniques). Việc lựa chọn phương pháp ảnh hưởng đến cấu trúc lưu trữ và quy trình tìm kiếm khi có đụng độ.
Có hai nhóm phương pháp chính được sử dụng rộng rãi để giải quyết đụng độ trong hash table: Separate Chaining (Kết nối riêng) và Open Addressing (Địa chỉ mở).
Separate Chaining
Separate Chaining (Kết nối riêng) là một phương pháp xử lý đụng độ tương đối đơn giản và phổ biến. Ý tưởng là thay vì mỗi vị trí (bucket) trong mảng chỉ lưu trữ một phần tử, nó sẽ lưu trữ một cấu trúc dữ liệu khác có khả năng chứa nhiều phần tử.
Thông thường, một danh sách liên kết (linked list) được sử dụng tại mỗi bucket. Khi có đụng độ xảy ra (hai khóa băm về cùng chỉ mục), cặp key-value mới sẽ chỉ đơn giản được thêm vào cuối danh sách liên kết tại bucket tương ứng đó.
Để tìm kiếm một phần tử trong hash table sử dụng Separate Chaining, trước tiên hash table tính toán chỉ mục từ khóa bằng hàm băm. Sau đó, nó truy cập vào bucket tại chỉ mục đó và duyệt qua danh sách liên kết tại bucket đó để tìm khóa cần thiết.
Ưu điểm chính của Separate Chaining là đơn giản để triển khai. Nó cũng quản lý việc xóa phần tử dễ dàng hơn so với Open Addressing. Kích thước của hash table không cần phải quá lớn so với số lượng phần tử, và hệ số tải (load factor) có thể vượt quá 1.
Nhược điểm là tốn thêm không gian bộ nhớ cho các con trỏ của danh sách liên kết. Hiệu suất có thể suy giảm nếu các danh sách liên kết tại các bucket trở nên quá dài (do hàm băm kém hoặc dữ liệu bị phân tán không đồng đều).
Open Addressing
Open Addressing (Địa chỉ mở), còn gọi là Closed Hashing, là phương pháp xử lý đụng độ bằng cách tìm một vị trí trống khác ngay trong chính mảng nội bộ của hash table khi vị trí ban đầu bị chiếm.
Khi đụng độ xảy ra tại chỉ mục i được tính từ hàm băm ban đầu, thuật toán Open Addressing sẽ tính toán một chuỗi các chỉ mục thay thế (i', i'', i''', v.v.) và kiểm tra từng vị trí trong chuỗi này cho đến khi tìm thấy một ô trống để chèn phần tử mới, hoặc tìm thấy phần tử cần tìm khi thực hiện thao tác truy xuất.
Chuỗi các chỉ mục thay thế này gọi là chuỗi thăm dò (probing sequence). Việc tính toán chuỗi thăm dò là điểm khác biệt chính giữa các biến thể của Open Addressing. Ba kỹ thuật phổ biến nhất là Linear Probing, Quadratic Probing và Double Hashing.
Linear Probing (Thăm dò tuyến tính): Nếu chỉ mục i bị đụng độ, nó sẽ kiểm tra các chỉ mục i+1, i+2, i+3,… (theo modulo kích thước mảng) cho đến khi tìm thấy ô trống. Đơn giản nhưng dễ gây Primary Clustering (các phần tử đụng độ liên tiếp tạo thành cụm lớn).
Quadratic Probing (Thăm dò bậc hai): Sử dụng một hàm bậc hai để tính bước nhảy: i + 1^2, i + 2^2, i + 3^2,… (theo modulo). Giảm bớt Primary Clustering nhưng có thể gây Secondary Clustering (các khóa có cùng mã băm ban đầu đi theo cùng một chuỗi thăm dò).
Double Hashing (Băm kép): Sử dụng hàm băm thứ hai để tính toán bước nhảy trong chuỗi thăm dò. i + hash2(key), i + 2*hash2(key), i + 3*hash2(key),… Đây là phương pháp phức tạp nhất nhưng thường cho phân tán tốt nhất và giảm thiểu clustering hiệu quả hơn.
Ưu điểm của Open Addressing là không cần không gian bộ nhớ bổ sung cho con trỏ hay các cấu trúc dữ liệu phụ (như danh sách liên kết). Nhược điểm là việc xóa phần tử phức tạp hơn (thường phải đánh dấu vị trí là “đã xóa” chứ không xóa hẳn để không làm gián đoạn chuỗi thăm dò khi tìm kiếm) và dễ bị ảnh hưởng bởi hiện tượng clustering nếu hàm băm hoặc phương pháp thăm dò không tốt.
Độ phức tạp thời gian của Hash Table (O(1))
Điểm mạnh nổi bật và lý do chính khiến hash table được ưa chuộng là hiệu suất hoạt động. Các thao tác cơ bản nhất như thêm (insertion), xóa (deletion) và tìm kiếm (lookup) dữ liệu trong hash table có độ phức tạp thời gian trung bình (average time complexity) là O(1).
Độ phức tạp O(1) có ý nghĩa cực kỳ quan trọng. Nó có nghĩa là thời gian để thực hiện các thao tác này gần như không đổi, không phụ thuộc vào số lượng phần tử n hiện có trong hash table. Cho dù hash table của bạn chứa 100 phần tử hay 1 tỷ phần tử, việc tìm kiếm một phần tử cụ thể vẫn chỉ mất một khoảng thời gian tương tự nhau (trung bình).
Hiệu suất O(1) trung bình này đạt được là nhờ vào nguyên lý băm. Khi không có đụng độ hoặc đụng độ được xử lý hiệu quả, việc truy xuất dữ liệu chỉ đơn giản là tính toán chỉ mục từ khóa (thời gian cố định) và truy cập trực tiếp vào vị trí đó trong mảng (thời gian cố định), tổng cộng là thời gian không đổi.
Tuy nhiên, cần lưu ý rằng O(1) là độ phức tạp trung bình (average case). Trong trường hợp xấu nhất (worst case), khi tất cả các khóa cùng băm về một chỉ mục duy nhất (hoặc tạo ra một chuỗi đụng độ cực kỳ dài), hash table có thể phải duyệt qua tất cả hoặc gần hết các phần tử.
Trong tình huống xấu nhất này, độ phức tạp thời gian có thể suy giảm xuống O(n), tương tự như việc tìm kiếm trên một danh sách liên kết hoặc mảng không được sắp xếp. Trường hợp xấu nhất thường xảy ra do hàm băm kém chất lượng hoặc do tập dữ liệu đầu vào có tính chất đặc biệt làm tăng đột biến số lượng đụng độ.
Hiệu suất thực tế của hash table phụ thuộc nhiều vào hai yếu tố chính: chất lượng của hàm băm (khả năng phân tán khóa đồng đều) và hệ số tải (load factor) – tỷ lệ giữa số lượng phần tử hiện có và tổng số bucket (kích thước mảng). Hệ số tải quá cao (quá nhiều phần tử trong khi ít bucket) chắc chắn sẽ làm tăng khả năng đụng độ và giảm hiệu suất.
Hash Table trong các ngôn ngữ lập trình phổ biến
Khái niệm và nguyên lý hoạt động của hash table là nền tảng cho nhiều cấu trúc dữ liệu “có sẵn” và được sử dụng rộng rãi trong các ngôn ngữ lập trình hiện đại. Dưới đây là cách hash table được triển khai và sử dụng trong một số ngôn ngữ phổ biến nhất:
Python Dictionary
Trong Python, kiểu dữ liệu tích hợp Dictionary (dict) chính là một cài đặt điển hình của hash table. Dictionary trong Python lưu trữ dữ liệu dưới dạng các cặp khóa-giá trị và được tối ưu hóa để cung cấp khả năng truy cập các giá trị bằng khóa một cách cực nhanh, với độ phức tạp thời gian trung bình là O(1).
Khóa trong Python dictionary phải là các đối tượng “hashable” (có thể băm được), nghĩa là chúng có mã băm không đổi trong suốt vòng đời và có thể so sánh bằng. Các kiểu dữ liệu bất biến (immutable) như chuỗi (string), số nguyên (integer), tuple thường là hashable và có thể dùng làm khóa.
Python
# Khởi tạo một dictionary (hash table) rỗng
sinh_vien = {}
# Thêm các cặp key-value vào dictionary
sinh_vien["ma_sv_101"] = "Nguyễn Văn A" # Khóa là "ma_sv_101", Giá trị là "Nguyễn Văn A"
sinh_vien["ma_sv_102"] = "Trần Thị B"
sinh_vien["ma_sv_103"] = "Lê Văn C"
# In ra dictionary
print(sinh_vien)
# Output có thể giống như: {'ma_sv_101': 'Nguyễn Văn A', 'ma_sv_102': 'Trần Thị B', 'ma_sv_103': 'Lê Văn C'}
Python
# Truy xuất giá trị bằng khóa
ten_sv_101 = sinh_vien["ma_sv_101"]
print(f"Tên sinh viên 101: {ten_sv_101}") # Output: Tên sinh viên 101: Nguyễn Văn A
# Cập nhật giá trị cho một khóa đã tồn tại
sinh_vien["ma_sv_102"] = "Trần Thị B (Đã cập nhật thông tin)"
print(sinh_vien["ma_sv_102"]) # Output: Trần Thị B (Đã cập nhật thông tin)
# Xóa một cặp key-value bằng khóa
del sinh_vien["ma_sv_103"]
# In ra dictionary sau khi xóa
print(sinh_vien)
# Output có thể giống như: {'ma_sv_101': 'Nguyễn Văn A', 'ma_sv_102': 'Trần Thị B (Đã cập nhật thông tin)'}
Các thao tác thêm, truy xuất, cập nhật và xóa phần tử trong Python dictionary bằng cách sử dụng khóa đều tận dụng nguyên lý băm nội bộ, mang lại hiệu suất O(1) trung bình, làm cho dictionary trở thành một trong những kiểu dữ liệu linh hoạt và được sử dụng nhiều nhất trong Python.
Java HashMap
Trong Java, lớp **HashMap** thuộc package java.util là một cài đặt phổ biến của hash table. HashMap triển khai interface Map, cho phép lưu trữ dữ liệu dưới dạng cặp khóa-giá trị và nổi bật với hiệu suất O(1) trung bình cho các thao tác cơ bản.
Khóa và giá trị trong HashMap của Java đều là các đối tượng. Khóa được sử dụng phải override chính xác hai phương thức hashCode() và equals() để đảm bảo hàm băm hoạt động đúng và có thể so sánh các khóa một cách chính xác khi xử lý đụng độ hoặc tìm kiếm.
Java
import java.util.HashMap;
import java.util.Map;
public class HashMapExample {
public static void main(String[] args) {
// Khởi tạo một HashMap. Khóa là String, Giá trị là String.
Map<String, String> sinhVien = new HashMap<>();
// Thêm các cặp key-value
sinhVien.put("ma_sv_101", "Nguyen Van A"); // Khóa là "ma_sv_101", Giá trị là "Nguyen Van A"
sinhVien.put("ma_sv_102", "Tran Thi B");
sinhVien.put("ma_sv_103", "Le Van C");
// In ra HashMap
System.out.println(sinhVien);
// Output có thể giống như: {ma_sv_101=Nguyen Van A, ma_sv_102=Tran Thi B, ma_sv_103=Le Van C}
// (Lưu ý: Thứ tự in ra có thể không giống thứ tự thêm vào vì HashMap không duy trì thứ tự)
}
}
Java
import java.util.HashMap;
import java.util.Map;
public class HashMapAccessExample {
public static void main(String[] args) {
Map<String, String> sinhVien = new HashMap<>();
sinhVien.put("ma_sv_101", "Nguyen Van A");
sinhVien.put("ma_sv_102", "Tran Thi B");
sinhVien.put("ma_sv_103", "Le Van C");
// Truy xuất giá trị bằng khóa
String tenSv = sinhVien.get("ma_sv_101");
System.out.println("Ten sinh vien 101: " + tenSv); // Output: Ten sinh vien 101: Nguyen Van A
// Cập nhật giá trị cho một khóa đã tồn tại
sinhVien.put("ma_sv_102", "Tran Thi B (Da cap nhat)"); // put() sẽ ghi đè nếu khóa đã tồn tại
System.out.println(sinhVien.get("ma_sv_102")); // Output: Tran Thi B (Da cap nhat)
// Xóa một cặp key-value bằng khóa
sinhVien.remove("ma_sv_103");
// In ra HashMap sau khi xóa
System.out.println(sinhVien);
// Output có thể giống như: {ma_sv_101=Nguyen Van A, ma_sv_102=Tran Thi B (Da cap nhat)}
}
}
HashMap của Java sử dụng kỹ thuật Separate Chaining để xử lý đụng độ (mỗi bucket là một danh sách liên kết). Các phương thức put(), get(), remove() đều được tối ưu hóa để tận dụng nguyên lý băm và cấu trúc bucket, mang lại hiệu suất cao cho các ứng dụng cần tra cứu nhanh dữ liệu theo khóa.
C++ unordered_map
Trong C++, thư viện Standard Template Library (STL) cung cấp container **std::unordered_map**. Đây là một cài đặt của hash table, cho phép lưu trữ các cặp khóa-giá trị mà không duy trì thứ tự các phần tử, tập trung chủ yếu vào việc cung cấp hiệu suất truy cập nhanh dựa trên khóa.
unordered_map yêu cầu kiểu dữ liệu của khóa phải cung cấp hàm băm (hash function) và toán tử so sánh bằng (==). Đối với các kiểu dữ liệu cơ bản (như int, float, string), STL đã cung cấp sẵn các hàm băm mặc định. Với các kiểu dữ liệu tùy chỉnh (class, struct), bạn cần cung cấp hàm băm riêng.
C++
#include <iostream>
#include <string>
#include <unordered_map>
int main() {
// Khởi tạo một unordered_map. Khóa là std::string, Giá trị là std::string.
std::unordered_map<std::string, std::string> sinhVien;
// Thêm các cặp key-value
sinhVien["ma_sv_101"] = "Nguyen Van A"; // Khóa là "ma_sv_101", Giá trị là "Nguyen Van A"
sinhVien["ma_sv_102"] = "Tran Thi B";
sinhVien["ma_sv_103"] = "Le Van C";
// In ra unordered_map (thứ tự có thể không giống thứ tự thêm vào)
// Sử dụng iterator để duyệt
for (const auto& pair : sinhVien) {
std::cout << pair.first << ": " << pair.second << std::endl;
}
return 0;
}
C++
#include <iostream>
#include <string>
#include <unordered_map>
int main() {
std::unordered_map<std::string, std::string> sinhVien;
sinhVien["ma_sv_101"] = "Nguyen Van A";
sinhVien["ma_sv_102"] = "Tran Thi B";
sinhVien["ma_sv_103"] = "Le Van C";
// Truy xuất giá trị bằng khóa
// Sử dụng toán tử []
std::cout << "Ten sinh vien 101: " << sinhVien["ma_sv_101"] << std::endl; // Output: Ten sinh vien 101: Nguyen Van A
// Sử dụng phương thức at() (an toàn hơn vì ném ngoại lệ nếu khóa không tồn tại)
try {
std::cout << "Ten sinh vien 102: " << sinhVien.at("ma_sv_102") << std::endl; // Output: Ten sinh vien 102: Tran Thi B
} catch (const std::out_of_range& oor) {
std::cerr << "Khoa khong ton tai: " << oor.what() << std::endl;
}
// Cập nhật giá trị cho một khóa đã tồn tại
sinhVien["ma_sv_102"] = "Tran Thi B (Da cap nhat)"; // Sử dụng toán tử []
std::cout << "Ten sinh vien 102 sau cap nhat: " << sinhVien["ma_sv_102"] << std::endl; // Output: Ten sinh vien 102 sau cap nhat: Tran Thi B (Da cap nhat)
// Xóa một cặp key-value bằng khóa
sinhVien.erase("ma_sv_103");
// In ra sau khi xoa
std::cout << "\nHashMap sau khi xoa ma_sv_103:" << std::endl;
for (const auto& pair : sinhVien) {
std::cout << pair.first << ": " << pair.second << std::endl;
}
return 0;
}
unordered_map trong C++ thường sử dụng Separate Chaining để xử lý đụng độ. Việc sử dụng toán tử [] để truy cập hoặc các phương thức như insert(), erase(), find() đều tận dụng cấu trúc hash table ngầm bên dưới, mang lại hiệu suất O(1) trung bình tương tự như Python dictionary và Java HashMap.
Khi nào sử dụng Hash Table? Ứng dụng thực tế
Hash table là lựa chọn cấu trúc dữ liệu lý tưởng trong nhiều tình huống lập trình thực tế, đặc biệt là khi bạn cần lưu trữ một bộ sưu tập các mục và thường xuyên thực hiện các thao tác tìm kiếm, thêm hoặc xóa dữ liệu dựa trên một khóa duy nhất với tốc độ cao.
Với hiệu suất O(1) trung bình cho các thao tác cơ bản, hash table là một công cụ mạnh mẽ để giải quyết các bài toán mà tốc độ truy cập dữ liệu là yếu tố then chốt.
Một trong những ứng dụng phổ biến nhất của hash table là xây dựng bộ nhớ đệm (cache). Cache lưu trữ tạm thời kết quả của các phép tính, truy vấn cơ sở dữ liệu hoặc dữ liệu truy cập gần đây dưới dạng cặp khóa-giá trị để sử dụng lại sau này mà không cần tính toán lại hoặc truy xuất từ nguồn chậm hơn.
Hash table cũng được sử dụng hiệu quả để đếm tần suất xuất hiện của các phần tử trong một tập dữ liệu lớn, ví dụ: đếm số lần xuất hiện của mỗi từ trong một văn bản. Khóa sẽ là phần tử (ví dụ: từ), giá trị sẽ là số lần xuất hiện. Hash table giúp cập nhật và truy vấn số đếm rất nhanh.
Trong lĩnh vực cơ sở dữ liệu, hash table thường được sử dụng để xây dựng các chỉ mục (index) cho bảng. Chỉ mục dựa trên hash table cho phép hệ quản trị cơ sở dữ liệu nhanh chóng định vị các bản ghi dựa trên giá trị của một cột đã được băm chỉ trong vài bước, giúp tăng tốc đáng kể các truy vấn tìm kiếm.
Cấu trúc dữ liệu Tập hợp (Set), vốn chỉ lưu trữ các phần tử duy nhất và hỗ trợ các thao tác kiểm tra sự tồn tại, thêm, xóa, có thể được triển khai rất hiệu quả bằng cách sử dụng hash table. Trong trường hợp này, các phần tử của tập hợp được lưu trữ làm khóa trong hash table, và giá trị có thể là null hoặc một giá trị mặc định nào đó.
Hash table còn được sử dụng trong việc kiểm tra tính duy nhất của các phần tử, xây dựng bảng biểu tượng (symbol table) trong trình biên dịch, hoặc trong các thuật toán liên quan đến xử lý chuỗi và so sánh dữ liệu.
Nguồn tham khảo: Hash Table (Bảng Băm) là gì? Toàn tập về cấu trúc & hoạt động - Interdata.vn
