<h1 style="text-align: justify;">Phương ph&aacute;p băm l&agrave; g&igrave;?</h1>
<p style="text-align: justify;">Phương ph&aacute;p băm l&agrave; một phương ph&aacute;p được &aacute;p dụng trong hệ quản trị cơ sở dữ liệu để t&igrave;m kiếm trực tiếp vị tr&iacute; của dữ liệu hay một bản ghi mong muốn tr&ecirc;n đĩa m&agrave; kh&ocirc;ng cần sử dụng cấu tr&uacute;c chỉ mục (Index). Phương ph&aacute;p băm được sử dụng phổ biến để đ&aacute;nh số chỉ mục v&agrave; truy xuất c&aacute;c dữ liệu trong cơ sở dữ liệu v&igrave; việc t&igrave;m kiếm sẽ nhanh hơn bằng c&aacute;ch sử dụng một kh&oacute;a được băm với độ d&agrave;i ngắn hơn thay v&igrave; sử dụng gi&aacute; trị gốc ban đầu của kh&oacute;a đ&oacute;. Dữ liệu được lưu trữ dưới dạng c&aacute;c khối dữ liệu m&agrave; c&oacute; địa chỉ được tạo ra bởi h&agrave;m băm trong nơi lưu trữ bộ nhớ của c&aacute;c bản ghi v&agrave; nơi lưu trữ n&agrave;y được gọi l&agrave; một khối dữ liệu.</p>
<h1 style="text-align: justify;">Tại sao cần sử dụng phương ph&aacute;p băm?</h1>
<p style="text-align: justify;">Dưới đ&acirc;y l&agrave; c&aacute;c trường hợp cần &aacute;p dụng phương ph&aacute;p băm:</p>
<ul style="text-align: justify;">
<li>Đối với một cấu tr&uacute;c cơ sở dữ liệu khổng lồ, thật kh&oacute; để t&igrave;m kiếm tất cả c&aacute;c gi&aacute; trị chỉ mục th&ocirc;ng qua tất cả c&aacute;c cấp của n&oacute; v&agrave; sau đ&oacute; mới đến được khối dữ liệu đ&iacute;ch để c&oacute; được dữ liệu mong muốn.</li>
<li>Phương ph&aacute;p băm được sử dụng để đ&aacute;nh số chỉ mục v&agrave; truy xuất c&aacute;c mục trong cơ sở dữ liệu v&igrave; việc t&igrave;m kiếm sẽ diễn ra nhanh hơn.</li>
<li>Phương ph&aacute;p băm sẽ rất l&yacute; tưởng để t&iacute;nh to&aacute;n vị tr&iacute; trực tiếp của một bản ghi dữ liệu tr&ecirc;n đĩa m&agrave; kh&ocirc;ng cần sử dụng cấu tr&uacute;c chỉ mục.</li>
</ul>
<h1 style="text-align: justify;">C&aacute;c thuật ngữ quan trọng trong phương ph&aacute;p băm</h1>
<p style="text-align: justify;">V&ugrave;ng nhớ dữ liệu (Data bucket) - Nh&oacute;m dữ liệu l&agrave; vị tr&iacute; bộ nhớ nơi c&aacute;c bản ghi được lưu trữ. V&agrave; n&oacute; c&ograve;n được gọi l&agrave; đơn vị lưu trữ.</p>
<p style="text-align: justify;">Kh&oacute;a (Key): Kh&oacute;a l&agrave; một thuộc t&iacute;nh hoặc tập hợp c&aacute;c thuộc t&iacute;nh gi&uacute;p x&aacute;c định duy nhất một h&agrave;ng trong một bảng. Đồng thời, kh&oacute;a cũng c&oacute; vai tr&ograve; trong việc tạo mối li&ecirc;n hệ giữa c&aacute;c bảng.</p>
<p style="text-align: justify;">H&agrave;m băm (Hash function): Một h&agrave;m băm, l&agrave; một h&agrave;m &aacute;nh xạ tất cả c&aacute;c tập hợp kh&oacute;a t&igrave;m kiếm trỏ đến địa chỉ nơi c&aacute;c bản ghi được lưu trữ.</p>
<p style="text-align: justify;">T&igrave;m kiếm tuyến t&iacute;nh (Linear Probing): Trong phương ph&aacute;p n&agrave;y, v&ugrave;ng nhớ dữ liệu c&oacute; sẵn tiếp theo sẽ được sử dụng để nhập bản ghi mới, thay v&igrave; ghi đ&egrave; l&ecirc;n bản ghi cũ.</p>
<p style="text-align: justify;">T&igrave;m kiếm cấp số mũ bậc hai (Quadratic probing): N&oacute; gi&uacute;p x&aacute;c định địa chỉ của v&ugrave;ng nhớ dữ liệu mới. N&oacute; sẽ th&ecirc;m bằng c&aacute;ch cộng th&ecirc;m đầu ra sau đ&oacute; của đa thức bậc hai với gi&aacute; trị được t&iacute;nh bằng ph&eacute;p t&iacute;nh ban đầu. Giả sử ta c&oacute; h&agrave;m băm h(x) với x l&agrave; gi&aacute; trị kh&oacute;a t&igrave;m kiếm. Nếu h(x) trả về địa chỉ mới đ&atilde; bị chiếm dụng th&igrave; n&oacute; sẽ t&iacute;nh (h(x) + 1*1).</p>
<p style="text-align: justify;">Chỉ mục băm (Hash index): N&oacute; l&agrave; một địa chỉ của khối dữ liệu. Một h&agrave;m băm c&oacute; thể l&agrave; một h&agrave;m to&aacute;n học đơn giản, hoặc thậm ch&iacute; l&agrave; một h&agrave;m phức tạp.</p>
<p style="text-align: justify;">Phương ph&aacute;p băm k&eacute;p (Double Hashing): L&agrave; một phương ph&aacute;p lập tr&igrave;nh m&aacute;y t&iacute;nh được sử dụng trong c&aacute;c bảng băm để giải quyết c&aacute;c xung đột.</p>
<p style="text-align: justify;">Tr&agrave;n v&ugrave;ng nhớ dữ liệu (Bucket overflow): Trạng th&aacute;i n&agrave;y c&ograve;n được gọi l&agrave; va chạm. Khi m&agrave; v&ugrave;ng nhớ kh&ocirc;ng c&ograve;n chỗ để chứa th&ecirc;m một bản ghi hoặc dữ liệu mới.</p>
<h1 style="text-align: justify;">Chủ yếu c&oacute; hai loại phương ph&aacute;p băm</h1>
<ol style="text-align: justify;">
<li>Phương ph&aacute;p băm tĩnh</li>
<li>Phương ph&aacute;p băm động</li>
</ol>
<h2 style="text-align: justify;">Phương ph&aacute;p băm tĩnh</h2>
<p style="text-align: justify;">Trong băm tĩnh, địa chỉ của một v&ugrave;ng nhớ dữ liệu khi được t&iacute;nh to&aacute;n th&igrave; sẽ lu&ocirc;n giống nhau. Do đ&oacute;, nếu tạo địa chỉ Student_ID = 10 bằng c&aacute;ch sử dụng h&agrave;m băm mod (3), địa chỉ v&ugrave;ng nhớ dữ liệu sẽ lu&ocirc;n l&agrave; 1. V&igrave; vậy, bạn sẽ kh&ocirc;ng thấy bất kỳ thay đổi n&agrave;o trong địa chỉ của v&ugrave;ng nhớ. Do đ&oacute;, trong phương ph&aacute;p băm tĩnh n&agrave;y, số lượng v&ugrave;ng nhớ dữ liệu trong bộ nhớ l&agrave; lu&ocirc;n kh&ocirc;ng đổi.</p>
<p style="text-align: justify;">V&iacute; dụ: C&oacute; 2 bảng chứa gi&aacute; trị kh&oacute;a v&agrave; một v&ugrave;ng nhớ dữ liệu chứa c&aacute;c dữ liệu tương ứng với c&aacute;c gi&aacute; trị kh&oacute;a đ&oacute;. Với gi&aacute; trị kh&oacute;a t&igrave;m kiếm đầu v&agrave;o l&agrave; 100, sử dụng phương ph&aacute;p băm cho gi&aacute; trị n&agrave;y th&igrave; ta được một gi&aacute; trị mới v&agrave; gi&aacute; trị mới n&agrave;y sẽ trỏ tới v&ugrave;ng nhớ dữ liệu A v&agrave; tương tự như vậy th&igrave; 101 sẽ được băm v&agrave; gi&aacute; trị mới sau khi băm 101 sẽ trỏ tới B v&agrave; cứ như vậy cho tới hết.</p>
<table style="height: 61px;" width="817">
<tbody>
<tr>
<td width="125">C&aacute;c gi&aacute; trị kh&oacute;a t&igrave;m kiếm</td>
<td width="125">100</td>
<td width="125">101</td>
<td width="125">102</td>
<td width="125">103</td>
</tr>
</tbody>
</table>
<table style="height: 34px;" width="819">
<tbody>
<tr>
<td width="125">H&agrave;m băm</td>
<td width="125">A</td>
<td width="125">B</td>
<td width="125">C</td>
<td width="125">D</td>
</tr>
</tbody>
</table>
<h2 style="text-align: justify;">C&aacute;c h&agrave;m băm tĩnh</h2>
<p style="text-align: justify;">Ch&egrave;n bản ghi: Khi một bản ghi mới y&ecirc;u cầu được ch&egrave;n v&agrave;o bảng, bạn c&oacute; thể tạo địa chỉ cho bản ghi mới bằng c&aacute;ch sử dụng kh&oacute;a băm của n&oacute;. Khi địa chỉ được sinh ra, bản ghi sẽ tự động được lưu trữ ở vị tr&iacute; đ&oacute;.</p>
<p style="text-align: justify;">T&igrave;m kiếm: Khi bạn cần truy xuất bản ghi, một h&agrave;m băm tương tự sẽ gi&uacute;p truy xuất địa chỉ của v&ugrave;ng nhớ dữ liệu, nơi dữ liệu hay bản ghi được lưu trữ.</p>
<p style="text-align: justify;">X&oacute;a bản ghi: Sử dụng h&agrave;m băm v&agrave; bạn c&oacute; thể lấy được bản ghi hoặc dữ liệu m&agrave; bạn muốn x&oacute;a. Sau đ&oacute;, bạn c&oacute; thể x&oacute;a địa chỉ của bản ghi đ&oacute; trong bộ nhớ.</p>
<p style="text-align: justify;">Phương ph&aacute;p băm tĩnh được chia th&agrave;nh 2 loại:</p>
<ol style="text-align: justify;">
<li>Phương ph&aacute;p băm mở</li>
<li>Phương ph&aacute;p băm đ&oacute;ng</li>
</ol>
<h3 style="text-align: justify;">Phương ph&aacute;p băm mở</h3>
<p style="text-align: justify;">Trong phương ph&aacute;p băm mở, thay v&igrave; ghi đ&egrave; v&ugrave;ng nhớ dữ liệu cũ, th&igrave; v&ugrave;ng nhớ dữ liệu tiếp theo được sử dụng để nhập bản ghi mới. Phương ph&aacute;p n&agrave;y c&ograve;n được gọi l&agrave; phương ph&aacute;p d&ograve; tuyến t&iacute;nh (Linear probing).</p>
<p style="text-align: justify;">V&iacute; dụ, A2 l&agrave; một bản ghi mới m&agrave; bạn muốn ch&egrave;n. H&agrave;m băm tạo ra địa chỉ l&agrave; 222. Nhưng n&oacute; đ&atilde; bị chiếm bởi một bản ghi kh&aacute;c. V&agrave; hệ thống sẽ t&igrave;m kiếm v&ugrave;ng nhớ dữ liệu tiếp theo l&agrave; 501 v&agrave; sẽ g&aacute;n A2 với địa chỉ n&agrave;y.</p>
<p><img style="width: 700px; display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/9f80023f-0424-47f4-9106-5a96ba31380c" alt="Capture-89" /></p>
<p style="text-align: justify;">&nbsp;</p>
<h3 style="text-align: justify;">Phương ph&aacute;p băm đ&oacute;ng</h3>
<p style="text-align: justify;">Khi c&aacute;c v&ugrave;ng nhớ dữ liệu đầy, một v&ugrave;ng nhớ mới sẽ được cấp ph&aacute;t cho c&ugrave;ng một h&agrave;m băm v&agrave; kết quả sẽ được li&ecirc;n kết sau v&ugrave;ng nhớ trước đ&oacute;.</p>
<p><img style="width: 700px; display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/15cdd252-c25b-4871-b6e4-c6043cbd72e0" alt="Capture-88" /></p>
<h2 style="text-align: justify;">Phương ph&aacute;p băm động</h2>
<p style="text-align: justify;">Vấn đề với phương ph&aacute;p băm tĩnh l&agrave; n&oacute; sẽ kh&ocirc;ng mở rộng hoặc thu nhỏ theo một c&aacute;ch linh hoạt khi k&iacute;ch thước của cơ sở dữ liệu tăng l&ecirc;n hoặc thu hẹp lại. Phương ph&aacute;p băm động cung cấp một cơ chế trong đ&oacute; c&aacute;c v&ugrave;ng nhớ dữ liệu được th&ecirc;m v&agrave;o v&agrave; x&oacute;a đi theo một c&aacute;ch linh hoạt. Phương ph&aacute;p băm động c&ograve;n được gọi l&agrave; phương ph&aacute;p băm mở rộng. H&agrave;m băm trong phương ph&aacute;p n&agrave;y được tạo ra để tạo ra một số lượng lớn c&aacute;c gi&aacute; trị.</p>
<h1 style="text-align: justify;">Lập chỉ mục theo thứ tự so với phương ph&aacute;p băm</h1>
<table style="height: 684px;" width="805">
<tbody>
<tr>
<td width="208">C&aacute;c tham số</td>
<td width="208">Lập chỉ mục c&oacute; thứ tự</td>
<td width="208">Phương ph&aacute;p băm</td>
</tr>
<tr>
<td width="208">Lưu trữ địa chỉ</td>
<td width="208">Địa chỉ trong bộ nhớ được sắp xếp theo một gi&aacute; trị kh&oacute;a được gọi l&agrave; kh&oacute;a ch&iacute;nh</td>
<td width="208">Địa chỉ lu&ocirc;n được tạo bằng c&aacute;ch sử dụng h&agrave;m băm l&ecirc;n gi&aacute; trị kh&oacute;a.</td>
</tr>
<tr>
<td width="208">Hiệu suất</td>
<td width="208">N&oacute; c&oacute; thể giảm khi dữ liệu tăng l&ecirc;n trong tệp băm. V&igrave; n&oacute; lưu trữ dữ liệu được sắp xếp, do vậy khi c&oacute; bất kỳ thao t&aacute;c n&agrave;o như ch&egrave;n, x&oacute;a hoặc cập nhật được thực hiện sẽ l&agrave;m giảm hiệu suất.</td>
<td width="208">Hiệu suất được cải thiện tốt hơn khi c&oacute; sự li&ecirc;n tục th&ecirc;m v&agrave; x&oacute;a dữ liệu. Tuy nhi&ecirc;n, đối với cơ sở dữ liệu lớn, th&igrave; việc tổ chức tệp băm v&agrave; việc duy tr&igrave; l&agrave; sẽ tốn k&eacute;m.</td>
</tr>
<tr>
<td width="208">Mục đ&iacute;ch sử dụng</td>
<td width="208">Ph&ugrave; hợp với việc truy xuất một tập c&aacute;c dữ liệu trong cho một phạm vi cụ thể</td>
<td width="208">Ph&ugrave; hợp cho việc truy xuất một bản ghi cụ thể dựa tr&ecirc;n kh&oacute;a t&igrave;m kiếm. Tuy nhi&ecirc;n, n&oacute; sẽ chỉ hoạt động tốt khi h&agrave;m băm được dựa tr&ecirc;n kh&oacute;a t&igrave;m kiếm.</td>
</tr>
<tr>
<td width="208">Quản l&yacute; bộ nhớ</td>
<td width="208">Sẽ c&oacute; nhiều v&ugrave;ng nhớ dữ liệu kh&ocirc;ng sử dụng khi c&oacute; c&aacute;c thao t&aacute;c như x&oacute;a hoặc cập nhật bản ghi. C&aacute;c v&ugrave;ng nhớ dữ liệu bị x&oacute;a hoặc bị thay đổi th&igrave; kh&ocirc;ng thể giải ph&oacute;ng để d&ugrave;ng lại. Đ&oacute; l&agrave; l&yacute; do tại sao cần phải duy tr&igrave; bộ nhớ thường xuy&ecirc;n.</td>
<td width="208">Bộ nhớ lu&ocirc;n được quản l&yacute;. T&igrave;nh trạng tr&agrave;n v&ugrave;ng nhớ dữ liệu cũng được xử l&yacute; tốt để mở rộng phương ph&aacute;p băm tĩnh.</td>
</tr>
</tbody>
</table>
<h1 style="text-align: justify;">Va chạm gi&aacute; trị băm</h1>
<p style="text-align: justify;">Va chạm gi&aacute; trị băm l&agrave; trạng th&aacute;i khi c&aacute;c kết quả băm từ hai hoặc nhiều dữ liệu trong tập dữ liệu, &aacute;nh xạ v&agrave;o c&ugrave;ng một vị tr&iacute; trong bảng băm. V&iacute; dụ được m&ocirc; tả trong h&igrave;nh b&ecirc;n dưới.</p>
<p><img style="width: 700px; display: block; margin-left: auto; margin-right: auto;" src="https://tek4.vn/public_files/07414227-1827-452c-ac7f-bc30c343900e" alt="Capture-92" /></p>
<h2 style="text-align: justify;">L&agrave;m thế n&agrave;o để giải quyết va chạm gi&aacute; trị băm?</h2>
<ul style="text-align: justify;">
<li>Thực hiện băm lại: Phương ph&aacute;p n&agrave;y được &aacute;p dụng li&ecirc;n tục cho đến khi t&igrave;m thấy một v&ugrave;ng nhớ mới, nơi c&oacute; thể đặt cho một bản ghi.</li>
<li>Li&ecirc;n kết chuỗi: Phương thức n&agrave;y x&acirc;y dựng một danh s&aacute;ch li&ecirc;n kết c&aacute;c bản ghi m&agrave; kh&oacute;a của ch&uacute;ng sau khi băm th&igrave; cho ra c&ugrave;ng một gi&aacute; trị.</li>
</ul>
<h1 style="text-align: justify;">T&oacute;m tắt</h1>
<ul style="text-align: justify;">
<li>Trong DBMS, phương ph&aacute;p băm l&agrave; một kỹ thuật t&igrave;m kiếm trực tiếp vị tr&iacute; của dữ liệu mong muốn tr&ecirc;n đĩa m&agrave; kh&ocirc;ng cần sử dụng cấu tr&uacute;c chỉ mục.</li>
<li>Phương thức băm được sử dụng để lập chỉ mục v&agrave; truy xuất c&aacute;c mục trong cơ sở dữ liệu nhanh hơn.</li>
<li>C&aacute;c thuật ngữ quan trọng: V&ugrave;ng nhớ dữ liệu, Kh&oacute;a, H&agrave;m băm, T&igrave;m kiếm tuyến t&iacute;nh, T&igrave;m kiếm cấp số mũ bậc hai, Chỉ mục băm, Băm k&eacute;p, Tr&agrave;n v&ugrave;ng nhớ dữ liệu.</li>
<li>Hai loại phương ph&aacute;p băm l&agrave;: Băm tĩnh v&agrave; Băm động.</li>
<li>Xung đột băm l&agrave; trạng th&aacute;i khi kết quả băm từ hai hoặc nhiều dữ liệu trong tập dữ liệu &aacute;nh xạ c&ugrave;ng một vị tr&iacute; trong bảng băm. V&agrave; c&oacute; 2 phương ph&aacute;p giải quyết cho xung đột băm l&agrave; li&ecirc;n kết chuỗi v&agrave; thực hiện băm lại.</li>
</ul>
<p style="text-align: justify;">P/s: Đến đ&acirc;y l&agrave; kết th&uacute;c b&agrave;i viết n&agrave;y, mong mọi người lu&ocirc;n ủng hộ cho tek4 nh&eacute;! Cảm ơn mọi người.</p>

Admin

Phương pháp băm trong hệ quản trị cơ sở dữ liệu – DBMS Hashing

Cùng tác giả

Admin

Có liên quan