Bảng băm

Trong hướng dẫn này, bạn sẽ tìm hiểu bảng băm là gì. Ngoài ra, bạn sẽ tìm thấy các ví dụ làm việc về các phép toán bảng băm trong C, C ++, Java và Python.

Bảng băm là một cấu trúc dữ liệu đại diện cho dữ liệu dưới dạng các cặp khóa-giá trị . Mỗi khóa được ánh xạ tới một giá trị trong bảng băm. Các khóa được sử dụng để lập chỉ mục các giá trị / dữ liệu. Một cách tiếp cận tương tự được áp dụng bởi một mảng kết hợp.

Dữ liệu được biểu diễn trong một cặp giá trị khóa với sự trợ giúp của các phím như trong hình bên dưới. Mỗi dữ liệu được liên kết với một khóa. Khóa là một số nguyên trỏ đến dữ liệu.

1. Bảng địa chỉ trực tiếp

Bảng địa chỉ trực tiếp được sử dụng khi dung lượng của bảng được sử dụng không phải là vấn đề đối với chương trình. Ở đây, chúng tôi giả định rằng

  • các phím là số nguyên nhỏ
  • số lượng khóa không quá lớn và
  • không có hai dữ liệu nào có cùng một khóa

Một nhóm các số nguyên được gọi là vũ trụ U = (0, 1,… ., n-1).
Mỗi vị trí của bảng địa chỉ trực tiếp T(0… n-1)chứa một con trỏ đến phần tử tương ứng với dữ liệu.
Chỉ mục của mảng Tlà chính khóa và nội dung của Tlà một con trỏ đến tập hợp (key, element). Nếu không có phần tử nào cho một khóa thì nó được để là NULL.

Đôi khi, chìa khóa chính là dữ liệu.

Mã giả cho các hoạt động

 directAddressSearch(T, k) return T(k) directAddressInsert(T, x) T(x.key) = x directAddressDelete(T, x) T(x.key) = NIL

Hạn chế của bảng địa chỉ trực tiếp

  • Giá trị của khóa phải nhỏ.
  • Số lượng khóa phải đủ nhỏ để nó không vượt qua giới hạn kích thước của một mảng.

2. Bảng băm

Trong bảng băm, các khóa được xử lý để tạo ra một chỉ mục mới ánh xạ đến phần tử được yêu cầu. Quá trình này được gọi là băm.

Hãy h(x)là một hàm băm và klà một khóa.
h(k)được tính toán và nó được sử dụng làm chỉ số cho phần tử.

Hạn chế của bảng băm

  • Nếu cùng một chỉ mục được tạo ra bởi hàm băm cho nhiều khóa thì xung đột sẽ phát sinh. Tình huống này được gọi là va chạm.
    Để tránh điều này, một hàm băm phù hợp được chọn. Nhưng, không thể tạo ra tất cả các khóa duy nhất bởi vì |U|>m. Do đó, một hàm băm tốt có thể không ngăn chặn hoàn toàn các va chạm nhưng nó có thể làm giảm số lượng các va chạm.

Tuy nhiên, chúng tôi có các kỹ thuật khác để giải quyết va chạm.

Ưu điểm của bảng băm so với bảng địa chỉ trực tiếp:

Các vấn đề chính với bảng địa chỉ trực tiếp là kích thước của mảng và giá trị có thể lớn của một khóa. Hàm băm làm giảm phạm vi của chỉ mục và do đó kích thước của mảng cũng giảm.
Ví dụ, If k = 9845648451321, then h(k) = 11(bằng cách sử dụng một số hàm băm). Điều này giúp tiết kiệm bộ nhớ bị lãng phí trong khi cung cấp chỉ mục của 9845648451321mảng

Giải quyết va chạm bằng cách xâu chuỗi

Trong kỹ thuật này, nếu một hàm băm tạo ra cùng một chỉ mục cho nhiều phần tử, các phần tử này được lưu trữ trong cùng một chỉ mục bằng cách sử dụng danh sách được liên kết kép.

Nếu jlà vị trí cho nhiều phần tử, nó chứa một con trỏ đến đầu danh sách các phần tử. Nếu không có phần tử nào, jchứa NIL.

