Hash table

Mảng băm

Mảng băm là một cấu trúc dữ liệu ánh xạ từ khóa tới dữ liệu. Trong mảng băm các khóa luôn luôn khác nhau. Hàm băm là là hàm số chuyển từ khóa thành giá trị băm tương ứng trong mảng lưu trữ các giá trị cần tìm.
Trong trường hợp lý tưởng thì một hàm băm sẽ luôn chuyển đổi khóa khác nhau thành các giá trị băm khác nhau. Tuy nhiên trong thực tế, các thuật toán băm luôn cung cấp cách giải quyết khi các khóa khác nhau lại băm về cùng một giá trị (hay còn gọi là va chạm băm).

Khi bảng băm có kích thước đủ lớn, thời gian trung bình để tra cứu một phần tử là hằng số O(1), không phụ thuộc vào số lượng phần tử trong bảng băm.

Ví dụ

Sau đây là cách cài đặt mảng băm đơn giản trong C. Ở ví dụ này, chúng ta có danh sách mảng với dữ liệu cần thêm vào bảng băm bao gồm số điện thoại (6 số cuối) và tên. Mảng băm là một mảng lưu các 10 địa chỉ. Hàm băm của chúng ta là lấy số điện thoại chuyển thành số nguyên rồi chia lấy dư cho 11.

Số điện thoại	Tên	Giá trị băm
124565	Tung	1
672922	Vuong	8
926506	Hoa	9

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


typedef struct Data {
  int phoneNumber;
  char name[10];
} Data;

typedef struct HashTable {
  Data** dataArray;
} HashTable;

int main() {
  const int SIZE_ARRAY = 10;
  HashTable ht;

  // cấp phát bộ nhớ
  ht.dataArray = (Data**) malloc(sizeof(Data*) * SIZE_ARRAY);

  // khởi tạo giá trị NULL
  for (int i = 0; i < SIZE_ARRAY; i++) {
    ht.dataArray[i] = NULL;
  }

  Data person1 = { .phoneNumber = 124565, .name = "Tung" };
  Data person2 = { .phoneNumber = 672922, .name = "Vuong" };
  Data person3 = { .phoneNumber = 926505, .name = "Hoa" };
}

Hàm thêm giá trị vào hàm băm

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


void addToHashTable(HashTable *hashTable, Data* data) {
  int key = data->phoneNumber % 11; // hàm băm
  
  Data* node = (Data*) malloc(sizeof(Data));
  node->phoneNumber = data->phoneNumber; // copy phoneNumber
  strcpy(node->name, data->name); // copy name

  hashTable->dataArray[key] = node;
}

int main() {
  addToHashTable(&ht, &person1);
  addToHashTable(&ht, &person2);
  addToHashTable(&ht, &person3);
}

Kiểm tra giá trị với key

Với hàm băm và key ta tìm được giá trị băm. Sử dụng giá trị băm và key ta có thể tìm được giá trị cần tìm.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


Data* findData(HashTable *hashTable, int phoneNumber) {
  int key = phoneNumber % 11;
  Data* node = hashTable->dataArray[key];
  if (node == NULL) {
    return NULL;
  }
  if (node->phoneNumber == phoneNumber) {
    return node;
  }
}

Xóa một giá trị trong bảng băm

Sau đây là hàm một giá trị trong bảng băm dựa theo key.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


void deleleData(HashTable* hashTable, int phoneNumber) {
  int key = phoneNumber % 11;
  Data* node = hashTable->dataArray[key];
  if (node == NULL) {
    return;
  }
  if (node->phoneNumber == phoneNumber) {
    free(node);
    hashTable->dataArray[key] = NULL;
  }
}

Giải quyết va chạm

Có hai cách giải quyết va chạm đó là phương pháp kết nối và phương pháp địa chỉ mở. Phương pháp kết nối lưu các giá trị vào một danh sách liên kết. Còn phương pháp địa chỉ mở thì các cặp vạ chạm khóa-giá trị được lưu trong bảng ở một chỗ khác. Một thuật toán sẽ tìm vị trí tiếp theo của của khóa va chạm này.

Trong ví dụ trên các khóa khi được băm ra sẽ có các giá trị khác nhau. Giờ ta sẽ giải quyết trường hợp va chạm với ví dụ trên khi thêm hai dữ liệu mới như sau:

Số điện thoại	Tên	Giá trị băm
124565	Tung	1
672922	Vuong	8
926506	Hoa	9
284657	Mai	10
228306	Linh	1

Có va chạm với số điện thoại 124565, tên Tung ở trên khi cùng giá trị băm là 1. Cách cài đặt giải quyết va chạm khi sử dụng danh sách liên kết như sau:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60


typedef struct Data {
  int phoneNumber;
  char name[10];
  struct Data* next;
} Data;

void addToHashTable(HashTable *hashTable, Data* data) {
  int key = data->phoneNumber % 11; // hàm băm
  Data* newData = malloc(sizeof(Data)); // tạo dữ liệu mới
  newData->phoneNumber = data->phoneNumber; // copy phoneNumber
  strcpy(newData->name, data->name); // copy name

  // tạo danh sách liên kết
  newData->next = hashTable->dataArray[key];
  hashTable->dataArray[key] = newData;
}

Data* findData(HashTable *hashTable, int phoneNumber) {
  int key = phoneNumber % 11; // hàm băm
  Data* data = hashTable->dataArray[key]; // lấy data

  // lặp qua danh sách liên kết
  while(data != NULL) {

    // nếu trùng phoneNumber thì return
    if (data->phoneNumber == phoneNumber) { 
      return data;
    }
    data = data->next;
  }
  return NULL;
}

void deleleData(HashTable* hashTable, int phoneNumber) {
  int key = phoneNumber % 11;
  Data* node = hashTable->dataArray[key];
  if (node == NULL) {
    return;
  }
  if (node->phoneNumber == phoneNumber) {
    free(node);
    hashTable->dataArray[key] = NULL;
    return;
  }

  Data* preNode = node;
  preNode = node;
  node = node->next;
  // lặp qua danh sách liên kết
  while(node != NULL) {
    // nếu trùng phoneNumber thì xóa phần tử đó
    if (node->phoneNumber == phoneNumber) { 
      preNode->next = node->next;
      free(node);
      return;
    }
    preNode = node;
    node = node->next;
  }
}

Trên đây là ví dụ để minh họa việc sử dụng hashmap. Trong thực tế chúng ta sẽ thường sử dụng hashmap qua các thư viện được viết sẵn.

Cấu trúc dữ liệu

Thuật toán sắp xếp