Hash là gì? Ứng dụng của hash

Bài viết này sẽ giải thích cho các bạn biết hàm băm là gì? Nó được sử dụng như thế nào và ứng dụng của nó nhé.

• Giải thuật tìm kiếm nhị phân (Binary Search)
• Duyệt cây trong cấu trúc dữ liệu và giải thuật
• Cây AVL trong cấu trúc dữ liệu và giải thuật

1. Hash là gì?

Hash là từ tiếng Anh, có nghĩa tiếng Việt là băm. Trong nấu ăn, để băm một cái gì đó có nghĩa là cắt và sau đó trộn nó. Chính từ đó chúng ta có món Hash brown - món khoai tây xắt sợi được rán hoặc chiên dùng cho bữa sáng ở Anh. Trong khoa học máy tính, hàm băm lấy đầu vào có độ dài và nội dung bất kỳ (ví dụ: chữ cái, số và ký hiệu) và sử dụng công thức toán học để cắt, trộn và tạo đầu ra có độ dài cụ thể.

Ví dụ: hãy nhìn giá trị dưới đây:

c017dcaadb04d44b6012b2a055786c77

Bạn có nhận ra nó? Đây được lấy từ 14 dòng thơ trong bài Sonnet 18 của Shakespeare bắt đầu từ "Shall I compare thee to a summer’s day?" và tạo một đầu ra chỉ có 32 ký tự.

Chúng ta có thể tạo hash của gần như mọi nội dung kỹ thuật số: tài liệu, hình ảnh, bài hát hoặc bất cứ thứ gì.

Bất kỳ nội dung kỹ thuật số nào ở mức thấp nhất chỉ là một chuỗi số 0 và 1. Mọi thứ đều có thể biểu diễn dưới dạng nhị phân. Ví dụ hello! trong nhị phân UTF-8 là 01001000 01100101 01101100 01101100 01101111 00100001. Đây là mã nhị phân mà hàm băm đang xáo trộn.

Có rất nhiều công thức toán học khác nhau mà bạn có thể sử dụng để tạo hash. Trên thực tế, không phải tất cả hash đều dài. Mỗi hàm băm kết hợp và trộn theo các cách khác nhau và do đó sẽ tạo ra các đầu ra khác nhau. Đối với giá trị băm trước đó sử dụng hàm băm được gọi là MD5 viết tắt của Message Digest. Một vài hàm băm tạo ra giá trị băm dài như SHA3–512 (Secure Hash Algorithm 3) tạo một hash dài 128 ký tự.

Khi sử dụng cùng một nội dung trên cùng một hàm băm, bạn sẽ nhận được cùng một đầu ra. Theo cách này, chuỗi 32 ký tự trên hoạt động hơi giống dấu vân tay kỹ thuật số của nội dung. Hãy xem điều gì xảy ra khi thay đổi một từ trong bài thơ Sonnet của Shakespeare (summer thành winter trong dòng đầu tiên).

Bản gốc: 017dcaadb04d44b6012b2a055786c77

Mới: ab7b6da7342ea2599198c3ba3e884b55

Chúng hoàn toàn khác nhau, phải không? Bạn không thể thấy bất kỳ kết nối nào, ngoài việc chuỗi đều là hệ thập lục phân (nghĩa là sử dụng 16 ký hiệu, 0-9 và a-f, một quá trình thường được sử dụng trong điện toán như một cách đơn giản để biểu diễn nhị phân). Giống như dấu vân tay con người là duy nhất, không ai giống ai, thậm chí một thay đổi nhỏ đối với một phần nội dung sẽ dẫn đến một hash hoàn toàn mới.

2. Ứng dụng của hash

Hash được sử dụng cho mật mã vì nó che dấu dữ liệu gốc với một giá trị khác. Hàm băm có thể được dùng để tạo một giá trị mà bạn chỉ có thể giải mã bằng cách tra cứu từ bảng băm. Bảng này có thể là một mảng, cơ sở dữ liệu hoặc cấu trúc dữ liệu. Một hàm băm mật mã tốt là không thể đảo ngược.

Các loại nén khác nhau, chẳng hạn như nén phương tiện và nén ảnh bị mất dữ liệu (lossy) có thể kết hợp hàm băm để giảm kích thước file. Bằng cách hash dữ liệu thành giá trị nhỏ hơn, file phương tiện có thể được nén thành các phần nhỏ hơn. Kiểu hash một chiều này không thể đảo ngược nhưng nó có thể tạo dữ liệu gần bằng dữ liệu gốc nhưng yêu cầu ít dung lượng đĩa hơn.

• Top phần mềm giải nén file và nén file tốt nhất hiện nay

Hash cũng được sử dụng để tạo checksum (giá trị tổng kiểm), xác nhận tính toàn vẹn của file. Checksum là giá trị nhỏ được tạo dựa trên các bit trong một file hoặc khối dữ liệu như image đĩa. Khi chức năng checksum chạy trên một bản sao của file (chẳng hạn như file được tải từ Internet), nó sẽ tạo ra giá trị băm giống như file gốc. Nếu file không tạo cùng một checksum, có nghĩa là file đã bị thay đổi.

Cuối cùng, hash được sử dụng để lập chỉ mục dữ liệu. Giá trị băm có thể được sử dụng để ánh xạ dữ liệu vào từng bucket trong một bảng băm. Mỗi bucket này có một ID duy nhất đóng vai trò là con trỏ tới dữ liệu gốc. Điều này tạo một chỉ mục nhỏ hơn nhiều so với dữ liệu gốc, cho phép giá trị được tìm kiếm và truy cập hiệu quả hơn.