Trong khoa học máy tính, bảng băm(Hash Tables) là một cấu trúc dữ liệu sử dụng hàm băm để ánh xạ từ giá trị xác định, được gọi là khóa (ví dụ như tên của một người), đến giá trị tương ứng (ví dụ như số điện thoại của họ). Do đó, bảng băm là một mảng kết hợp. Hàm băm được sử dụng để chuyển đổi từ khóa thành chỉ số (giá trị băm) trong mảng lưu trữ các giá trị tìm kiếm.
Tóm Tắt
1. Lý thuyết về bảng băm
Băm là một kỹ thuật được sử dụng để định danh một đối tượng người tiêu dùng đơn cử trong một nhóm những đối tượng người dùng tương tự như. Một số ví dụ về việc sử dụng bảng băm trên trong thực tiễn :
- Trong trường đại học, mỗi sinh viên được chỉ định một mã sinh viên không giống nhau và qua mã sinh viên đó có thể truy xuất các thông tin của sinh viên đó.
- Trong thư viện, mỗi một cuốn sách một mã số riêng và mã số đó có thể được dùng để xác định các thông tin của sách, chẳng hạn như vị trí chính xác của sách trong thư viện hay thể loại của sách đó,…
Trong cả 2 ví dụ trên, các sinh viên và các cuốn sách được “băm” thành các mã số duy nhất(không trùng lặp).
Giả sử rằng bạn có một đối tượng và bạn muốn gán cho nó một cái khóa(key) để giúp tìm kiếm dễ dàng hơn. Để lưu giữ cặp
Trong hashing, các key có giá trị lớn sẽ được đưa về giá trị nhỏ hơn bằng cách sử dụng hàm băm(hash functions). Các giá trị sau đó được lưu trong một cấu trúc dữ liệu gọi là bảng băm(hash tables). Ý tưởng của hashing là đưa các cặp
Việc hashing được triển khai qua 2 bước :
- Một phần tử sẽ được chuyển đổi thành 1 số nguyên bằng việc sử dụng hàm băm. Phần tử này được sử dụng như một chỉ mục để lưu trữ phần tử gốc và nó sẽ được đưa vào bảng băm.
- Phần tử sẽ được lưu giữ trong bảng băm, nó có thể được truy xuất nhanh bằng khóa băm:
- hash = hashfunc(key)
- index = hash % array_size
Theo cách trên thì việc băm sẽ phụ thuộc vào kích thước mảng array_size. Chỉ số index sau đó được đưa về [0; array_size-1] bằng việc sử dụng toán tử chia lấy dư %.
2. Hàm băm
Hàm băm là bất kể hàm nào hoàn toàn có thể được sử dụng để ánh xạ tập dữ liệu có size tùy ý thành tập dữ liệu có size cố định và thắt chặt và đưa vào bảng băm. Các giá trị được trả về bởi hàm băm được gọi là giá trị băm .
Một hàm băm được nhìn nhận tốt nếu nó đạt được những nhu yếu cơ bản sau :
- Dễ tính toán: Nó phải dễ tính toán và bản thân nó không phải là một thuật toán
- Phân bố đồng đều: Nó cần phải phân phối đồng đều trên bảng băm, không xảy ra việc tập trung thành các cụm
- Ít va chạm: Va chạm xảy ra khi các cặp phần tử được ánh xạ tới cùng một giá trị băm
Chú ý: Bất kể hàm băm có tốt đên đâu, va chạm vẫn có thể xảy ra. Vì vậy, để duy trì hiệu suất của bảng băm, điều quan trọng là phải quản lý va chạm thông qua các kỹ thuật giải quyết va chạm.
Tại sao phải cần hàm băm đủ tốt?
Hãy đi vào một ví dụ để dễ tưởng tượng nhé. Giả sử rằng bạn cần lưu giữ những string sau đây trong bảng băm : { “ abcdef ”, “ bcdefa ”, “ cdefab ”, “ defabc ” } .
Để thống kê giám sát chỉ mục lưu giữ những string này, tất cả chúng ta dùng một hàm băm như sau : Chỉ mục của mỗi string sẽ được tính bằng tổng giá trị ASCII của những ký tự trong nó sau đó lấy dư với 599 .
Do 5 là số nguyên tố và nó lớn hơn số lượng thành phần, nó có năng lực lập ra những chỉ mục khác nhau ( giảm va chạm ). Số nguyên tố luôn là lựa chọn tốt nếu bạn muốn dùng phép lấy phần dư. Các giá trị ASCII của a, b, c, d, e và f lần lượt là 97, 98, 99, 100, 101 và 102 .
Dễ nhận thấy, những string kia chỉ là những hoán vị của cùng 1 chuỗi, do đó chỉ mục được tạo ra của chúng đều giống nhau và đều bằng 597 % 5 = 2 .
Lúc này, hàm băm sẽ đo lường và thống kê và toàn bộ những string kia đều có cùng 1 chỉ mục. Khi đó, bạn hoàn toàn có thể tạo 1 list tại chỉ số đó để lưu những string trong list đó. Như hình ảnh minh họa này :
Bạn thấy đó, bạn vẫn sẽ mất O ( n ) để tìm kiếm một string đơn cử. Điều đó có nghĩa hàm băm này chưa thực sự tốt .
Hãy thử với 1 hàm băm khác nhé. Chỉ mục của những string sẽ được tính bằng tổng của những mã ASCII của từng ký tự theo sau là vị trí của ký tự đó trong string. Sau đó đem chia dư cho số nguyên tố 2069 .
String Hash function Index
abcdef (971 + 982 + 993 + 1004 + 1015 + 1026)%2069 38
bcdefa (981 + 992 + 1003 + 1014 + 1025 + 976)%2069 23
cdefab (991 + 1002 + 1013 + 1024 + 975 + 986)%2069 14
defabc (1001 + 1012 + 1023 + 974 + 985 + 996)%2069 11
Lúc này, những chỉ mục của mỗi string là không trùng lặp ( không va chạm ) .
3. Kỹ thuật xử lý va chạm
3.1. Separate chaining (open hashing)
Separate chaining là một kỹ thuật giải quyết và xử lý và chạm phổ cập nhất. Nó thường được thiết lập với list link. Để lưu giữ một thành phần trong bảng băm, bạn phải thêm nó vào một list link ứng với chỉ mục của nó. Nếu có sự va chạm xảy ra, những thành phần đó sẽ nằm cùng trong 1 list link ( xem ảnh để hiểu hơn ) .
Như vậy, kỹ thuật này sẽ đạt được vận tốc tìm kiếm O ( 1 ) trong trường hợp tối ưu và O ( N ) nếu tổng thể những thành phần ở cùng 1 list link duy nhất. Đó là do có điều kiện kèm theo 3 trong tiêu chuẩn hàm băm tốt .
Cài đặt bảng băm sử dụng Separate chaining
Giả định : Hàm băm sẽ trả về số int trong [ 0, 19 ] .
| 0123 |
vector inthashTableSize=20; |
Thêm vào bảng băm
| 012345678 |
voidinsert(strings) { / / Compute the index using Hash Function intindex=hashFunc(s); / / Insert the element in the linked list at the particular index hashTable[index].push_back(s); } |
Tìm kiếm
| 012345678910111213141516 |
voidsearch(strings) { / / Compute the index by using the hash function intindex=hashFunc(s); / / Search the linked list at that specific index for(inti=0;i { if(hashTable[index][i]==s) { cout< return; } } cout< } |
3.2. Linear probing (open addressing or closed hashing)
Trong kỹ thuật giải quyết và xử lý va chạm này, tất cả chúng ta sẽ không dùng linklist để tàng trữ mà chỉ có bản thân array đó thôi .
Khi thêm vào bảng băm, nếu chỉ mục đó đã có thành phần rồi ; Giá trị chỉ mục sẽ được đo lường và thống kê lại theo chính sách tuần tự. Giả sử rằng chỉ mục là chỉ số của mảng, khi đó, việc đo lường và thống kê chỉ mục cho thành phần được tính theo cách sau :
index = index % hashTableSize
index = (index + 1) % hashTableSize
index = (index + 2) % hashTableSize
index = (index + 3) % hashTableSize
Và cứ thế theo cách như vậy chừng nào index thu được chưa có thành phần được sử dụng. Tất nhiên, khoảng trống chỉ mục phải được bảo vệ để luôn có chỗ cho thành phần mới .
Như trong ví dụ dưới đây, chuỗi Hashing bị trùng chỉ mục(2) ở lần đầu tính chỉ mục. Do đó, nó được đẩy lên vị trí trống ở phía sau(3).
Cài đặt bảng băm dùng Linear probing
Giả sử rằng :
- Không có nhiều hơn 20 phần tử trong tập dữ liệu
- Hàm băm sẽ trả về một số nguyên từ 0 đến 19
- Tập dữ liệu phải là các phần tử duy nhất
| 0123 |
stringhashTable[21]; inthashTableSize=21; |
Thêm vào bảng băm
| 012345678910 |
voidinsert(strings) { / / Compute the index using the hash function intindex=hashFunc(s); / / Search for an unused slot and if the index will exceed the hashTableSize then roll back while(hashTable[index]!=” “) index=(index+1)%hashTableSize; hashTable[index]=s; } |
Tìm kiếm
| 01234567891011121314 |
voidsearch(strings) { / / Compute the index using the hash function intindex=hashFunc(s); / / Search for an unused slot and if the index will exceed the hashTableSize then roll back while(hashTable[index]!=sandhashTable[index]!=” “) index=(index+1)%hashTableSize; / / Check if the element is present in the hash table if(hashTable[index]==s) cout< else cout< } |
3.3. Quadratic Probing
Ý tưởng cũng khá giống Linear Probing, nhưng cách tính chỉ mục có khác đôi chút :
index = index % hashTableSize
index = (index + 12) % hashTableSize
index = (index + 22) % hashTableSize
index = (index + 32) % hashTableSize
Và cứ thế cho tới khi tìm được chỉ mục trống .
Cài đặt bảng băm dùng Quadratic Probing
Giả sử rằng :
- Không có nhiều hơn 20 phần tử trong tập dữ liệu
- Hàm băm sẽ trả về một số nguyên từ 0 đến 19
- Tập dữ liệu phải là các phần tử duy nhất
| 0123 |
stringhashTable[21]; inthashTableSize=21; |
Thêm phần tử
|
012345678
9 1011121314 |
voidinsert(strings) { / / Compute the index using the hash function intindex=hashFunc(s); / / Search for an unused slot and if the index will exceed the hashTableSize roll back inth=1; while(hashTable[index]!=” “) { index=(index+h *h)%hashTableSize; h++; } hashTable[index]=s; } |
Tìm kiếm phần tử
| 0123456789101112131415161718 |
voidsearch(strings) { / / Compute the index using the Hash Function intindex=hashFunc(s); / / Search for an unused slot and if the index will exceed the hashTableSize roll back inth=1; while(hashTable[index]!=sandhashTable[index]!=” “) { index=(index+h *h)%hashTableSize; h++; } / / Is the element present in the hash table if(hashTable[index]==s) cout< else cout< } |
3.4. Double hashing
Vẫn giống 2 kỹ thuật ngay phía trên, chỉ khác ở công thức tính khi xảy ra va chạm như sau :
index = (index + 1 * indexH) % hashTableSize;
index = (index + 2 * indexH) % hashTableSize;
Và cứ liên tục cho tới khi tìm được chỉ mục chưa được sử dụng .
Cài đặt bảng băm dùng Double hashing
Giả sử rằng :
- Không có nhiều hơn 20 phần tử trong tập dữ liệu
- Hàm băm sẽ trả về một số nguyên từ 0 đến 19
- Tập dữ liệu phải là các phần tử duy nhất
| 0123 |
stringhashTable[21]; inthashTableSize=21; |
Thêm vào bảng băm
| 01234567891011 |
voidinsert(strings) { / / Compute the index using the hash function1 intindex=hashFunc1(s); intindexH=hashFunc2(s); / / Search for an unused slot and if the index exceeds the hashTableSize roll back while(hashTable[index]!=” “) index=(index+indexH)%hashTableSize; hashTable[index]=s; } |
Tìm kiếm trên bảng băm
| 0123456789101112131415 |
voidsearch(strings) { / / Compute the index using the hash function intindex=hashFunc1(s); intindexH=hashFunc2(s); / / Search for an unused slot and if the index exceeds the hashTableSize roll back while(hashTable[index]!=sandhashTable[index]!=” “) index=(index+indexH)%hashTableSize; / / Is the element present in the hash table if(hashTable[index]==s) cout< else cout< } |
4. Ứng dụng của bảng băm
Trong các bài toán thông thường, các bạn thường chỉ cần sử dụng cấu trúc dữ liệu được cài đặt sẵn ở các ngôn ngữ lập trình: map, set trong C/C++, Java; Dictionary trong C#, Python. Đó chính là các bảng băm cực kỳ hữu dụng mà chúng ta vẫn hay sử dụng.
Nếu các bạn để ý thì multimap và multiset trong C++ cho phép lưu trữ key trùng nhau với giá trị khác nhau đó. Đó là 2 thằng đã được thiết lập cơ chế xử lý va chạm.
Với những bài toán đặc trưng, những bạn sẽ phải tự viết cho mình hàm băm và thiết kế xây dựng cấu trúc tài liệu bảng băm cho tương thích. Dưới đây là một số ít ứng dụng của bảng băm :
- Associative arrays: Bảng băm thường được sử dụng để cài đặt nhiều loại in-memory tables. Chúng được sử dụng để thực hiện các mảng kết hợp (các mảng có chỉ số là các chuỗi tùy ý hoặc các đối tượng phức tạp khác).
- Lập chỉ mục CSDL: Các bảng băm cũng có thể được sử dụng làm cấu trúc dữ liệu để lập chỉ mục dữ liệu trong các CSDL.
- Caches: Bảng băm dùng để thiết lập cơ chế caches, thường được dùng để tăng tốc độ truy cập dữ liệu.
- Biểu diễn các đối tượng: Một số ngôn ngữ động, chẳng hạn như Perl, Python, JavaScript và Ruby sử dụng bảng băm để triển khai các đối tượng.
- Hàm băm được sử dụng trong các thuật toán khác nhau để tăng tốc độ tính toán.
5. Bài tập thực hành
Một số link chứa bài tập thực hành thực tế dành cho bạn :
- http://ntucoder.net/Problem/List?ThemeID=29
- https://www.hackerearth.com/practice/data-structures/hash-tables/basics-of-hash-tables/practice-problems/
- https://www.spoj.com/KSTN/problems/HASH2509/
Source: https://final-blade.com
Category: Kiến thức Internet
