Khái niệm hàm băm

5.1 Định nghĩa hàm băm và ứng dụng của nó

Hàm băm là một hàm nhận đầu vào (hoặc khóa) và trả về kích thước bit cố định, thường được gọi là hash hoặc giá trị băm. Mục đích chính của hàm băm là phân phối dữ liệu hiệu quả trong bảng băm để đảm bảo truy cập nhanh vào các phần tử.

Ứng dụng:

• Bảng băm: Được sử dụng để triển khai mảng kết hợp (dict trong Python), đảm bảo truy cập nhanh vào dữ liệu qua khóa.
• Kiểm tra toàn vẹn dữ liệu: Các hàm băm được sử dụng để kiểm tra toàn vẹn của tệp và dữ liệu (ví dụ, thuật toán MD5, SHA-1, SHA-256).
• Mật mã học: Các hàm băm được sử dụng trong các thuật toán mã hóa và tạo chữ ký số.
• Công cụ tìm kiếm: Được sử dụng để lập chỉ mục và tìm kiếm thông tin nhanh chóng.
• Quản lý bộ nhớ đệm: Được sử dụng để tổ chức bộ nhớ đệm, giúp tìm dữ liệu nhanh chóng.

Ví dụ ứng dụng hàm băm trong Python:

# Ví dụ sử dụng hàm băm trong Python cho bảng băm (dict)
data = {"apple": 1, "banana": 2, "cherry": 3}

# Lấy giá trị băm của khóa
key = "banana"
hash_value = hash(key)

print(f"Giá trị băm cho khóa '{key}': {hash_value}")

5.2 Tương tự trong đời thực

Bằng cách sử dụng hàm băm, bạn có thể chia một nhóm lớn các đối tượng thành các nhóm gần bằng nhau. Hơn thế nữa, nếu bạn tiếp tục thêm các đối tượng mới, chúng sẽ tiếp tục được phân phối đồng đều trong các nhóm.

Giả sử bạn có 1000 người và bạn cần phân họ vào 30 nhóm. Đây là cách bạn có thể làm điều này.

Cách 1. Theo chữ cái đầu tiên của tên.

Nhóm đầu tiên là tất cả những người có tên bắt đầu bằng "A", nhóm thứ hai là tất cả những người có tên bắt đầu bằng "B", và cứ thế. Quy tắc "Nhóm của bạn là chữ cái đầu tiên của tên bạn" cũng được coi là một hàm băm. Nhưng với hàm băm như vậy, chúng ta có nguy cơ có nhiều người trong nhóm "A" và ít hơn trong "E".

Cách 2. Theo ngày sinh.

Sinh vào ngày đầu tiên của bất kỳ tháng nào là nhóm đầu tiên, ngày thứ hai là nhóm thứ hai, và cứ thế. Sẽ có 31 nhóm. Trong nhóm thứ 31 sẽ có ít người hơn khoảng 2 lần so với các nhóm khác, nhưng người trong các nhóm như vậy được phân phối đều hơn nhiều so với trường hợp đầu tiên.

Cách 3. Số điện thoại

Ý tưởng lý tưởng là nhận được một số mà một bên là ngẫu nhiên nhất (khi đó các số như vậy sẽ được phân phối đều), một bên khác nó phải luôn được tính toán nhanh chóng và luôn như nhau.

Hãy lấy 4 chữ số cuối của số điện thoại - sẽ có 10.000 lựa chọn. Sau đó chia số này cho 30. Khi đó chúng ta có 30 khả năng chia lấy dư: 0, 1, 2, ..., 29. Đây sẽ là số nhóm của chúng ta.

Có ích! Thú vị là, hầu như bất cứ hàm băm nào cũng sử dụng phần dư của phép chia - đó là cách đơn giản và cho phép điều chỉnh số lượng nhóm cần chia các phần tử.

5.3 Tính chất chính của hàm băm

Tính chất chính của một hàm băm tốt:

Tính xác định: Cùng một hàm băm luôn phải trả về cùng một giá trị băm cho cùng một giá trị đầu vào.

Ví dụ:

key = "example"
assert hash(key) == hash(key)

Quan trọng! Toán tử assert kiểm tra rằng biểu thức phía bên phải là đúng True. Nếu biểu thức không đúng False, thì sẽ có một ngoại lệ được ném ra.

Tính đều: Một hàm băm tốt phải phân phối các giá trị đều khắp phạm vi các giá trị băm có thể có để tránh các xung đột.

Ví dụ từ cuộc sống của lập trình viên Python: Trong từ điển (lớp dict) Python, hàm băm hash() phân phối các khóa đều đặn.

Hiệu quả tính toán: Hàm băm phải nhanh và hiệu quả để không làm chậm các thao tác chèn và tìm kiếm.

Ví dụ từ cuộc sống của lập trình viên Python: Các hàm băm tiêu chuẩn trong Python được thực hiện để làm việc với các khóa loại khác nhau, như chuỗi và số.

Giảm thiểu xung đột: Xung đột xảy ra khi hai khóa khác nhau có cùng giá trị băm. Một hàm băm tốt phải giảm thiểu khả năng xảy ra xung đột.

Ví dụ từ cuộc sống của lập trình viên Python: Thuật toán SHA-256 giảm thiểu khả năng xảy ra xung đột khi băm dữ liệu.

