Hiểu biết về quy tắc băm trong Python

Khi nói về băm trong Python, chúng ta đang bước vào một lĩnh vực nơi danh tính, sự bình đẳng và hiệu suất hội tụ. Trong bài học đầu tiên, chúng ta đã tìm hiểu sự khác biệt giữa Danh tính và Sự bình đẳng. Băm trong Python sử dụng sự bình đẳng thay vì danh tính. Nó hứa hẹn rằng hai đối tượng bằng nhau sẽ chia sẻ cùng một dấu hiệu.

Nhưng lời hứa này không hoàn hảo.

Phần 1: Băm là gì?

Băm (Hash) là một giá trị được tạo ra bởi một hàm nhằm đại diện duy nhất cho một đối tượng. Trong Python, hàm tích hợp hash() trả về một số nguyên và nó được sử dụng bởi các từ điển và tập hợp để kiểm tra sự hiện diện. Khi bạn thực hiện:

hash("key")

Python không tìm kiếm qua tất cả các khóa mỗi lần. Thay vào đó, nó tính toán một băm cho "key", sử dụng nó để nhảy đến đúng vị trí trong bộ nhớ, và sau đó kiểm tra sự bình đẳng để xác nhận.

Vì vậy, quy tắc là:

1. Nếu a == b, thì hash(a) == hash(b).
2. Nhưng điều ngược lại không được đảm bảo: nếu hash(a) == hash(b), a và b có thể không bằng nhau.

Quy tắc đầu tiên cho phép các từ điển và tập hợp hoạt động đúng cách.

Phần 2: Trường hợp kỳ lạ của NaN

Về mặt toán học, NaN (Not a Number) được định nghĩa như sau:

float('nan') == float('nan')  # False

Điều này là có chủ ý: NaN không bằng với bất kỳ điều gì, ngay cả chính nó.

Tuy nhiên, Python đảm bảo:

hash(float('nan')) == hash(float('nan'))

Tại sao? Bởi vì các bộ sưu tập dựa trên băm yêu cầu một hợp đồng nhất quán: các đối tượng bằng nhau phải chia sẻ cùng một băm, nhưng Python không cấm các đối tượng không bằng nhau chia sẻ một băm.

Phần 3: Băm và Sự bình đẳng trong các lớp do người dùng định nghĩa

Khi bạn định nghĩa lớp riêng của mình, bạn có thể quyết định ý nghĩa của sự bình đẳng và băm.

Bây giờ, hai cuộn với cùng một văn bản được coi là bằng nhau, và chúng chia sẻ cùng một băm:

class Cuon:
    def __init__(self, text):
        self.text = text

    def __eq__(self, other):
        return self.text == other.text

    def __hash__(self):
        return hash(self.text)

Nếu bạn ghi đè __eq__ nhưng quên ghi đè __hash__, Python sẽ thường làm cho đối tượng của bạn không thể băm. Nếu bạn định nghĩa chúng không nhất quán như việc trả về các giá trị băm khác nhau cho các đối tượng bằng nhau, mã của bạn có thể hoạt động kỳ lạ hoặc không hiệu quả.

Hướng dẫn thực hành:

• Nếu một lớp không định nghĩa phương thức __eq__(), nó cũng không nên định nghĩa hoạt động __hash__().
• Nếu nó định nghĩa __eq__() nhưng không có __hash__(), các phiên bản của nó sẽ không thể sử dụng làm mục trong các bộ sưu tập có thể băm.
• Nếu một lớp định nghĩa các đối tượng có thể thay đổi và thực hiện phương thức __eq__(), nó không nên thực hiện __hash__(), vì việc triển khai các bộ sưu tập có thể băm yêu cầu rằng giá trị băm của một khóa là không thay đổi (nếu giá trị băm của đối tượng thay đổi, nó sẽ nằm trong thùng băm sai).

Phần 4: Các vấn đề khác

4.1 Sự bình đẳng giữa các loại

Python cố gắng duy trì tính nhất quán giữa các loại liên quan:

print(1 == 1.0)      # True
print(hash(1) == hash(1.0))  # True

Mặc dù là các loại khác nhau, giá trị của 1 và 1.0 đều bằng nhau, vì vậy các băm của chúng cũng bằng nhau.

d = {1: "integer"}
d[1.0]   # "integer"

Nhìn qua, điều này có vẻ thanh lịch, nhưng nó có nghĩa là các loại số khác nhau có thể sụp đổ vào cùng một thùng, ngay cả khi ý nghĩa của chúng khác nhau trong miền của bạn. Trong mã khoa học hoặc tài chính, sự bình đẳng tinh tế này có thể gây ra hành vi bất ngờ nếu bạn muốn phân biệt int với float.

4.2 Không thay đổi vs Thay đổi

Các băm được thiết kế để ổn định. Nếu nội dung của một đối tượng có thể thay đổi sau khi được đặt trong một từ điển hoặc tập hợp, việc ánh xạ sẽ bị phá vỡ.

Đây là lý do:

• Các container không thay đổi (như tuples) có thể băm — nhưng chỉ nếu tất cả các nội dung của chúng có thể băm.
• Các container có thể thay đổi (như lists và dicts) không thể băm.

hash((1, 2, (3, 4)))  # Works
hash((1, [2, 3]))     # TypeError

Lỗi không phải ngẫu nhiên. Nó bảo vệ bạn khỏi việc đặt một khóa không ổn định vào một từ điển. Hãy tưởng tượng việc thay đổi danh sách bên trong một tuple sau khi nó đã được sử dụng làm khóa — giá trị băm sẽ không còn phản ánh trạng thái của đối tượng nữa.

Kết luận

Người mới thấy hai NaNs và nói: "Các dấu ấn giống nhau, vì vậy các đối tượng phải giống nhau." Người thầy đã sửa sai: "Mực giống nhau, nhưng con dấu đã bị vỡ."

Băm là một biểu tượng, không phải là một bằng chứng. Sự bình đẳng và băm có thể chạm vào nhau, nhưng chúng không bị ràng buộc. Để thấy rõ, chúng ta phải nắm giữ cả biểu tượng và nội dung mà nó chỉ đến.

Cảm ơn bạn đã đọc Python Koans! Nếu bạn thích bài viết này, hãy chia sẻ với bạn bè hoặc đăng ký bên dưới để nhận thêm thông tin:

Python Koans | Vivis Dev | Substack

Các bài học Python được gói trong các bài koan. Những câu đố nhỏ, những sự thật sâu sắc. Không phải là bài hướng dẫn thông thường của bạn. Click để đọc Python Koans, của Vivis Dev, một ấn phẩm Substack với hàng trăm người đăng ký.

pythonkoans.substack.com