- Cấu hình dữ liệu
- Học C/C++
By
Nguyễn Văn Hiếu-
3
78105
Mục này là phần 3 của 16 trong loạt bài Cấu trúc dữ liệu
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 . Do đó, bảng băm là một mảng hợp nhất. Hàm băm được sử dụng để chuyển từ khóa thành chỉ số [giá trị băm] trong mảng lưu trữ các giá trị được tìm kiếm
NỘI DUNG BÀI VIẾT
- 1. Lý thuyết về bảng trùm
- 2. hash
- Tại sao phải cần hàm đủ tốt?
- 3. Kỹ thuật xử lý va chạm
- 3. 1. Chuỗi riêng biệt [băm mở]
- 3. 2. Thăm dò tuyến tính [xác định địa chỉ mở hoặc băm đóng]
- Cài đặt bảng băm dùng thăm dò tuyến tính
- 3. 3. Thăm dò bậc hai
- Cài đặt bảng băm sử dụng Quadratic Probing
- 3. 4. băm đôi
- Cài đặt bảng băm sử dụng Double hashing
- 4. Ứng dụng của bảng băm
- 5. Bài tập thực thi
1. Lý thuyết về bảng trùm
Băm là một kỹ thuật được sử dụng để xác định danh sách một đối tượng cụ thể trong một nhóm các đối tượng tương tự. Một số ví dụ về việc sử dụng bảng trùm trên thực tế
- Trong trường đại học, mỗi sinh viên chỉ được xác đị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 cuốn sách có một mã số riêng và mã số đó có thể được sử 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 hoặc có 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 lặp lại]
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 từ khóa [key] để giúp việc tìm kiếm dễ dàng hơn. Để lưu giữ cặp [nó thường được gọi là hơn], bạn có thể sử dụng mảng bình thường để làm công việc này; . Tuy nhiên, trong trường hợp phạm vi của khóa lớn và không thể sử dụng chỉ số mảng được, khi đó bạn sẽ cần phải truy cập vào hash[hashing]
Trong hàm băm, các khóa 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 [hàm băm]. Các giá trị sau đó được lưu trong một cấu trúc dữ liệu được gọi là bảng băm [bảng băm]. Ý tưởng của hàm băm là đưa các cặp về một mảng hệ thống nhất; . Bằng cách sử dụng từ khóa định danh đó, chúng ta có thể truy cập trực tiếp vào nó với mức độ phức tạp O[1]. Thuật toán trùm sẽ sử dụng khóa băm để tính toán xác định khóa danh sách của các phần tử hoặc bổ sung vào bảng trùm
Việc băm công việc được thực hiện qua 2 bước
- Một phần tử sẽ được chuyển đổi thành 1 số nguyên bằng cách sử dụng hàm băm. Phần tử này được sử dụng như một mục duy nhất để 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 bảng băm
- hàm băm = hashfunc[key]
- chỉ mục = hàm băm % mảng_size
Theo cách trên, nhiệm vụ sẽ phụ thuộc vào kích thước mảng array_size. The number of index after that was given [0;
2. hash
Hàm băm là bất kỳ hàm nào có thể được sử dụng để ánh xạ tệp dữ liệu có kích thước tùy chọn thành tệp dữ liệu có kích thước cố định và đưa vào bảng băm. Các giá trị được trả về bởi hàm mũ được gọi là giá trị mũ
Một hàm được đánh giá tốt nếu nó đạt được các yêu cầu cơ bản sau
- Tính toán đơn giả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
- Đồng bộ phân vùng. 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. Và có thể xảy ra khi các cặp phần tử được ánh xạ tới cùng một giá trị trùm
Chú thích. Dù kể hà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 trùm, điều quan trọng là phải quản lý và 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 đủ tốt?
Please go to an example to easy to dung nhé. Giả sử rằng bạn cần lưu giữ các chuỗi sau đây trong bảng băm. {abcdef, bcdefa, cdefab , defabc }
Để tính toán chỉ mục lưu giữ các chuỗi này, chúng ta sử dụng một hàm băm như sau. Chỉ mục của mỗi chuỗi sẽ được tính bằng tổng giá trị ASCII của các ký tự trong nó sau đó lấy dư với 599
Do 5là số nguyên tố và nó lớn hơn số lượng phần tử, nó có khả năng thiết lập các 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 cho 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, các chuỗi kia chỉ là các vị trí thay thế của cùng 1 chuỗi, do đó chỉ mục được tạo ra của chúng giống nhau và đều bằng 597 % 5 = 2
Lúc này, hàm băm sẽ tính toán và tất cả các chuỗi kia đều có cùng 1 mục. Khi đó, bạn có thể tạo 1 danh sách tại số đó để lưu các chuỗi trong danh sách đó. Như hình ảnh minh họa này
Bạn thấy vậy, bạn vẫn sẽ mất O[n] để tìm kiếm cụ thể một chuỗi. Điều đó có nghĩa là 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 chuỗi sẽ được tính bằng tổng số mã ASCII của từng ký tự theo sau là vị trí của ký tự đó trong chuỗi. Sau đó chia dư cho số nguyên tố 2069
Chuỗi Hàm băm Chỉ mục
abcdef [971 + 982 + 993 + 1004 + 1015 + 1026]%2069 38
bcdefa [981 + 992 +
cdefab [991 + 1002 + 1013 + 1024 + 975 + 986]%2069 14
defabc [1001 + 1012 + 1023 + 974 + 985 + 996]%2069 11
Lúc này, các mục duy nhất của mỗi chuỗi không trùng lặp [không va chạm]
3. Kỹ thuật xử lý va chạm
3. 1. Chuỗi riêng biệt [băm mở]
Chuỗi riêng biệt là một kỹ thuật xử lý kỹ thuật và phổ biến nhất. Nó thường được cài đặt với danh sách liên kết. Để lưu giữ một phần tử trong bảng băm, bạn phải thêm nó vào một danh sách liên kết với chỉ mục của nó. Nếu có sự việc xảy ra, các phần tử đó sẽ giống nhau trong 1 danh sách liên kết [xem ảnh để hiểu rõ hơn]
Như vậy, kỹ thuật này sẽ đạt được tốc độ tìm kiếm O[1] trong trường hợp tối ưu và O[N] nếu tất cả các phần tử ở cùng 1 danh sách liên kết duy nhất. Đó là do có điều kiện 3 trong tiêu chí hàm tốt
Cài đặt bảng trùm sử dụng Chuỗi chuỗi riêng biệt
Giả định. Hàm sẽ trả về int number in [0, 19]
0
1
2
3
vectơ hashTable[20];
int hashTableSize = 20;
Thêm vào bảng trống
0
1
2
3
4
5
6
7
8
void insert[chuỗi s]
{
// Tính toán chỉ mục bằng Hàm băm
int index = hashFunc[s];
// Chèn phần tử vào danh sách được liên kết tại chỉ mục cụ thể
hashTable[index].push_back[s];
}
Tìm kiếm
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void tìm kiếm[chuỗi s]
{
//Tính toán chỉ mục bằng hàm băm
int index = hashFunc[s];
//Tìm kiếm danh sách được liên kết tại chỉ mục cụ thể đó
cho[int i = 0;i