Phân phối băm: Đối với khối lượng lớn dữ liệu, hàm băm phải đảm bảo phân phối đều các giá trị băm khắp bảng băm.

Ví dụ từ cuộc sống của lập trình viên Python: Các hàm băm tiêu chuẩn trong Python xử lý tốt việc phân phối các khóa trong bảng băm.

5.4 Ví dụ về hàm băm và cách triển khai chúng

Các hàm băm nhận đầu vào là dữ liệu kích thước tùy ý và trả về giá trị băm kích thước cố định. Hãy cùng xem qua một vài ví dụ về hàm băm và cách triển khai chúng.

Ví dụ 1: Hàm băm đơn giản cho chuỗi

Một trong những hàm băm đơn giản nhất cho chuỗi có thể được thực hiện bằng cách sử dụng tổng mã của các ký tự trong chuỗi:

def simple_hash(key):
    hash_value = 0
    for char in key:
        hash_value += ord(char)
    return hash_value % 1000  # Giả sử bảng của chúng ta có kích thước 1000

# Ví dụ sử dụng:
key = "example"
print(f"Giá trị băm cho khóa '{key}': {simple_hash(key)}")

Ví dụ 2: Hàm băm cho chuỗi sử dụng băm đa thức

Băm đa thức là một kỹ thuật phức tạp hơn nhưng hiệu quả hơn:

def polynomial_hash(key, a=33, m=1000):
    hash_value = 0
    for char in key:
        hash_value = (hash_value * a + ord(char)) % m
    return hash_value

# Ví dụ sử dụng:
key = "example"
print(f"Giá trị băm cho khóa '{key}': {polynomial_hash(key)}")

Ví dụ 3: Hàm băm tích hợp trong Python

Python cung cấp hàm tích hợp hash() để lấy giá trị băm cho các loại dữ liệu khác nhau:

key = "example"
print(f"Giá trị băm cho khóa '{key}': {hash(key)}")

Ví dụ 4: Hàm băm mật mã (SHA-256)

Các hàm băm mật mã như SHA-256 được sử dụng để đảm bảo bảo mật dữ liệu:

import hashlib

def sha256_hash(key):
    return hashlib.sha256(key.encode()).hexdigest()

# Ví dụ sử dụng:
key = "example"
print(f"Giá trị băm cho khóa '{key}': {sha256_hash(key)}")

5.5 Giới thiệu về băm và ứng dụng của nó

Băm là quá trình chuyển đổi dữ liệu đầu vào kích thước tùy ý thành kích thước cố định của giá trị băm bằng cách sử dụng hàm băm. Băm được sử dụng rộng rãi trong khoa học máy tính và lập trình để tối ưu hóa và đảm bảo an toàn.

Các ứng dụng chính của băm:

1. Bảng băm (dict): Bảng băm sử dụng hàm băm để tổ chức và truy cập dữ liệu nhanh chóng.

data = {"apple": 1, "banana": 2, "cherry": 3}
key = "banana"
hash_value = hash(key)
print(f"Giá trị băm cho khóa '{key}': {hash_value}")

2. Kiểm tra toàn vẹn dữ liệu: Các hàm băm được sử dụng để kiểm tra toàn vẹn của tệp và dữ liệu.

Ví dụ: Kiểm tra toàn vẹn của tệp sử dụng SHA-256:

import hashlib

def get_file_hash(file_path):
    hasher = hashlib.sha256()
    with open(file_path, 'rb') as file:
        buf = file.read()
        hasher.update(buf)
    return hasher.hexdigest()

file_hash = get_file_hash('example.txt')
print(f"SHA-256 hash của tệp: {file_hash}")

3. Mật mã học và bảo mật: Các hàm băm được sử dụng để tạo ra các nguyên thủy mật mã, như chữ ký số và băm mật khẩu.

Ví dụ: Băm mật khẩu sử dụng SHA-256:

import hashlib

def hash_password(password):
    return hashlib.sha256(password.encode()).hexdigest()

password = "securepassword"
hashed_password = hash_password(password)
print(f"Băm của mật khẩu: {hashed_password}")

4. Công cụ tìm kiếm và lập chỉ mục: Băm được sử dụng để tạo ra các chỉ mục và tìm kiếm dữ liệu nhanh chóng.

Ví dụ: Tạo chỉ mục cho tìm kiếm văn bản:

def create_index(text):
    index = {}
    for word in text.split():
        word_hash = hash(word)
        if word_hash not in index:
            index[word_hash] = []
        index[word_hash].append(word)
    return index

text = "This is an example text for indexing"
index = create_index(text)
print(f"Chỉ mục: {index}")

5. Quản lý bộ nhớ đệm: Băm được sử dụng để tổ chức bộ nhớ đệm và tìm kiếm dữ liệu nhanh chóng.

Ví dụ: Bộ nhớ đệm đơn giản sử dụng hàm băm:

cache = {}

def get_from_cache(key):
    hash_key = hash(key)
    return cache.get(hash_key, None)

def add_to_cache(key, value):
    hash_key = hash(key)
    cache[hash_key] = value

# Thêm và lấy dữ liệu từ bộ nhớ đệm
add_to_cache("test_key", "test_value")
print(get_from_cache("test_key"))  # Kết quả: test_value