Hashing là phương pháp mà chúng ta có thể ánh xạ bất kỳ phần tử dữ liệu độ dài nào với một khóa có kích thước cố định. băm hoạt động như các cặp khóa-giá trị.
Hàm băm là hàm thực hiện ánh xạ trong một bản đồ băm. các phần tử dữ liệu được cung cấp làm đầu vào cho Hàm băm có thể nhận được cùng một khóa băm. Trong trường hợp này các phần tử có thể chồng lên nhau. Để tránh chồng chéo các phần tử có cùng khóa băm, khái niệm chuỗi đã được giới thiệu.
Tạo bản đồ băm
Để tạo một bản đồ băm, chúng ta cần hàm băm để xác định giá trị chỉ mục của phần tử dữ liệu.
Chúng ta có một bảng băm, với n nhóm. Để chèn một nút vào bảng băm , chúng tôi được cung cấp một hàm băm là
hashIndex =key% noOfBuckets
Bây giờ, chúng tôi sẽ sử dụng hàm băm này và tính toán hashindex của mọi giá trị được chèn vào hashmap .
-
Chèn phần tử và tính toán hashIndex của giá trị khóa nhất định, sau đó chèn nút mới vào cuối danh sách.
-
Để xóa một nút, chúng tôi sẽ tính toán chỉ số băm và trong nhóm tương ứng với Chỉ mục băm, chúng tôi sẽ tìm kiếm phần tử trong nhóm và xóa nó.
Ví dụ
#include<iostream>
#include <list>
using namespace std;
class Hash{
int BUCKET;
list < int >*table;
public:
Hash (int V);
void insertItem (int x);
void deleteItem (int key);
int hashFunction (int x){
return (x % BUCKET);
}
void displayHash ();
};
Hash::Hash (int b){
this->BUCKET = b;
table = new list < int >[BUCKET];
}
void Hash::insertItem (int key){
int index = hashFunction (key);
table[index].push_back (key);
}
void Hash::deleteItem (int key){
int index = hashFunction (key);
list < int >::iterator i;
for (i = table[index].begin (); i != table[index].end (); i++){
if (*i == key)
break;
}
if (i != table[index].end ())
table[index].erase (i);
}
void Hash::displayHash (){
for (int i = 0; i < BUCKET; i++){
cout << i;
for (auto x:table[i])
cout << " --> " << x;
cout << endl;
}
}
int main (){
int a[] = { 5, 12, 67, 9, 16 };
int n = 5;
Hash h (7);
for (int i = 0; i < n; i++)
h.insertItem (a[i]);
h.deleteItem (12);
h.displayHash ();
return 0;
} Đầu ra
0 1 2 --> 9 --> 16 3 4 --> 67 5 --> 5 6