Cấu trúc dữ liệu và thuật toán - Bảng băm

Bảng băm là một cấu trúc dữ liệu lưu trữ dữ liệu theo cách liên kết. Trong bảng băm, dữ liệu được lưu trữ ở định dạng mảng, trong đó mỗi giá trị dữ liệu có giá trị chỉ mục duy nhất của riêng nó. Việc truy cập dữ liệu trở nên rất nhanh nếu chúng ta biết chỉ mục của dữ liệu mong muốn.

Do đó, nó trở thành một cấu trúc dữ liệu trong đó các thao tác chèn và tìm kiếm diễn ra rất nhanh bất kể kích thước của dữ liệu. Bảng băm sử dụng một mảng làm phương tiện lưu trữ và sử dụng kỹ thuật băm để tạo chỉ mục nơi một phần tử sẽ được chèn vào hoặc được định vị từ đó.

Băm

Hashing là một kỹ thuật để chuyển đổi một loạt các giá trị khóa thành một loạt các chỉ mục của một mảng. Chúng ta sẽ sử dụng toán tử modulo để nhận một loạt các giá trị chính. Hãy xem xét một ví dụ về bảng băm có kích thước 20 và các mục sau đây sẽ được lưu trữ. Mục ở định dạng (khóa, giá trị).

• (1,20)
• (2,70)
• (42,80)
• (4,25)
• (12,44)
• (14,32)
• (17,11)
• (13,78)
• (37,98)

Sr.No.	Chìa khóa	Băm	Chỉ mục mảng
1	1	1% 20 = 1	1
2	2	2% 20 = 2	2
3	42	42% 20 = 2	2
4	4	4% 20 = 4	4
5	12	12% 20 = 12	12
6	14	14% 20 = 14	14
7	17	17% 20 = 17	17
số 8	13	13% 20 = 13	13
9	37	37% 20 = 17	17

Đo tuyến tính

Như chúng ta thấy, có thể xảy ra trường hợp kỹ thuật băm được sử dụng để tạo chỉ mục đã được sử dụng của mảng. Trong trường hợp này, chúng ta có thể tìm kiếm vị trí trống tiếp theo trong mảng bằng cách nhìn vào ô tiếp theo cho đến khi tìm thấy ô trống. Kỹ thuật này được gọi là thăm dò tuyến tính.

Sr.No.	Chìa khóa	Băm	Chỉ mục mảng	Sau khi dò tuyến tính, chỉ mục mảng
1	1	1% 20 = 1	1	1
2	2	2% 20 = 2	2	2
3	42	42% 20 = 2	2	3
4	4	4% 20 = 4	4	4
5	12	12% 20 = 12	12	12
6	14	14% 20 = 14	14	14
7	17	17% 20 = 17	17	17
số 8	13	13% 20 = 13	13	13
9	37	37% 20 = 17	17	18

Hoạt động cơ bản

Sau đây là các hoạt động chính cơ bản của bảng băm.

• Search - Tìm kiếm một phần tử trong bảng băm.

• Insert - Chèn một phần tử trong bảng băm.

• delete - Xóa một phần tử khỏi bảng băm.

Mục dữ liệu

Xác định một mục dữ liệu có một số dữ liệu và khóa, dựa vào đó việc tìm kiếm sẽ được thực hiện trong bảng băm.

struct DataItem {
   int data;
   int key;
};

Phương pháp băm

Xác định phương pháp băm để tính mã băm của khóa của mục dữ liệu.

int hashCode(int key){
   return key % SIZE;
}

Hoạt động tìm kiếm

Bất cứ khi nào một phần tử cần được tìm kiếm, hãy tính mã băm của khóa được truyền và xác định vị trí phần tử bằng cách sử dụng mã băm đó làm chỉ mục trong mảng. Sử dụng thăm dò tuyến tính để đưa phần tử đi trước nếu phần tử không được tìm thấy trong mã băm đã tính.

Thí dụ

struct DataItem *search(int key) {
   //get the hash
   int hashIndex = hashCode(key);
	
   //move in array until an empty
   while(hashArray[hashIndex] != NULL) {
	
      if(hashArray[hashIndex]->key == key)
         return hashArray[hashIndex];
			
      //go to next cell
      ++hashIndex;
		
      //wrap around the table
      hashIndex %= SIZE;
   }

   return NULL;        
}

Chèn hoạt động

Bất cứ khi nào một phần tử được chèn vào, hãy tính toán mã băm của khóa được truyền và xác định vị trí chỉ mục bằng cách sử dụng mã băm đó làm chỉ mục trong mảng. Sử dụng thăm dò tuyến tính cho vị trí trống, nếu một phần tử được tìm thấy trong mã băm được tính toán.

Thí dụ

void insert(int key,int data) {
   struct DataItem *item = (struct DataItem*) malloc(sizeof(struct DataItem));
   item->data = data;  
   item->key = key;     

   //get the hash 
   int hashIndex = hashCode(key);

   //move in array until an empty or deleted cell
   while(hashArray[hashIndex] != NULL && hashArray[hashIndex]->key != -1) {
      //go to next cell
      ++hashIndex;
		
      //wrap around the table
      hashIndex %= SIZE;
   }
	
   hashArray[hashIndex] = item;        
}

Xóa hoạt động

Bất cứ khi nào một phần tử bị xóa, hãy tính toán mã băm của khóa được truyền và xác định vị trí chỉ mục bằng cách sử dụng mã băm đó làm chỉ mục trong mảng. Sử dụng thăm dò tuyến tính để đưa phần tử đi trước nếu phần tử không được tìm thấy trong mã băm đã tính. Khi tìm thấy, hãy lưu trữ một vật phẩm giả ở đó để giữ nguyên hiệu suất của bảng băm.

Thí dụ

struct DataItem* delete(struct DataItem* item) {
   int key = item->key;

   //get the hash 
   int hashIndex = hashCode(key);

   //move in array until an empty 
   while(hashArray[hashIndex] !=NULL) {
	
      if(hashArray[hashIndex]->key == key) {
         struct DataItem* temp = hashArray[hashIndex]; 
			
         //assign a dummy item at deleted position
         hashArray[hashIndex] = dummyItem; 
         return temp;
      } 
		
      //go to next cell
      ++hashIndex;
		
      //wrap around the table
      hashIndex %= SIZE;
   }  
	
   return NULL;        
}

Để biết về triển khai băm trong ngôn ngữ lập trình C, vui lòng nhấp vào đây .