Tóm Tắt
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.
