Sự khác biệt thực sự giữa từ điển và bảng băm là gì?

Question

Tôi đã luôn sử dụng từ điển. Tôi viết bằng Python.

Answer 1

Từ điển là khái niệm chung để ánh xạ khóa cho giá trị. Có nhiều cách để thực hiện một ánh xạ như vậy.

Một Hashtable là một cách cụ thể để triển khai từ điển.

Bên cạnh hashtables, một cách phổ biến khác để triển khai từ điển là red-black trees.

Mỗi phương pháp đều có ưu và nhược điểm riêng. Một cây đỏ đen luôn có thể thực hiện tra cứu trong O (log N). Một hashtable có thể thực hiện một tra cứu trong O (1) thời gian mặc dù có thể làm suy giảm đến O (N) tùy thuộc vào đầu vào.

Answer 2

Từ điển Python được triển khai nội bộ bằng thẻ bắt đầu bằng #.

Answer 3

Từ điển là cấu trúc dữ liệu ánh xạ khóa tới giá trị.

Bảng băm là cấu trúc dữ liệu ánh xạ khóa tới giá trị bằng cách lấy giá trị băm của khóa (bằng cách áp dụng hàm băm nào đó) và ánh xạ tới một nhóm nơi một hoặc nhiều giá trị được lưu trữ.

IMO điều này tương tự như yêu cầu sự khác biệt giữa danh sách và danh sách được liên kết. Để rõ ràng, có thể điều quan trọng là Python hiện đang thực hiện các từ điển của họ bằng cách sử dụng các bảng băm, và CÓ THỂ là trường hợp trong tương lai mà Python thay đổi thực tế đó mà không làm cho từ điển của họ ngừng sử dụng từ điển .

Answer 4

"Từ điển" có một vài ý nghĩa khác nhau trong lập trình, vì wikipedia sẽ cho bạn biết - "mảng kết hợp", ý nghĩa trong đó Python sử dụng cụm từ này (còn được gọi là "ánh xạ") ý nghĩa (nhưng "từ điển dữ liệu" và "tấn công từ điển" trong các lần thử đoán mật khẩu cũng rất quan trọng).

Bảng băm là cấu trúc dữ liệu quan trọng; Python sử dụng chúng để triển khai hai loại dữ liệu tích hợp quan trọng, dict và set.

Vì vậy, ngay cả trong Python, bạn có thể không xem xét "bảng băm" là một từ đồng nghĩa với "từ điển" ... kể từ khi một cấu trúc dữ liệu tương tự cũng được sử dụng để thực hiện "bộ" -!)

Answer 5

Từ điển được triển khai bằng cách sử dụng các bảng băm. Theo tôi, sự khác biệt giữa 2 có thể được coi là sự khác biệt giữa Stacks và mảng mà chúng ta sẽ sử dụng mảng để thực hiện Stacks.

Answer 6

Bảng băm luôn sử dụng một số hàm hoạt động trên một giá trị để xác định nơi lưu trữ giá trị. Một từ điển (như tôi tin bạn dự định nó) là một thuật ngữ tổng quát hơn, và chỉ đơn giản chỉ ra một cơ chế tra cứu, có thể là một bảng băm hoặc có thể được thực hiện bởi một cấu trúc đơn giản hơn mà không xem xét giá trị của nó trong việc xác định vị trí lưu trữ của nó.