Mã giả cho các hoạt động

 chainedHashSearch(T, k) return T(h(k)) chainedHashInsert(T, x) T(h(x.key)) = x //insert at the head chainedHashDelete(T, x) T(h(x.key)) = NIL

Triển khai Python, Java, C và C ++

Python Java C C ++ 
 # Python program to demonstrate working of HashTable hashTable = ((),) * 10 def checkPrime(n): if n == 1 or n == 0: return 0 for i in range(2, n//2): if n % i == 0: return 0 return 1 def getPrime(n): if n % 2 == 0: n = n + 1 while not checkPrime(n): n += 2 return n def hashFunction(key): capacity = getPrime(10) return key % capacity def insertData(key, data): index = hashFunction(key) hashTable(index) = (key, data) def removeData(key): index = hashFunction(key) hashTable(index) = 0 insertData(123, "apple") insertData(432, "mango") insertData(213, "banana") insertData(654, "guava") print(hashTable) removeData(123) print(hashTable) 
 // Java program to demonstrate working of HashTable import java.util.*; class HashTable ( public static void main(String args()) ( Hashtable ht = new Hashtable(); ht.put(123, 432); ht.put(12, 2345); ht.put(15, 5643); ht.put(3, 321); ht.remove(12); System.out.println(ht); ) ) 
 // Implementing hash table in C #include #include struct set ( int key; int data; ); struct set *array; int capacity = 10; int size = 0; int hashFunction(int key) ( return (key % capacity); ) int checkPrime(int n) ( int i; if (n == 1 || n == 0) ( return 0; ) for (i = 2; i < n / 2; i++) ( if (n % i == 0) ( return 0; ) ) return 1; ) int getPrime(int n) ( if (n % 2 == 0) ( n++; ) while (!checkPrime(n)) ( n += 2; ) return n; ) void init_array() ( capacity = getPrime(capacity); array = (struct set *)malloc(capacity * sizeof(struct set)); for (int i = 0; i < capacity; i++) ( array(i).key = 0; array(i).data = 0; ) ) void insert(int key, int data) ( int index = hashFunction(key); if (array(index).data == 0) ( array(index).key = key; array(index).data = data; size++; printf(" Key (%d) has been inserted ", key); ) else if (array(index).key == key) ( array(index).data = data; ) else ( printf(" Collision occured "); ) ) void remove_element(int key) ( int index = hashFunction(key); if (array(index).data == 0) ( printf(" This key does not exist "); ) else ( array(index).key = 0; array(index).data = 0; size--; printf(" Key (%d) has been removed ", key); ) ) void display() ( int i; for (i = 0; i < capacity; i++) ( if (array(i).data == 0) ( printf(" array(%d): / ", i); ) else ( printf(" key: %d array(%d): %d ", array(i).key, i, array(i).data); ) ) ) int size_of_hashtable() ( return size; ) int main() ( int choice, key, data, n; int c = 0; init_array(); do ( printf("1.Insert item in the Hash Table" "2.Remove item from the Hash Table" "3.Check the size of Hash Table" "4.Display a Hash Table" " Please enter your choice: "); scanf("%d", &choice); switch (choice) ( case 1: printf("Enter key -: "); scanf("%d", &key); printf("Enter data -: "); scanf("%d", &data); insert(key, data); break; case 2: printf("Enter the key to delete-:"); scanf("%d", &key); remove_element(key); break; case 3: n = size_of_hashtable(); printf("Size of Hash Table is-:%d", n); break; case 4: display(); break; default: printf("Invalid Input"); ) printf("Do you want to continue (press 1 for yes): "); scanf("%d", &c); ) while (c == 1); )
 // Implementing hash table in C++ #include #include using namespace std; class HashTable ( int capacity; list *table; public: HashTable(int V); void insertItem(int key, int data); void deleteItem(int key); int checkPrime(int n) ( int i; if (n == 1 || n == 0) ( return 0; ) for (i = 2; i  capacity = size; table = new list(capacity); ) void HashTable::insertItem(int key, int data) ( int index = hashFunction(key); table(index).push_back(data); ) void HashTable::deleteItem(int key) ( int index = hashFunction(key); list::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 HashTable::displayHash() ( for (int i = 0; i < capacity; i++) ( cout << "table(" << i << ")"; for (auto x : table(i)) cout < " << x; cout << endl; ) ) int main() ( int key() = (231, 321, 212, 321, 433, 262); int data() = (123, 432, 523, 43, 423, 111); int size = sizeof(key) / sizeof(key(0)); HashTable h(size); for (int i = 0; i < n; i++) h.insertItem(key(i), data(i)); h.deleteItem(12); h.displayHash(); )

