[NOTE]Trong nội dung cấu trúc dữ liệu nân cao mình tìm thấy bài này giá trị nên quote về cho mọi người xem.[/NOTE] Hashing là cái gì? Hashing (mảng băm) là một cấu trúc dữ liệu cho phép lưu trữ & tìm kiếm giá trị (dạng chuỗi ký tự) ở độ phức tạp O(1). Nghĩa là tốc độ tìm kiếm phần tử luôn là một hằng số, dù số phần tử lên đến cả tỷ. Làm sao được như vậy? Ví dụ: muốn tổ chức một mảng để lưu trữ 3 chuỗi "dream", "pete", và "soda". Trước hết, khởi tạo một mảng như bình thường, với mỗi phần tử kiểu chuỗi. Sau đó, mình lấy 3 chuỗi trên và tính giá trị hashcode cho chúng theo cách sau: qui ước ký tự 'a'=1, 'b'=2,... đến 'z'=26. Ta có: Mã: dream = 4 + 18 + 5 + 1 + 13 = 41 pete = 16 + 5 + 20 + 5 = 46 soda = 19 + 15 + 4 + 1 = 39 Tính xong rồi, thế là đặt "dream" vào vị trí 41, "pete" vào vị trí 46, và "soda" vào vị trí 39 của mảng. Sau này, muốn truy xuất, thì mình tính hashcode 1 lần nữa rồi vô mảng mà lấy. Sao đơn giản dzậy? Thực tế thì phức tạp hơn 1 chút. Cách làm như ví dụ trên tệ ở chỗ: chỉ để chứa 3 phần tử mà cần 1 cái mảng tới 46 "ô". Thế thì giải quyết như thế này: lấy hashcode thu được rồi chia modulo cho tổng sức chứa. Ví dụ, nếu chỉ muốn chứa 10 phần tử, ta tính như vầy: Mã: dream = 41 % 10 = 1 pete = 46 % 10 = 6 soda = 39 % 10 = 9 Thế thì đặt "dream" vô vị trí 1, "pete" vô 6, và "sodo" vô 9. Xem chừng ổn 1 chút. Hết rồi hả? Chưa đâu! xem thử trường hợp này nè: tui muốn bổ sung thêm vào mảng trên 1 phần tử nữa, là "sado". Tính hashcode cho phần tử mới: Code: "sado" = 19 + 1 + 4 + 15 = 39, lấy 39 % 10 = 9 Anh chàng "sado" này bị trùng chổ với tiểu thư "soda" rồi! Vậy giải quyết làm sao? Phối hợp cả 2 cách bên dưới: - Thứ nhất: thiết kế một hàm băm (hash funtion) thật tốt. Phải "băm" làm sao cho tỷ lệ trùng nhau giữa các chuỗi khác nhau là rất thấp. Ví dụ: đem nhân giá trị của ký tự cho 1 số nào đó, cộng hết lại, rồi chia modulo cho 1 số nguyên tố (vì sao lại là nguyên tố? thử suy nghĩ nhé!) - Thứ hai: nếu đã băm rồi mà vẫn còn đụng độ thì dùng một trong 2 kỹ thuật linear-probing và buckets để giải quyết: + Linear-probing: ý tưởng là dò tìm vị trí trống tiếp theo rồi chèn phần tử bị đụng độ vào đó. Trong ví dụ trên, khi anh "sado" bị đụng tại vị trí 9, tôi tìm và thấy ô thứ 10 còn trống, thế thì tôi chèn "anh" vào đó. Khi mảng đầy, tôi resize lại mảng cho lớn hơn 1 chút. + Buckets: Thay vì cố gắng tìm trong danh sách một vị trí còn trống kế tiếp, kỹ thuật buckets tổ chức lại cấu trúc danh sách để có thể đặt nhiều phần tử vào cùng một vị trí, như thế này: Mã: 0| 1|-"dream" 2| 3| 4| 5| 6|-"pete" 7| 8| 9|-"soda" -- "sado" Ở đây, ta tổ chức một danh sách liên kết 2 chiều. Khi bị đụng, ta nối phần tử mới vào phía sau phần tử đã có. Làm gì thì làm, thực tế đụng độ vẫn có thể xảy ra. Khi có nhiều phần tử được đặt cùng một vị trí thì tốc độ tìm kiếm sẽ bị giảm xuống. Người ra đề xuất giải pháp thay đổi lại kích thước của danh sách để các phần tử được phân phối một cách thích hợp. Thông thường người ta dựa vào một giá trị gọi là thừa số tải (load factor) – tỷ lệ giữa số phần tử đã được lưu trữ trên tổng số phần tử của danh sách. Khi tỷ lệ này chạm đến mức thừa số tải thì thao tác thay đổi kích thước tự động được thi hành. Trong ví dụ trên, thừa số tải là 4 / 10 = 40%. Thông thường một thừa số tải thích hợp là 0.75, tức 75%. Code ví dụ đi! Ờ, có chương trình nhỏ (viết cách đây 2 năm) đây nè, viết bằng Visual C++, sử dụng kỹ thuật buckets. Mỗi phần tử là một kiểu cấu trúc gồm 3 phần: -Khóa (key): kiểu chuỗi ký tự -Giá trị (value): kiểu số nguyên -Con trỏ đến phần tử kế tiếp (next) Code: Mã: #include <stdio.h> #include <tchar.h> #include <windows.h> const long PARALEN = 100; //số lượng trung bình các phần tử thực tế class Hashtable { private: struct ItemType{ TCHAR key[50]; long value; ItemType *next; }; typedef ItemType *Item; Item *data; //data là một danh sách các Item long capacity; //sức chứa của Hashtable long num; //num là số lượng các phần tử thực tế //Hàm làm tròn dung lượng hashtable long GetRoundCapacity() { long result = 1; while (result < capacity) { result*=10; } return result; } //Hàm lấy mã băm long GetHashCode(const TCHAR *string) { long code = 0; long sum = 0; long round = GetRoundCapacity(); char length = _tcslen(string); for(char i=0; i < length; i++) sum = sum*3 + string[i]; while (sum > 0) { code = code + sum%round; sum = sum/round; } return code%capacity; } public: //Hàm dựng Hashtable(long capac) { capacity = capac; data = (Item *)malloc(capacity*sizeof(Item)); num = 0; for(long i=0; i<capacity; i++) { data[i] = NULL; } } //Kiểm tra một khóa có tồn tại trong hashtable hay không BOOL Contain(const TCHAR *key) { Item temp; BOOL found = FALSE; long pos = GetHashCode(key); temp = data[pos]; while ((temp != NULL) && (!found)) { if (_tcsicmp(temp->key,key)==0) found = TRUE; else temp = temp->next; } return found; } //Chèn một phần tử vào hashtable BOOL Put(const TCHAR *key, const long value) { Item temp, current; long pos = GetHashCode(key); if (Contain(key)) return FALSE; //nếu khóa đã tồn tại thì kết thúc temp = (Item)malloc(sizeof(ItemType)); //tạo một phần tử mới _tcscpy(temp->key, key); temp->value = value; temp->next = data[pos]; //chèn phần tử mới vào đầu data[pos] = temp; return TRUE; } //Phương thức lấy giá trị dựa vào khóa cho trước long Get(const TCHAR *key) { long pos = GetHashCode(key); Item temp = data[pos]; BOOL found = FALSE; while ((temp != NULL) && (!found)) { if (_tcsicmp(temp->key, key)==0) found = TRUE; else temp = temp->next; } if (found) return (temp->value); else return -1; } //Phương thức loại bỏ một phần tử ra khỏi hashtable void Remove(const TCHAR *key) { Item temp, temp2; BOOL done = FALSE; long pos = GetHashCode(key); if (data[pos]==NULL) return; //nếu không tồn tại khóa thì kết thúc temp = data[pos]; if (_tcsicmp(temp->key, key)==0) //nếu khóa nằm ngay vị trí đầu thì loại bỏ phần tử đầu { data[pos] = data[pos]->next; free(temp); } else //ngược lại, loại bỏ phần tử ở giữa nếu tìm thấy { temp2 = temp->next; while ((!done) && (temp2!=NULL)) { if (_tcsicmp(temp2->key,key)==0) { temp->next = temp2->next; free(temp2); done = TRUE; } else{ temp = temp->next; temp2 = temp2->next; } } }} // In tất cả các phần tử trong hashtable void ViewAll() { Item temp; if (num <= 0) { printf("No Item"); return; } for(long i = 0; i < capacity; i++) { if (data[i]!= NULL) { temp = data[i]; while (temp != NULL) { printf("%s \t %d \n",temp->key, temp->value); temp = temp->next; } } } } }; //kiem tra xem thu void main() { Hashtable T(20); T.Put("vitung",30); T.Put("tranduy",30); T.Put("dinhtu",10); T.ViewAll(); } Nguồn : congdongcviet
