Từ điển Python có phải là một ví dụ về bảng băm không?

Question

Một trong những cấu trúc dữ liệu cơ bản trong Python là từ điển, cho phép người ta ghi lại "các khóa" để tra cứu "các giá trị" của bất kỳ loại nào. Điều này có được thực thi nội bộ dưới dạng bảng băm không? Nếu không, nó là gì?

Answer 1

Vâng, đó là bản đồ băm hoặc bảng băm. Bạn có thể đọc mô tả về triển khai dict của python, được viết bởi Tim Peters, here.

Đó là lý do tại sao bạn không thể sử dụng một cái gì đó 'không hashable' như một chìa khóa dict, giống như một danh sách:

>>> a = {} 
>>> b = ['some', 'list'] 
>>> hash(b) 
Traceback (most recent call last): 
    File "<stdin>", line 1, in <module> 
TypeError: list objects are unhashable 
>>> a[b] = 'some' 
Traceback (most recent call last): 
    File "<stdin>", line 1, in <module> 
TypeError: list objects are unhashable 

Bạn có thể read more about hash tables hoặc check how it has been implemented in python và why it is implemented that way.

Answer 2

Có. Bên trong nó được thực hiện như băm mở dựa trên đa thức nguyên thủy trên Z/2 (source).

Answer 3

Nếu bạn quan tâm đến chi tiết kỹ thuật, một bài viết trong số Beautiful Code sẽ đề cập đến nội dung thực thi dict của Python.

Answer 4

Để mở rộng khi giải thích nosklo của:

a = {} 
b = ['some', 'list'] 
a[b] = 'some' # this won't work 
a[tuple(b)] = 'some' # this will, same as a['some', 'list'] 

Answer 5

Phải có hơn một từ điển Python hơn một tra cứu bảng trên băm(). Bằng cách thử nghiệm vũ phu tôi thấy băm này va chạm:

>>> hash(1.1) 
2040142438 
>>> hash(4504.1) 
2040142438 

Tuy nhiên, nó không phá vỡ các từ điển:

>>> d = { 1.1: 'a', 4504.1: 'b' } 
>>> d[1.1] 
'a' 
>>> d[4504.1] 
'b' 

Sanity kiểm tra:

>>> for k,v in d.items(): print(hash(k)) 
2040142438 
2040142438 

Có thể có một mức tham chiếu sau hash() giúp tránh va chạm giữa các khóa từ điển. Hoặc có thể dict() sử dụng một băm khác nhau.

(By the way, đây bằng Python 2.7.10. Tương tự câu chuyện bằng Python 3.4.3 và 3.5.0 với một vụ va chạm tại hash(1.1) == hash(214748749.8).)