Cấu trúc dữ liệu bảng băm và ứng dụng của bảng băm

Trong bài viết này, ta sẽ cùng tìm hiểu về cấu trúc dữ liệu bảng băm. Ngoài ra, ta sẽ thực hiện triển khai ví dụ cho kiểu cấu trúc dữ liệu này bằng ngôn ngữ lập trình C.

Bảng băm hay Hash table là một cấu trúc dữ liệu và biểu diễn dữ liệu dưới dạng các cặp khóa và 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ỉ số cho các giá trị hay dữ liệu.

Dữ liệu được biểu diễn trong một cặp giá trị và khóa với sự trợ giúp của các khóa 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.

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 ta sẽ giả định rằng:

Các khóa là số nguyên nhỏ.
Số lượng khóa không quá lớn.
Không có 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à một tập hợp Universe U={0, 1,……, N-1}.

Mỗi vị trí của bảng địa chỉ trực tiếp là T[0...n-1] chứa một con trỏ đến phần tử tương ứng với dữ liệu.

Chỉ số của mảng T chính là khóa và nội dung của T là một con trỏ tới tập [khóa, phần tử]. Nếu không có phần tử nào được dành cho khóa thì nó được để là NULL.

Đôi khi, khóa cũng đồng thời đóng vai trò là dữ liệu.

Đoạn giả mã cho các thao tác có dạng như sau:

Hàm tìm kiếm địa chỉ trực tiếp(T, k)
  Trả về T[k]
Hàm chèn địa chỉ trực tiếp(T, x)
  Gán x cho T[x.key]
Hàm xóa địa chỉ trực tiếp(T, x)
  Gán giá trị NIL cho T[x.key]

Hàm tìm kiếm địa chỉ trực tiếp(T, k)

Trả về T[k]

Hàm chèn địa chỉ trực tiếp(T, x)

Gán x cho T[x.key]

Hàm xóa địa chỉ trực tiếp(T, x)

Gán giá trị NIL cho T[x.key]

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.

Cấu trúc dữ liệu bảng băm

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

Gọi h(x) là một hàm băm và k là 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ỉ số đượ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 lựa chọn. Tuy nhiên, không thể tạo ra tất cả các khóa duy nhất 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 xảy ra. Tuy nhiên, chúng ta sẽ sử dụng các kỹ thuật khác để giải quyết vấn đề về 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ỉ số và do đó kích thước của mảng cũng giảm.

Ví dụ: Nếu k = 9845648451321, thì 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ỉ số 9845648451321 cho mả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ỉ số cho nhiều phần tử, các phần tử này được lưu trữ trong cùng một chỉ số bằng cách sử dụng danh sách liên kết đôi.

Nếu j là vùng chứa nhiều phần tử, nó chứa một con trỏ đến phần đầu của danh sách các phần tử. Nếu không có phần tử nào, j sẽ chứa giá trị NIL.

Đoạn giả mã cho các thao tác như sau:

Hàm tìm kiếm bảng băm được xâu chuỗi(T, k)
  Trả về T[h(k)]
Hàm chèn vào bảng băm được xâu chuỗi(T, x)
  T[h(x.key)] = x //insert at the head
Hàm xóa khóa khỏi bảng băm được xâu chuỗi(T, x)
  T[h(x.key)] = NIL

Hàm tìm kiếm bảng băm được xâu chuỗi(T, k)

Trả về T[h(k)]

Hàm chèn vào bảng băm được xâu chuỗi(T, x)

T[h(x.key)] = x //insert at the head

Hàm xóa khóa khỏi bảng băm được xâu chuỗi(T, x)

T[h(x.key)] = NIL

Ví dụ: Triển khai bảng băm bằng ngôn ngữ lập trình C.

#include <stdio.h>
#include <stdlib.h>

struct space
{
  int key;
  int data;
};
struct space *arr;
int MAX = 10;
int size = 0;