Hàm băm tốt

Một hàm băm tốt có các đặc điểm sau.

  1. Nó không được tạo ra các khóa quá lớn và không gian nhóm nhỏ. Không gian bị lãng phí.
  2. Các phím được tạo không được gần cũng không quá xa trong phạm vi.
  3. Sự va chạm phải được giảm thiểu càng nhiều càng tốt.

Một số phương pháp được sử dụng để băm là:

Phương pháp phân chia

Nếu klà một khóa và mlà kích thước của bảng băm, hàm băm h()được tính như sau:

h(k) = k mod m

Ví dụ: Nếu kích thước của bảng băm là 10và k = 112sau đó là h(k) = 112mod 10 = 2. Giá trị của mkhông được là quyền hạn của 2. Điều này là do quyền hạn của 2ở định dạng nhị phân là 10, 100, 1000,… . Khi chúng ta tìm thấy k mod m, chúng ta sẽ luôn nhận được p-bit bậc thấp hơn.

 nếu m = 22, k = 17 thì h (k) = 17 mod 22 = 10001 mod 100 = 01 nếu m = 23, k = 17 thì h (k) = 17 mod 22 = 10001 mod 100 = 001 nếu m = 24, k = 17 thì h (k) = 17 mod 22 = 10001 mod 100 = 0001 nếu m = 2p thì h (k) = p bit thấp hơn của m

Phương pháp nhân

h(k) = ⌊m(kA mod 1)⌋
Ở đâu,

  • kA mod 1đưa ra phần phân số kA,
  • ⌊ ⌋ cho giá trị sàn
  • Alà bất kỳ hằng số nào. Giá trị của sự Anằm trong khoảng từ 0 đến 1. Nhưng, một lựa chọn tối ưu sẽ được ≈ (√5-1)/2đề xuất bởi Knuth.

Băm chung

Trong băm phổ quát, hàm băm được chọn ngẫu nhiên độc lập với các khóa.

Mở địa chỉ

Nhiều giá trị có thể được lưu trữ trong một vị trí duy nhất trong bảng băm thông thường.

Bằng cách sử dụng địa chỉ mở, mỗi vị trí được lấp đầy bằng một phím duy nhất hoặc bên trái NIL. Tất cả các phần tử được lưu trữ trong chính bảng băm.

Unlike chaining, multiple elements cannot be fit into the same slot.

Open addressing is basically a collision resolving technique. Some of the methods used by open addressing are:

Linear Probing

In linear probing, collision is resolved by checking the next slot.
h(k, i) = (h'(k) + i) mod m
where,

  • i = (0, 1,… .)
  • h'(k) is a new hash function

If a collision occurs at h(k, 0), then h(k, 1) is checked. In this way, the value of i is incremented linearly.
The problem with linear probing is that a cluster of adjacent slots is filled. When inserting a new element, the entire cluster must be traversed. This adds to the time required to perform operations on the hash table.

Quadratic Probing

In quadratic probing, the spacing between the slots is increased (greater than one) by using the following relation.
h(k, i) = (h'(k) + c1i + c2i2) mod m
where,

  • c1và là các hằng số phụ dương,c2
  • i = (0, 1,… .)

Băm kép

Nếu xung đột xảy ra sau khi áp dụng một hàm băm h(k), thì một hàm băm khác sẽ được tính để tìm vị trí tiếp theo.
h(k, i) = (h1(k) + ih2(k)) mod m

Ứng dụng bảng băm

Bảng băm được triển khai ở đâu

  • tra cứu thời gian liên tục và chèn là bắt buộc
  • ứng dụng mật mã
  • dữ liệu lập chỉ mục là bắt buộc

thú vị bài viết...