Xóa bảng băm C++
By Show - 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ùmBă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 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
Theo cách trên, nhiệm vụ sẽ phụ thuộc vào kích thước mảng 2. hashHà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
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 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ạm3. 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ơ <chuỗi> 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 < hashTable[index].kích thước();i++) { nếu(hashTable[index][i] == s) { cout << s << " is found!" << endl; return; } } cout << s << " is not found!" << endl; }
3. 2. Thăm dò tuyến tính (xác định địa chỉ mở hoặc băm đóng)Trong kỹ thuật xử lý va chạm này, chúng ta sẽ không dùng linklist để lưu trữ mà chỉ có bản thân mảng đó thôi Khi thêm vào bảng băm, nếu mục đó đã có phần tử rồi; . Giả sử rằng chỉ mục là chỉ số của mảng, khi đó, công việc tính toán chỉ mục cho phần tử được tính theo cách sau index = index % hashTableSize Và cứ thế theo cách như vậy, chừng nào chỉ số thu được chưa có phần tử được sử dụng. Tất nhiên, không chỉ mục phải được đảm bảo để luôn có chỗ cho phần tử mới Như trong ví dụ dưới đây, Chuỗi băm bị trùng chỉ mục (2) ở lần đầu tính chỉ mục. Do đó, nó được đưa lên vị trí trống ở phía sau(3) Cài đặt bảng băm dùng thăm dò tuyến tínhGiả sử rằng
0 1 2 3
chuỗi hashTable[21]; int hashTableSize = 21;
Thêm vào bảng trống 0 1 2 3 4 5 6 7 8 9 10
void insert(chuỗi s) { //Tính toán chỉ mục bằng hàm băm int index = hashFunc(s); //Tìm kiếm một vị trí không sử dụng và nếu chỉ mục vượt quá hashTableSize thì hãy quay lại while(hashTable[index] ! = "") chỉ mục = (chỉ mục + 1) % hashTableSize; hashTable[index] = s; }
Tìm kiếm 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
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 vị trí không sử dụng và nếu chỉ mục vượt quá hashTableSize thì hãy quay lại while(hashTable[index] ! = s và hashTable[ . index] ! = "") chỉ mục = (chỉ mục + 1) % hashTableSize; //Kiểm tra xem phần tử có trong bảng băm hay không if(hashTable[index] == s) cout << s << " is found!" << endl; khác cout << s << " is not found!" << endl; }
3. 3. Thăm dò bậc haiÝ tưởng cũng khá giống Linear Probing, nhưng cách tính chỉ mục có đôi chút khác nhau index = index % hashTableSize And the next to going to when found a index item is empty Cài đặt bảng băm sử dụng Quadratic ProbingGiả sử rằng
0 1 2 3
chuỗi hashTable[21]; int hashTableSize = 21;
Add the element 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
void insert(chuỗi s) { //Tính toán chỉ mục bằng hàm băm int index = hashFunc(s); //Tìm kiếm vị trí không sử dụng và liệu chỉ mục có vượt quá khôi phục hashTableSize int h = 1; while(hashTable[index] ! = "") { chỉ mục = (chỉ mục + h*h) % hashTableSize; h ++ ; } hashTable[index] = s; }
Search search section 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
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 vị trí không sử dụng và liệu chỉ mục có vượt quá khôi phục hashTableSize int h = 1; while(hashTable[index] ! = s và hashTable[ . index] ! = "") { chỉ mục = (chỉ mục + h*h) % hashTableSize; h ++ ; } //Phần tử có trong bảng băm không if(hashTable[index] == s) cout << s << " is found!" << endl; khác cout << s << " is not found!" << endl; }
3. 4. băm đôiVẫn giống như 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; Và cứ tiếp tục cho đến khi tìm được mục chưa được sử dụng Cài đặt bảng băm sử dụng Double hashingGiả sử rằng
0 1 2 3
chuỗi hashTable[21]; int hashTableSize = 21;
Thêm vào bảng trống 0 1 2 3 4 5 6 7 8 9 10 11
void insert(chuỗi s) { //Tính toán chỉ mục bằng hàm băm1 int index = hashFunc1(s); int indexH = hashFunc2(s); //Tìm kiếm vị trí không sử dụng và nếu chỉ mục vượt quá giới hạn hashTableSize while(hashTable[index] ! = "") chỉ mục = (chỉ mục + indexH) % hashTableSize; hashTable[index] = s; }
Tìm kiếm trên bảng trùm 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
void tìm kiếm(chuỗi s) { //Tính toán chỉ mục bằng hàm băm int index = hashFunc1(s); int indexH = hashFunc2(s); //Tìm kiếm vị trí không sử dụng và nếu chỉ mục vượt quá giới hạn hashTableSize while(hashTable[index] ! = s và hashTable[ . index] ! = "") chỉ mục = (chỉ mục + indexH) % hashTableSize; //Phần tử có trong bảng băm không if(hashTable[index] == s) cout << s << " is found!" << endl; khác cout << s << " is not found!" << endl; }
4. Ứng dụng của bảng bămTrong 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 in C/C++, Java; . Đó 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 key trùng nhau với các giá trị khác nhau đó. Đó là 2 người đã thiết lập cơ chế xử lý va chạm Với các bài toán thù địch đặc biệt, các bạn sẽ phải tự viết cho mình hàm mũ và xây dựng bảng dữ liệu cấu trúc bảng băm cho phù hợp. Dưới đây là một số ứng dụng của bảng băm
5. Bài tập thực thiMột số liên kết chứa bài tập thực thi dành cho bạn
Nguyễn Văn Hiếu Sáng lập cộng đồng Lập Trình Không Khó với mong muốn giúp đỡ các bạn trẻ trên con đường trở thành những lập trình viên tương lai. Tất cả những gì tôi viết ra đây chỉ đơn giản là cơ sở thích ghi lại các kiến thức mà tôi tích lũy được |
