Đối tượng Python làm khóa từ điển

Yêu cầu duy nhất đối với khóa từ điển là khóa đó có thể băm được. Các loại có thể thay đổi như danh sách, từ điển và bộ sẽ không hoạt động và dẫn đến lỗi như TypeError. loại không thể băm. 'dict'. nguồn

Những người mới sử dụng Python thường thắc mắc tại sao, trong khi ngôn ngữ này bao gồm cả bộ dữ liệu và loại danh sách, bộ dữ liệu có thể được sử dụng làm khóa từ điển, trong khi danh sách thì không. Đây là một quyết định thiết kế có chủ ý và có thể được giải thích tốt nhất bằng cách hiểu cách thức hoạt động của từ điển Python

Từ điển hoạt động như thế nào

Từ điển, trong Python, còn được gọi là "ánh xạ", bởi vì chúng "ánh xạ" hoặc "liên kết" các đối tượng chính với các đối tượng giá trị

Do đó, ánh xạ Python phải có khả năng, với một đối tượng khóa cụ thể, xác định đối tượng giá trị nào [nếu có] được liên kết với một khóa đã cho. Một cách tiếp cận đơn giản là lưu trữ danh sách các cặp [khóa, giá trị], sau đó tìm kiếm danh sách một cách tuần tự mỗi khi một giá trị được yêu cầu. Tuy nhiên, cách tiếp cận này sẽ rất chậm với số lượng lớn các mục - về độ phức tạp, thuật toán này sẽ là O[n], trong đó n là số lượng mục trong ánh xạ

Việc triển khai từ điển của Python giảm độ phức tạp trung bình của việc tra cứu từ điển xuống O[1] bằng cách yêu cầu các đối tượng chính đó cung cấp hàm "băm". Hàm băm như vậy lấy thông tin trong một đối tượng chính và sử dụng nó để tạo ra một số nguyên, được gọi là giá trị băm. Giá trị băm này sau đó được sử dụng để xác định cặp "nhóm" [khóa, giá trị] này sẽ được đặt vào. Mã giả cho chức năng tra cứu này có thể trông giống như

Để thuật toán tra cứu như vậy hoạt động chính xác, các hàm băm được cung cấp phải đảm bảo rằng nếu hai khóa tạo ra các giá trị băm khác nhau thì hai đối tượng khóa không tương đương, nghĩa là,

for all i1, i2, if hash[i1] != hash[i2], then i1 != i2

Mặt khác, việc kiểm tra giá trị băm của một đối tượng chính có thể khiến chúng ta tìm sai nhóm và do đó không bao giờ tìm thấy giá trị liên quan

Để thuật toán tra cứu như vậy hoạt động hiệu quả, hầu hết các nhóm chỉ nên có một số lượng nhỏ các mục [tốt nhất là chỉ có một mục]. Xem xét điều gì sẽ xảy ra với hàm băm sau

Lưu ý rằng hàm này đáp ứng các yêu cầu của hàm băm - mỗi khi hai khóa có giá trị băm khác nhau, chúng sẽ đại diện cho các đối tượng khác nhau. [Điều này đúng một cách tầm thường vì không có khóa nào có giá trị băm khác nhau - tất cả chúng đều có giá trị 1. ] Nhưng đây là một hàm băm tồi vì nó có nghĩa là tất cả các cặp [khóa, giá trị] sẽ được đặt trong một danh sách duy nhất và do đó, mỗi lần tra cứu sẽ yêu cầu tìm kiếm toàn bộ danh sách này. Do đó, một thuộc tính mong muốn [rất] của hàm băm là nếu hai khóa tạo ra các giá trị băm giống nhau, thì các đối tượng khóa là tương đương, nghĩa là,

for all i1, i2, if hash[i1] == hash[i2], then i1 == i2

Các hàm băm có thể ước lượng tốt thuộc tính này sẽ phân phối đồng đều các cặp [khóa, giá trị] trên các nhóm và giảm thời gian tra cứu

Các loại có thể sử dụng làm khóa từ điển

Cuộc thảo luận ở trên sẽ giải thích tại sao Python yêu cầu điều đó

Để được sử dụng làm khóa từ điển, một đối tượng phải hỗ trợ hàm băm [e. g. đến __hash__], so sánh bình đẳng [e. g. thông qua __eq__ hoặc __cmp__] và phải thỏa mãn điều kiện đúng ở trên

Danh sách dưới dạng khóa từ điển

