Hash table là một cấu trúc dữ liệu phổ biến trong lập trình và được sử dụng rộng rãi để lưu trữ và truy xuất các phần tử dựa trên giá trị khóa của chúng. Trong bài viết này, chúng ta sẽ tìm hiểu cách xây dựng một Hash table đơn giản trong lập trình C/C++.
DANH SÁCH BÀI VIẾT Tìm hiểu Cấu trúc dữ liệu Hash table trong lập trình C/C++ Cây đa phân trong lập trình C/C++ – Cấu trúc dữ liệu cây đa phân Hiểu về cấu trúc dữ liệu cây trong lập trình C/C++ Chinh phục cấu trúc dữ liệu hàng đợi lập trình C/C++ trong 5 phút Cấu trúc dữ liệu ngăn xếp trong lập trình C/C++ Cấu trúc dữ liệu Danh sách liên kết (Linked list) trong lập trình C/C++ Cấu trúc dữ liệu cây nhị phân trong lập trình C/C++ Cây nhị phân tìm kiếm – Tìm hiểu cây nhị phân tìm kiếm trong C/C++ Duyệt tiền tố, trung tố, hậu tố trong cây nhị phân – Lập trình C/C++
Tìm hiểu Hash table
Cấu trúc của Hash table Một Hash table bao gồm một mảng các phần tử và một hàm băm (hash function) để ánh xạ khóa vào vị trí trong mảng. Khi thêm hoặc truy xuất một phần tử, hàm băm được sử dụng để tìm kiếm vị trí trong mảng tương ứng với khóa của phần tử.
Hàm băm là một hàm mà ánh xạ một giá trị khóa (key) thành một số nguyên (index) trong mảng. Hàm băm phải đảm bảo rằng các khóa khác nhau sẽ được ánh xạ đến các vị trí khác nhau trong mảng.
Một hàm băm đơn giản có thể được thực hiện như sau:
unsigned int hash_function(char *key, int table_size) {
unsigned int hash_value = 0;
for (int i = 0; i < strlen(key); i++) {
hash_value = hash_value * 31 + key[i];
}
return hash_value % table_size;
}
Hàm này ánh xạ một chuỗi ký tự (key) thành một số nguyên bằng cách sử dụng phép nhân và cộng. Phép nhân với số 31 được sử dụng để tạo ra sự khác biệt giữa các khóa và cộng các mã ASCII của các ký tự trong khóa lại để tạo ra giá trị băm cuối cùng. Cuối cùng, hàm trả về giá trị băm này chia lấy dư với kích thước của mảng để đảm bảo rằng giá trị nằm trong phạm vi của mảng.
Xây dựng Hash table
Xây dựng cấu trúc Hash table
Một Hash table có thể được xây dựng bằng cách sử dụng một cấu trúc dữ liệu cho mỗi phần tử trong mảng và một mảng để lưu trữ các phần tử này. Cấu trúc có thể được định nghĩa như sau:
typedef struct {
char *key;
int value;
} hash_elem;
Trong cấu trúc này, mỗi phần tử bao gồm một khóa (key) và giá trị (value) tương ứng.
Mảng được sử dụng để lưu trữ các phần tử và có thể được khởi tạo bằng cách sử dụng cấu trúc dữ liệu sau đây:
typedef struct {
hash_elem *elems;
int size;
} hash_table;
Trong đó, elems là một con trỏ đến mảng các phần tử trong Hash table và size là kích thước của mảng này.
Tạo một Hash table
Để tạo một Hash table, ta có thể sử dụng hàm sau đây:
hash_table *create_hash_table(int size) {
hash_table *table = (hash_table *) malloc(sizeof(hash_table));
table->elems = (hash_elem *) calloc(size, sizeof(hash_elem));
table->size = size;
return table;
}
Hàm này sử dụng hàm malloc() để cấp phát bộ nhớ cho Hash table và hàm calloc() để khởi tạo các phần tử trong mảng. Sau khi tạo Hash table, ta có thể thêm và truy xuất các phần tử bằng cách sử dụng các hàm thích hợp.
Thêm phần tử vào Hash table
Để thêm một phần tử vào Hash table, ta cần tìm vị trí trong mảng tương ứng với khóa của phần tử bằng cách sử dụng hàm băm. Sau đó, ta có thể gán giá trị của phần tử vào vị trí này trong mảng.
void add_element(hash_table *table, char *key, int value) {
int index = hash_function(key, table->size);
table->elems[index].key = key;
table->elems[index].value = value;
}
Hàm này sử dụng hàm băm để tìm vị trí trong mảng tương ứng với khóa của phần tử. Sau đó, hàm gán giá trị khóa và giá trị của phần tử vào vị trí này trong mảng.
Truy xuất phần tử từ Hash table
Để truy xuất một phần tử từ Hash table, ta cần tìm vị trí trong mảng tương ứng với khóa của phần tử bằng cách sử dụng hàm băm. Sau đó, ta có thể trả về giá trị của phần tử tại vị trí này trong mảng.
int get_element(hash_table *table, char *key) {
int index = hash_function(key, table->size);
return table->elems[index].value;
}
Hàm này sử dụng hàm băm để tìm vị trí trong mảng tương ứng với khóa của phần tử. Sau đó, hàm trả về giá trị của phần tử tại vị trí này trong mảng.
Giải phóng Hash table
Sau khi sử dụng xong Hash table, ta cần giải phóng bộ nhớ được cấp phát cho nó bằng cách sử dụng hàm sau đây:
void destroy_hash_table(hash_table *table) {
free(table->elems);
free(table);
}
Hàm này sử dụng hàm free() để giải phóng bộ nhớ đã cấp phát cho Hash table.
Độ phức tạp của Hash table
Độ phức tạp của Hash table phụ thuộc vào hàm băm và kích thước của mảng. Nếu hàm băm hoạt động tốt và kích thước của mảng đủ lớn, thì Hash table sẽ có độ phức tạp O(1) cho các thao tác thêm, truy xuất và xóa phần tử. Tuy nhiên, nếu kích thước của mảng quá nhỏ hoặc hàm băm không tốt, thì Hash table có thể trở nên chậm hơn vì sự xung đột của các phần tử khi chúng được lưu trữ tại cùng một vị trí trong mảng.
Kết luận
Trong bài viết này, chúng ta đã tìm hiểu về cấu trúc và hoạt động của Hash table trong lập trình C. Hash table là một cấu trúc dữ liệu quan trọng và được sử dụng rộng rãi trong nhiều ứng dụng, như tìm kiếm, sắp xếp và phân tích dữ liệu. Nếu bạn muốn tìm hiểu thêm về Hash table, hãy tham khảo các tài liệu và ví dụ khác trên internet để có được kiến thức chi tiết hơn.
[Xem tất cả bài viết chủ đề C/C++ tại đây]
XÊM THÊM Hiểu về cấu trúc dữ liệu cây trong lập trình C/C++ Cấu trúc dữ liệu Danh sách liên kết (Linked list) trong lập trình C/C++ Cấu trúc dữ liệu ngăn xếp trong lập trình C/C++ Cấu trúc dữ liệu cây nhị phân trong lập trình C/C++ Tìm hiểu các toán tử thao tác bit trong lập trình C/C++ Cấu trúc dữ liệu cây nhị phân trong lập trình C/C++ Thuật toán đếm số lượng chữ số của số nguyên dương n Thuật toán tính dãy số Fibonacci Bài toán chuẩn hóa xâu ký tự Kiểm tra số chẵn lẻ trong lập trình C/C++
