Bảng Hash 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ó. Truy cập dữ liệu trở nên rất nhanh nếu chúng ta biết chỉ số 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 hoạt động chèn và tìm kiếm 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 ra một chỉ mục trong đó một phần tử sẽ được chèn hoặc được định vị từ đó.
Băm
Băm là một kỹ thuật để chuyển đổi một phạm vi các giá trị chính thành một phạm vi các chỉ mục của một mảng. Chúng tôi sẽ sử dụng toán tử modulo để có được 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 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)
Probing tuyến tính
Như chúng ta có thể thấy, kỹ thuật băm được sử dụng để tạo ra một chỉ mục đã được sử dụng của mảng. Trong trường hợp như vậ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 chúng ta tìm thấy một ô trống. Kỹ thuật này được gọi là thăm dò tuyến tính.
Hoạt động cơ bản
Sau đây là các hoạt động cơ bản của bảng băm.
- Tìm kiếm - Tìm kiếm một phần tử trong bảng băm.
- Chèn - chèn một phần tử trong bảng băm.
- xóa - 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 đó tìm kiếm sẽ được tiến hành trong bảng băm.
struct DataItem {
int data;
int key;
};Phương pháp băm
Xác định phương thức 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 tìm kiếm, hãy tính mã băm của khóa được truyền và định vị 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ử về phía trước nếu không tìm thấy phần tử tại mã băm được tính toán.
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 mã băm của khóa được truyền và định vị 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 tại 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 mã băm của khóa được truyền và định vị 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 không tìm thấy phần tử tại mã băm được tính toán. Khi tìm thấy, lưu trữ một mục 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;
}Được cập nhật: 15 tháng 4 lúc 11:52:07 | Lượt xem: 895