int hash_func(int a)
{
  return (a % MAX);
}
int check_primeNumber(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 get_primeNumber(int n)
{
  if (n % 2 == 0)
  {
    n++;
  }
  while (!check_primeNumber(n))
  {
    n += 2;
  }
  return n;
}
void create()
{
  MAX = get_primeNumber(MAX);
  arr = (struct space *)malloc(MAX * sizeof(struct space));
  for (int i = 0; i < MAX; i++)
  {
    arr[i].key = 0;
    arr[i].data = 0;
  }
}

void add(int key, int data)
{
  int index = hash_func(key);
  if (arr[index].data == 0)
  {
    arr[index].key = key;
    arr[index].data = data;
    size++;
    printf("\nĐã được thêm\n");
  }
  else if (arr[index].key == key)
  {
    arr[index].data = data;
  }
  else
  {
    printf("\nXung đột xảy ra\n");
  }
}

void del(int key)
{
  int index = hash_func(key);
  if (arr[index].data == 0)
  {
    printf("\nKhông tồn tại\n");
  }
  else
  {
    arr[index].key = 0;
    arr[index].data = 0;
    size--;
    printf("\nĐã xóa\n");
  }
}
void print()
{
  int i;
  for (i = 0; i < MAX; i++)
  {
    if (arr[i].data == 0)
    {
      printf("\n a[%d]: / ", i);
    }
    else
    {
      printf("\nKhóa: %d dữ liệu a[%d]: %d \t", arr[i].key, i, arr[i].data);
    }
  }
}

int space_hashtable()
{
  return size;
}

int main()
{
  int inp, key, data, n;
  int c = 0;
  create();
  printf("\rCác thao tác với bảng băm\n");
  do
  {
    printf("1.Thêm phần tử"
         "\n2.Xóa phần tử"
         "\n3.Kiểm tra kích thước"
         "\n4.In giá trị"
         "\n\nMời bạn nhập: ");
    scanf("%d", &inp);
    switch (inp)
    {
    case 1:
      printf("Khóa: ");
      scanf("%d", &key);
      printf("Dữ liệu: ");
      scanf("%d", &data);
      add(key, data);
      break;

    case 2:
      printf("Nhập khóa:");
      scanf("%d", &key);
      del(key);
      break;

    case 3:
      n = space_hashtable();
      printf("Kích thước của bảng băm:%d\n", n);
      break;

    case 4:
      print();
      break;

    default:
      printf("Bạn đã nhập quá giá trị cho phép\n");
    }
    printf("\nBạn muốn tiếp tục không?(1/0): ");
    scanf("%d", &c);
  } while (c == 1);
  printf("\nKết thúc");
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

#include <stdio.h>

#include <stdlib.h>

struct space

{

int key;

int data;

};

struct space *arr;

int MAX = 10;

int size = 0;

int hash_func(int a)

{

return (a % MAX);

}

int check_primeNumber(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 get_primeNumber(int n)

{

if (n % 2 == 0)

{

n++;

}

while (!check_primeNumber(n))

{

n += 2;

}

return n;

}

void create()

{

MAX = get_primeNumber(MAX);

arr = (struct space *)malloc(MAX * sizeof(struct space));

for (int i = 0; i < MAX; i++)

{

arr[i].key = 0;

arr[i].data = 0;

}

void add(int key, int data)

{

int index = hash_func(key);

if (arr[index].data == 0)

{

arr[index].key = key;

arr[index].data = data;

size++;

printf("\nĐã được thêm\n");

}

else if (arr[index].key == key)

{

arr[index].data = data;

}

else

{

printf("\nXung đột xảy ra\n");

}

void del(int key)

{

int index = hash_func(key);

if (arr[index].data == 0)

{

printf("\nKhông tồn tại\n");

}

else

{

arr[index].key = 0;

arr[index].data = 0;

size--;

printf("\nĐã xóa\n");

}

void print()

{

int i;

for (i = 0; i < MAX; i++)

{

if (arr[i].data == 0)

{

printf("\n a[%d]: / ", i);

}

else

{

printf("\nKhóa: %d dữ liệu a[%d]: %d \t", arr[i].key, i, arr[i].data);

}

int space_hashtable()

{

return size;

}

int main()

{

int inp, key, data, n;

int c = 0;

create();

printf("\rCác thao tác với bảng băm\n");

{

printf("1.Thêm phần tử"

"\n2.Xóa phần tử"

"\n3.Kiểm tra kích thước"

"\n4.In giá trị"

"\n\nMời bạn nhập: ");

scanf("%d", &inp);

switch (inp)

{

case 1:

printf("Khóa: ");

scanf("%d", &key);

printf("Dữ liệu: ");

scanf("%d", &data);

add(key, data);

break;

case 2:

printf("Nhập khóa:");

scanf("%d", &key);

del(key);

break;

case 3:

n = space_hashtable();

printf("Kích thước của bảng băm:%d\n", n);

break;

case 4:

print();

break;

default:

printf("Bạn đã nhập quá giá trị cho phép\n");

}

printf("\nBạn muốn tiếp tục không?(1/0): ");

scanf("%d", &c);

} while (c == 1);

printf("\nKết thúc");

}

Kết quả:

Các thao tác với bảng băm
1.Thêm phần tử
2.Xóa phần tử
3.Kiểm tra kích thước
4.In giá trị

Mời bạn nhập: 1
Khóa: 2
Dữ liệu: 32

Đã được thêm
Bạn muốn tiếp tục không?(1/0): 0
Kết thúc

Các thao tác với bảng băm

1.Thêm phần tử

2.Xóa phần tử

3.Kiểm tra kích thước

4.In giá trị

Mời bạn nhập: 1

Khóa: 2

Dữ liệu: 32

Đã được thêm

Bạn muốn tiếp tục không?(1/0): 0

Kết thúc

Trên đây là khái niệm và ví dụ cơ bản về cấu trúc dữ liệu bảng băm. Hy vọng mọi người có thể áp dụng vào trong chương trình của mình. Nếu mọi người có đóng góp gì thêm thì có thể để các bình luận bên dưới bài viết này. Mọi người hãy tiếp tục theo dõi các bài tiếp theo và cập nhật các bài mới nhất trên tek4 nhé!

P/s: Cảm ơn mọi người!

Bài trước: Cấu trúc dữ liệu hàng đợi Deque

Bài tiếp theo: Cấu trúc dữ liệu cây và ứng dụng

5 1 vote

Article Rating