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

<p style="text-align: justify;">Trong b&agrave;i viết n&agrave;y, ta sẽ c&ugrave;ng t&igrave;m hiểu về cấu tr&uacute;c dữ liệu bảng băm. Ngo&agrave;i ra, ta sẽ thực hiện triển khai v&iacute; dụ cho kiểu cấu tr&uacute;c dữ liệu n&agrave;y bằng ng&ocirc;n ngữ lập tr&igrave;nh C.</p> <p style="text-align: justify;">Bảng băm hay Hash table l&agrave; một cấu tr&uacute;c dữ liệu v&agrave; biểu diễn dữ liệu dưới dạng c&aacute;c cặp kh&oacute;a v&agrave; gi&aacute; trị. Mỗi kh&oacute;a được &aacute;nh xạ tới một gi&aacute; trị trong bảng băm. C&aacute;c kh&oacute;a được sử dụng để lập chỉ số cho c&aacute;c gi&aacute; trị hay dữ liệu.</p> <p style="text-align: justify;">Dữ liệu được biểu diễn trong một cặp gi&aacute; trị v&agrave; kh&oacute;a với sự trợ gi&uacute;p của c&aacute;c kh&oacute;a như trong h&igrave;nh b&ecirc;n dưới. Mỗi dữ liệu được li&ecirc;n kết với một kh&oacute;a. Kh&oacute;a l&agrave; một số nguy&ecirc;n trỏ đến dữ liệu.</p> <p style="text-align: justify;"><img style="width: 100%;" src="../../../public_files/bcc171dd-1188-4786-9ce1-f50af050f5a9" alt="bang-bam" /></p> <h2 style="text-align: justify;">1. Bảng địa chỉ trực tiếp</h2> <p style="text-align: justify;">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&ocirc;ng phải l&agrave; vấn đề đối với chương tr&igrave;nh. Ở đ&acirc;y, ch&uacute;ng ta sẽ giả định rằng:</p> <ul style="text-align: justify;"> <li>C&aacute;c kh&oacute;a l&agrave; số nguy&ecirc;n nhỏ.</li> <li>Số lượng kh&oacute;a kh&ocirc;ng qu&aacute; lớn.</li> <li>Kh&ocirc;ng c&oacute; dữ liệu n&agrave;o c&oacute; c&ugrave;ng một kh&oacute;a.</li> </ul> <p style="text-align: justify;">Một nh&oacute;m c&aacute;c số nguy&ecirc;n được gọi l&agrave; một tập hợp Universe <span class="lang:default decode:true crayon-inline">U={0, 1,&hellip;&hellip;, N-1}</span>.</p> <p style="text-align: justify;">Mỗi vị tr&iacute; của bảng địa chỉ trực tiếp l&agrave; <span class="lang:default decode:true crayon-inline">T[0...n-1]</span>&nbsp;chứa một con trỏ đến phần tử tương ứng với dữ liệu.</p> <p style="text-align: justify;">Chỉ số của mảng T ch&iacute;nh l&agrave; kh&oacute;a v&agrave; nội dung của T l&agrave; một con trỏ tới tập <span class="lang:default decode:true crayon-inline">[kh&oacute;a, phần tử]</span>. Nếu kh&ocirc;ng c&oacute; phần tử n&agrave;o được d&agrave;nh cho kh&oacute;a th&igrave; n&oacute; được để l&agrave; NULL.</p> <p style="text-align: justify;"><img style="width: 100%;" src="../../../public_files/c939e064-e95c-4cb6-8f8c-4dc6b8741d2d" alt="bang-bam-2" /></p> <p style="text-align: justify;">Đ&ocirc;i khi, kh&oacute;a cũng đồng thời đ&oacute;ng vai tr&ograve; l&agrave; dữ liệu.</p> <p style="text-align: justify;">Đoạn giả m&atilde; cho c&aacute;c thao t&aacute;c c&oacute; dạng như sau:</p> <pre class="language-markup"><code>H&agrave;m t&igrave;m kiếm địa chỉ trực tiếp(T, k) Trả về T[k] H&agrave;m ch&egrave;n địa chỉ trực tiếp(T, x) G&aacute;n x cho T[x.key] H&agrave;m x&oacute;a địa chỉ trực tiếp(T, x) G&aacute;n gi&aacute; trị NIL cho T[x.key]</code></pre> <h3 style="text-align: justify;">Hạn chế của bảng địa chỉ trực tiếp</h3> <ul style="text-align: justify;"> <li>Gi&aacute; trị của kh&oacute;a phải nhỏ.</li> <li>Số lượng kh&oacute;a phải đủ nhỏ để n&oacute; kh&ocirc;ng vượt qua giới hạn k&iacute;ch thước của một mảng.</li> </ul> <h2 style="text-align: justify;">2. Cấu tr&uacute;c dữ liệu bảng băm</h2> <p style="text-align: justify;">Trong bảng băm, c&aacute;c kh&oacute;a được xử l&yacute; để tạo ra một chỉ số mới &aacute;nh xạ đến phần tử được y&ecirc;u cầu. Qu&aacute; tr&igrave;nh n&agrave;y được gọi l&agrave; băm.</p> <p style="text-align: justify;">Gọi <span class="lang:default decode:true crayon-inline ">h(x)</span> l&agrave; một h&agrave;m băm v&agrave; <span class="lang:default decode:true crayon-inline">k</span>&nbsp;l&agrave; một kh&oacute;a.</p> <p style="text-align: justify;"><span class="lang:default decode:true crayon-inline">h(k)</span>&nbsp;được t&iacute;nh to&aacute;n v&agrave; n&oacute; được sử dụng l&agrave;m chỉ số cho phần tử.</p> <p style="text-align: justify;"><img style="width: 100%;" src="../../../public_files/3de59a59-3ba2-43cc-8866-92be12b34634" alt="bang-bam-3" /></p> <h3 style="text-align: justify;">Hạn chế của bảng băm</h3> <p style="text-align: justify;">Nếu c&ugrave;ng một chỉ số được tạo ra bởi h&agrave;m băm cho nhiều kh&oacute;a th&igrave; xung đột sẽ ph&aacute;t sinh. T&igrave;nh huống n&agrave;y được gọi l&agrave; va chạm.</p> <p style="text-align: justify;">Để tr&aacute;nh điều n&agrave;y, một h&agrave;m băm ph&ugrave; hợp được lựa chọn. Tuy nhi&ecirc;n, kh&ocirc;ng thể tạo ra tất cả c&aacute;c kh&oacute;a duy nhất v&igrave; <span class="lang:default decode:true crayon-inline">|U|&gt; m</span>. Do đ&oacute;, một h&agrave;m băm tốt c&oacute; thể kh&ocirc;ng ngăn chặn ho&agrave;n to&agrave;n c&aacute;c va chạm nhưng n&oacute; c&oacute; thể l&agrave;m giảm số lượng c&aacute;c va chạm xảy ra. Tuy nhi&ecirc;n, ch&uacute;ng ta sẽ sử dụng c&aacute;c kỹ thuật kh&aacute;c để giải quyết vấn đề về va chạm.</p> <h3 style="text-align: justify;">Ưu điểm của bảng băm so với bảng địa chỉ trực tiếp</h3> <p style="text-align: justify;">C&aacute;c vấn đề ch&iacute;nh với bảng địa chỉ trực tiếp l&agrave; k&iacute;ch thước của mảng v&agrave; gi&aacute; trị c&oacute; thể lớn của một kh&oacute;a. H&agrave;m băm l&agrave;m giảm phạm vi của chỉ số v&agrave; do đ&oacute; k&iacute;ch thước của mảng cũng giảm.</p> <p style="text-align: justify;">V&iacute; dụ: Nếu k = 9845648451321, th&igrave; h(k) = 11 (bằng c&aacute;ch sử dụng một số h&agrave;m băm). Điều n&agrave;y gi&uacute;p tiết kiệm bộ nhớ bị l&atilde;ng ph&iacute; trong khi cung cấp chỉ số 9845648451321 cho mảng</p> <h3 style="text-align: justify;">Giải quyết va chạm bằng c&aacute;ch x&acirc;u chuỗi</h3> <p style="text-align: justify;">Trong kỹ thuật n&agrave;y, nếu một h&agrave;m băm tạo ra c&ugrave;ng một chỉ số cho nhiều phần tử, c&aacute;c phần tử n&agrave;y được lưu trữ trong c&ugrave;ng một chỉ số bằng c&aacute;ch sử dụng danh s&aacute;ch li&ecirc;n kết đ&ocirc;i.</p> <p style="text-align: justify;">Nếu j l&agrave; v&ugrave;ng chứa nhiều phần tử, n&oacute; chứa một con trỏ đến phần đầu của danh s&aacute;ch c&aacute;c phần tử. Nếu kh&ocirc;ng c&oacute; phần tử n&agrave;o, j sẽ chứa gi&aacute; trị NIL.</p> <p style="text-align: justify;"><img style="width: 100%;" src="../../../public_files/af21e794-981c-439f-815a-b241f8122b99" alt="bang-bam-4" /></p> <p style="text-align: justify;">Đoạn giả m&atilde; cho c&aacute;c thao t&aacute;c như sau:</p> <pre class="language-markup"><code>H&agrave;m t&igrave;m kiếm bảng băm được x&acirc;u chuỗi(T, k) Trả về T[h(k)] H&agrave;m ch&egrave;n v&agrave;o bảng băm được x&acirc;u chuỗi(T, x) T[h(x.key)] = x //insert at the head H&agrave;m x&oacute;a kh&oacute;a khỏi bảng băm được x&acirc;u chuỗi(T, x) T[h(x.key)] = NIL</code></pre> <p style="text-align: justify;">V&iacute; dụ: Triển khai bảng băm bằng ng&ocirc;n ngữ lập tr&igrave;nh C.</p> <pre class="language-c"><code>#include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; 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 &lt; 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 &lt; 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Đ&atilde; được th&ecirc;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&ocirc;ng tồn tại\n"); } else { arr[index].key = 0; arr[index].data = 0; size--; printf("\nĐ&atilde; x&oacute;a\n"); } } void print() { int i; for (i = 0; i &lt; MAX; i++) { if (arr[i].data == 0) { printf("\n a[%d]: / ", i); } else { printf("\nKh&oacute;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&aacute;c thao t&aacute;c với bảng băm\n"); do { printf("1.Th&ecirc;m phần tử" "\n2.X&oacute;a phần tử" "\n3.Kiểm tra k&iacute;ch thước" "\n4.In gi&aacute; trị" "\n\nMời bạn nhập: "); scanf("%d", &amp;inp); switch (inp) { case 1: printf("Kh&oacute;a: "); scanf("%d", &amp;key); printf("Dữ liệu: "); scanf("%d", &amp;data); add(key, data); break; case 2: printf("Nhập kh&oacute;a:"); scanf("%d", &amp;key); del(key); break; case 3: n = space_hashtable(); printf("K&iacute;ch thước của bảng băm:%d\n", n); break; case 4: print(); break; default: printf("Bạn đ&atilde; nhập qu&aacute; gi&aacute; trị cho ph&eacute;p\n"); } printf("\nBạn muốn tiếp tục kh&ocirc;ng?(1/0): "); scanf("%d", &amp;c); } while (c == 1); printf("\nKết th&uacute;c"); }</code></pre> <p style="text-align: justify;">Kết quả:</p> <pre class="language-markup"><code>C&aacute;c thao t&aacute;c với bảng băm 1.Th&ecirc;m phần tử 2.X&oacute;a phần tử 3.Kiểm tra k&iacute;ch thước 4.In gi&aacute; trị Mời bạn nhập: 1 Kh&oacute;a: 2 Dữ liệu: 32 Đ&atilde; được th&ecirc;m Bạn muốn tiếp tục kh&ocirc;ng?(1/0): 0 Kết th&uacute;c</code></pre> <p style="text-align: justify;">Tr&ecirc;n đ&acirc;y l&agrave; kh&aacute;i niệm v&agrave; v&iacute; dụ cơ bản về cấu tr&uacute;c dữ liệu bảng băm. Hy vọng mọi người c&oacute; thể &aacute;p dụng v&agrave;o trong chương tr&igrave;nh của m&igrave;nh. Nếu mọi người c&oacute; đ&oacute;ng g&oacute;p g&igrave; th&ecirc;m th&igrave; c&oacute; thể để c&aacute;c b&igrave;nh luận b&ecirc;n dưới b&agrave;i viết n&agrave;y. Mọi người h&atilde;y tiếp tục theo d&otilde;i c&aacute;c b&agrave;i tiếp theo v&agrave; cập nhật c&aacute;c b&agrave;i mới nhất tr&ecirc;n <a href="http://tek4.vn">tek4</a> nh&eacute;!</p>