it-swarm-vi.com

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

Sự khác biệt giữa HashDictionary là gì?

Đến từ một nền tảng kịch bản, tôi cảm thấy rằng chúng giống nhau, nhưng tôi muốn tìm ra sự khác biệt chính xác. Googling không giúp tôi nhiều.

48
Sairam

Hash là một cấu trúc dữ liệu được đặt tên cực kỳ kém, nơi lập trình viên đã nhầm lẫn giao diện với việc thực hiện ( = đã quá lười biếng để viết tên đầy đủ, tức là HashTable thay vào đó dùng đến một từ viết tắt, Hash).

Dictionarytên chính xác của tên) của giao diện (= ADT ), tức là một thùng chứa kết hợp ánh xạ các khóa (thường là duy nhất) thành các giá trị (không nhất thiết là duy nhất).

Bảng băm là one khả năng thực hiện từ điển như vậy cung cấp các đặc điểm truy cập khá tốt (về mặt thời gian chạy) và do đó thường là triển khai mặc định.

Việc thực hiện như vậy có hai thuộc tính quan trọng:

  1. các khóa phải là hashable đẳng thức so sánh.
  2. các mục xuất hiện không theo thứ tự cụ thể trong từ điển.

(Để một khóa có thể băm có nghĩa là chúng ta có thể tính toán một giá trị số từ một khóa mà sau đó được sử dụng làm chỉ mục trong một mảng.)

Có tồn tại các triển khai thay thế của cấu trúc dữ liệu từ điển áp đặt một order trên các khóa - điều này thường được gọi là a sort dictionary (và thường được thực hiện theo thuật ngữ một cây tìm kiếm, mặc dù các triển khai hiệu quả khác tồn tại).


Để tóm tắt: a dictionary là một ADT ánh xạ các khóa thành các giá trị. Có một số triển khai có thể có của ADT này, trong đó bảng băm là một. Hash là một cách viết sai nhưng trong ngữ cảnh, nó tương đương với một từ điển được thực hiện dưới dạng bảng băm.

94
Konrad Rudolph

"Từ điển" là tên của khái niệm. Một hashtable là một thực hiện có thể.

8
dan_waterworth

Từ điển là thuật ngữ tập thể được đưa ra cho bất kỳ triển khai cấu trúc dữ liệu nào được sử dụng để tra cứu/chèn nhanh. Điều này có thể đạt được/thực hiện bằng nhiều cấu trúc dữ liệu khác nhau như bảng băm, danh sách bỏ qua, cây rb, v.v ... Bảng băm là một cấu trúc dữ liệu cụ thể hữu ích cho nhiều mục đích bao gồm thực hiện từ điển.

7
aufather

A dictionary sử dụng khóa để tham chiếu giá trị trực tiếp bên trong mảng kết hợp.

i E (KEY => VALUE)

A hash thường được mô tả là bảng băm sử dụng hàm băm để tính toán vị trí trong bộ nhớ (hoặc dễ dàng hơn là một mảng) trong đó giá trị sẽ là. Băm sẽ lấy KEY làm đầu vào và đưa ra một giá trị làm đầu ra. Sau đó cắm giá trị đó vào bộ nhớ hoặc chỉ mục mảng.

i E KEY => HASH FUNCTION => VALUE

Tôi đoán một cái là trực tiếp trong khi cái kia thì không. Các hàm băm có thể không hoàn hảo hoặc đôi khi có thể cung cấp một chỉ mục tham chiếu giá trị sai. Nhưng điều đó có thể được sửa chữa.

Nơi tốt nhất để tìm: Wikipedia ( mảng kết hợp bảng băm )

5
Ross