Điều đó nói rằng, câu trả lời đơn giản cho lý do tại sao danh sách không thể được sử dụng làm khóa từ điển là danh sách không cung cấp phương thức __hash__ hợp lệ. Tất nhiên, câu hỏi rõ ràng là, "Tại sao không?"

Xem xét những loại hàm băm nào có thể được cung cấp cho danh sách

Nếu các danh sách được băm theo id, điều này chắc chắn sẽ hợp lệ theo định nghĩa của hàm băm của Python - các danh sách có giá trị băm khác nhau sẽ có các id khác nhau. Nhưng danh sách là vùng chứa và hầu hết các hoạt động khác trên chúng đều xử lý chúng như vậy. Vì vậy, danh sách băm theo id của chúng thay vào đó sẽ tạo ra hành vi không mong muốn, chẳng hạn như

• Tra cứu các danh sách khác nhau có cùng nội dung sẽ tạo ra các kết quả khác nhau, mặc dù so sánh các danh sách có cùng nội dung sẽ chỉ ra chúng là tương đương

• Sử dụng một danh sách theo nghĩa đen trong tra cứu từ điển sẽ là vô nghĩa -- nó sẽ luôn tạo ra KeyError

Nếu các danh sách được băm theo nội dung của chúng [như các bộ dữ liệu], thì đây cũng sẽ là một hàm băm hợp lệ - các danh sách có giá trị băm khác nhau sẽ có nội dung khác nhau. Vì vậy, một lần nữa, vấn đề không nằm ở định nghĩa của hàm băm. Nhưng điều gì sẽ xảy ra khi một danh sách, được sử dụng làm khóa từ điển, bị sửa đổi? . Điều này có thể dẫn đến các lỗi không mong muốn như

   1 >>> l = [1, 2]
   2 >>> d = {}
   3 >>> d[l] = 42
   4 >>> l.append[3]
   5 >>> d[l]
   6 Traceback [most recent call last]:
   7   File "", line 1, in ?
   8 KeyError: [1, 2, 3]
   9 >>> d[[1, 2]]
  10 Traceback [most recent call last]:
  11   File "", line 1, in ?
  12 KeyError: [1, 2]

trong đó giá trị 42 không còn nữa vì danh sách băm thành cùng một giá trị, [1, 2], không tương đương với danh sách đã sửa đổi và giá trị tương đương với danh sách đã sửa đổi, [1, 2, 3] . Vì từ điển không biết khi nào một đối tượng khóa được sửa đổi, nên các lỗi như vậy chỉ có thể được tạo ra khi tra cứu khóa chứ không phải tại thời điểm sửa đổi đối tượng, điều này có thể khiến các lỗi như vậy khá khó gỡ lỗi

Nhận thấy rằng cả hai cách băm danh sách đều có một số tác dụng phụ không mong muốn, rõ ràng hơn là tại sao Python có lập trường rằng

Không nên sử dụng loại danh sách tích hợp làm khóa từ điển

Lưu ý rằng vì các bộ dữ liệu là bất biến, nên chúng không gặp rắc rối với danh sách - chúng có thể được băm theo nội dung của chúng mà không phải lo lắng về việc sửa đổi. Do đó, trong Python, chúng cung cấp phương thức __hash__ hợp lệ và do đó có thể sử dụng làm khóa từ điển

Các loại do người dùng xác định làm khóa từ điển

Còn các trường hợp của các loại do người dùng xác định thì sao?

Theo mặc định, tất cả các loại do người dùng xác định đều có thể sử dụng làm khóa từ điển với hash[object] mặc định là id[object] và cmp[object1, object2] mặc định là cmp[id[object1], id[object2]]. Đề xuất tương tự này đã được thảo luận ở trên cho các danh sách và thấy không đạt yêu cầu. Tại sao các loại do người dùng xác định lại khác nhau?

1. Trong trường hợp một đối tượng phải được đặt trong ánh xạ, nhận dạng đối tượng thường quan trọng hơn nhiều so với nội dung đối tượng

2. Trong trường hợp nội dung đối tượng thực sự quan trọng, cài đặt mặc định có thể được xác định lại bằng cách ghi đè __hash__ và __cmp__ hoặc __eq__

Lưu ý rằng cách thực hành tốt hơn thường là khi một đối tượng được liên kết với một giá trị, chỉ cần gán giá trị đó làm một trong các thuộc tính của đối tượng

Một đối tượng có thể là một khóa trong từ điển Python không?

Đối tượng có thể được sử dụng làm khóa trong từ điển không?

dict[] có giống như {} không?

Bạn có thể lưu trữ các đối tượng trong từ điển Python không?