Câu hỏi Tại sao từ điển được ưu tiên hơn Hashtable?


Trong hầu hết các ngôn ngữ lập trình, từ điển được ưu tiên hơn hashtables. Lý do đằng sau điều đó là gì?


1205
2017-11-19 09:24


gốc


> Điều này không nhất thiết phải đúng. Bảng băm là triển khai từ điển. Một điển hình tại đó, và nó có thể là một mặc định trong .NET, nhưng nó không phải là định nghĩa duy nhất. Tôi không chắc rằng điều này là bắt buộc theo tiêu chuẩn ECMA, nhưng Tài liệu MSDN rất rõ ràng gọi nó như đang được thực hiện như là một hashtable. Họ thậm chí cung cấp lớp SortedList cho các lần khi một sự thay thế hợp lý hơn. - Promit
@Promit Tôi luôn nghĩ rằng Dictionary là việc triển khai Hashtable. - b1nary.atr0phy
Tôi nghĩ lý do là, trong từ điển bạn có thể xác định loại khóa và giá trị cho selfe của bạn. Hashtable chỉ có thể lấy các đối tượng và lưu các cặp dựa trên hàm băm (từ object.GetHashCode ()). - Radinator
Một từ điển là để tìm kiếm một mục duy nhất. Cùng một mục có thể được tìm thấy dưới nhiều phím. Nhưng bạn sẽ không nhận được nhiều mục từ cùng một khóa. Điều này không đúng với hashtables. Nếu bạn đã thực hiện tìm kiếm ví dụ cho tên, bạn có thể tìm thấy nhiều mục nhập, mỗi mục đại diện cho một người khác có cùng tên. Điều này thực sự là tiêu chí duy nhất của bạn để chọn cái nào cần sử dụng. - Dan


Các câu trả lời:


Đối với những gì nó có giá trị, một từ điển  (khái niệm) một bảng băm.

Nếu bạn có nghĩa là "tại sao chúng ta sử dụng Dictionary<TKey, TValue> lớp thay vì Hashtable lớp học? ", thì đó là một câu trả lời dễ dàng: Dictionary<TKey, TValue> là loại chung, Hashtable không phải là. Điều đó có nghĩa là bạn được an toàn với Dictionary<TKey, TValue>, bởi vì bạn không thể chèn bất kỳ đối tượng ngẫu nhiên vào nó, và bạn không phải bỏ các giá trị bạn đưa ra.

Điều thú vị là Dictionary<TKey, TValue> triển khai trong .NET Framework dựa trên Hashtable, như bạn có thể nói từ bình luận này trong mã nguồn của nó:

Từ điển chung được sao chép từ nguồn của Hashtable

Nguồn 


1406
2017-11-19 09:28



Và các bộ sưu tập chung cũng nhanh hơn rất nhiều vì không có boxing / unboxing - Chris S
Bạn không chắc chắn về một Hashtable với câu lệnh trên, nhưng đối với ArrayList vs List <t> nó là true - Chris S
Hashtable sử dụng Object để giữ những thứ bên trong (Chỉ cách không chung chung để làm điều đó) vì vậy nó cũng sẽ phải hộp / unbox. - Guvante
@BrianJ: Một "bảng băm" (hai từ) là thuật ngữ khoa học máy tính cho loại cấu trúc này; Từ điển là một triển khai cụ thể. Một HashTable tương ứng gần với một từ điển <object, object> (mặc dù với các giao diện hơi khác nhau), nhưng cả hai đều là các triển khai của khái niệm bảng băm. Và tất nhiên, chỉ để gây nhầm lẫn các vấn đề hơn nữa, một số ngôn ngữ gọi bảng băm của họ là "từ điển" (ví dụ: Python) - nhưng thuật ngữ CS thích hợp vẫn là bảng băm. - Michael Madsen
@BrianJ: Cả hai HashTable (lớp) và Dictionary (lớp) là các bảng băm (khái niệm), nhưng HashTable Không phải là Dictionary, cũng không phải là Dictionary một HashTable. Chúng được sử dụng trong thời trang rất giống nhau, và Dictionary<Object,Object> có thể hành động theo cùng cách thức mà HashTable nhưng không trực tiếp chia sẻ bất kỳ mã nào (mặc dù các phần có thể được triển khai theo cách rất giống nhau). - Michael Madsen


Dictionary <<< >>> Hashtable sự khác biệt:

  • Chung  <<< >>> Không chung
  • Nhu cầu -sự đồng bộ hóa chủ đề riêng <<< >>> Ưu đãi chủ đề an toàn phiên bản thông qua Synchronized() phương pháp
  • Mục được liệt kê: KeyValuePair <<< >>> Mục được liệt kê: DictionaryEntry
  • Mới hơn (> .NET 2.0) <<< >>> Cũ hơn (kể từ .NET 1.0)
  • trong System.Collections.Generic <<< >>> đang ở System.Collections 
  • Yêu cầu khóa không tồn tại ném ngoại lệ <<< >>> Yêu cầu khóa không tồn tại trả về null
  • có khả năng một chút nhanh hơn cho các loại giá trị <<< >>> chậm hơn một chút (cần boxing / unboxing) cho các loại giá trị

Dictionary / Hashtable điểm tương đồng:

  • Cả hai đều là nội bộ hashtables == truy cập nhanh vào dữ liệu nhiều mục theo khóa
  • Cả hai đều cần phím bất biến và duy nhất
  • Chìa khóa của cả hai nhu cầu riêng GetHashCode() phương pháp

Giống Bộ sưu tập .NET (ứng viên sử dụng thay cho từ điển và Hashtable):

  • ConcurrentDictionary - - chủ đề an toàn (có thể được truy cập một cách an toàn từ một số chủ đề đồng thời)
  • HybridDictionary - - hiệu suất tối ưu (đối với vài mặt hàng và cũng cho nhiều mặt hàng)
  • OrderedDictionary - giá trị có thể là truy cập qua chỉ mục int (theo thứ tự các mục được thêm vào)
  • SortedDictionary - mặt hàng được sắp xếp tự động
  • StringDictionary - gõ mạnh mẽ và tối ưu hóa cho chuỗi

565
2018-04-21 10:32



Chúng ta có thể sử dụng concurrentDictionary (trong .NET 4.0) cho threadsafe. - WAP Guy
@ Guillaume86, đây là lý do tại sao bạn sử dụng TryGetValue thay thế msdn.microsoft.com/en-us/library/bb347013.aspx - Aleksey Bykov
+1 cho StringDictionary... btw StringDictionary không giống như Dictionary<string, string> khi bạn sử dụng hàm tạo mặc định. - Danny Chen
ParallelExtensionsExtras @code.msdn.microsoft.com/windowsdesktop/… có chứa một ObservableConcurrentDictionary đó là tuyệt vời linh sam ràng buộc cũng như đồng thời. - VoteCoffee
lời giải thích tuyệt vời, nó thực sự tốt đẹp bạn cũng liệt kê những điểm tương đồng để giảm bớt những câu hỏi có thể đến với tâm trí của một người - mkb


Bởi vì Dictionary là một lớp học chung chung ( Dictionary<TKey, TValue> ) để truy cập nội dung của nó an toàn kiểu (tức là bạn không cần phải truyền từ Object, như bạn làm với một Hashtable).

So sánh

var customers = new Dictionary<string, Customer>();
...
Customer customer = customers["Ali G"];

đến

var customers = new Hashtable();
...
Customer customer = customers["Ali G"] as Customer;

Tuy nhiên, Dictionary được triển khai như Hashtable bên trong, về mặt kỹ thuật, nó hoạt động theo cùng một cách.


163
2017-11-19 09:27





FYI: Trong .NET, Hashtable là chủ đề an toàn để sử dụng bởi nhiều chủ đề đọc và một chuỗi viết đơn, trong khi ở Dictionary thành viên tĩnh công cộng là chủ đề an toàn, nhưng bất kỳ thành viên cá thể nào cũng không được bảo đảm là luồng an toàn.

Chúng tôi đã phải thay đổi tất cả các từ điển của mình trở lại Hashtable vì điều này.


80
2017-11-19 11:55



Vui vẻ. Mã nguồn từ điển <T> trông sạch hơn và nhanh hơn rất nhiều. Nó có thể là tốt hơn để sử dụng từ điển và thực hiện đồng bộ hóa của riêng bạn. Nếu từ điển đọc hoàn toàn cần phải được hiện tại, sau đó bạn chỉ cần có để đồng bộ hóa truy cập vào các phương pháp đọc / ghi của từ điển. Nó sẽ là rất nhiều khóa, nhưng nó sẽ là chính xác. - Triynko
Ngoài ra, nếu lần đọc của bạn không phải là hoàn toàn hiện tại, bạn có thể coi từ điển là không thay đổi. Sau đó bạn có thể lấy một tham chiếu đến từ điển và đạt được hiệu suất bằng cách không đồng bộ hóa đọc ở tất cả (vì nó không thay đổi và vốn đã an toàn). Để cập nhật nó, bạn xây dựng một bản cập nhật hoàn chỉnh của từ điển trong nền, sau đó chỉ cần trao đổi tham chiếu với Interlocked.CompareExchange (giả sử một luồng văn bản đơn; nhiều luồng ghi sẽ yêu cầu đồng bộ hóa các bản cập nhật). - Triynko
.Net 4.0 đã thêm ConcurrentDictionary lớp có tất cả các phương thức công cộng / được bảo vệ được triển khai để an toàn chỉ. Nếu bạn không cần hỗ trợ các nền tảng cũ, điều này sẽ cho phép bạn thay thế Hashtable trong mã đa luồng: msdn.microsoft.com/en-us/library/dd287191.aspx - Dan Neely
vô danh để giải cứu. Câu trả lời thú vị. - unkulunkulu
Tôi nhớ lại đọc rằng HashTable chỉ là người viết chủ đề an toàn trong kịch bản mà thông tin không bao giờ bị xóa khỏi bảng. Nếu người đọc đang yêu cầu một mục nằm trong bảng trong khi một mục khác đang bị xóa và người đọc sẽ xem nhiều hơn một mục cho mục đó, có thể khi người đọc đang tìm kiếm người viết có thể di chuyển mục đó từ một nơi chưa được kiểm tra đến nơi có, do đó dẫn đến một báo cáo sai rằng mục đó không tồn tại. - supercat


Trong .NET, sự khác biệt giữa Dictionary<,> và HashTable chủ yếu là trước đây là loại chung, vì vậy bạn có được tất cả lợi ích của generics về kiểm tra kiểu tĩnh (và giảm boxing, nhưng điều này không lớn như mọi người có xu hướng suy nghĩ về hiệu suất - có một xác định chi phí bộ nhớ để đấm bốc, mặc dù).


62
2017-11-19 09:28





Mọi người đang nói rằng một từ điển giống như một bảng băm.

Điều này không thực sự đúng. Bảng băm là một thực hiện của một từ điển. Một điển hình tại đó, và nó có thể là một mặc định trong .NET, nhưng nó không phải là định nghĩa duy nhất.

Bạn cũng có thể thực hiện tốt một từ điển với một danh sách liên kết hoặc một cây tìm kiếm, nó sẽ không hiệu quả (đối với một số chỉ số hiệu quả).


27
2017-11-19 13:03



MS tài liệu nói: "Lấy một giá trị bằng cách sử dụng khóa của nó là rất nhanh, gần với O (1), vì lớp Từ điển <(Of <(TKey, TValue>)>) được triển khai như một bảng băm." - vì vậy bạn nên được đảm bảo một hashtable khi giao dịch với Dictionary<K,V>. IDictionary<K,V> có thể là bất cứ điều gì, mặc dù :) - snemarch
@ rix0rrr - Tôi nghĩ rằng bạn đã có điều đó ngược, một từ điển sử dụng một HashTable không phải là một HashTable sử dụng một từ điển. - Joseph Hamilton
@JosephHamilton - rix0rrr đã làm đúng: "Bảng băm Là thực hiện một từ điển"Anh ấy có nghĩa là khái niệm" từ điển ", không phải là lớp (lưu ý trường hợp thấp hơn) .Theo khái niệm, một bảng băm thực hiện một giao diện từ điển. Trong .NET, Dictionary sử dụng một bảng băm để thực hiện IDictionary. Nó lộn xộn;) - Robert Hensing
Tôi đã nói về .NET, vì đó là những gì anh ta tham chiếu trong phản ứng của anh ta. - Joseph Hamilton
@JosephHamilton: dụng cụ (hoặc là thực hiện) thậm chí không có nghĩa là từ xa giống như sử dụng. Khá ngược lại. Có lẽ nó sẽ được rõ ràng hơn nếu ông nói nó hơi khác nhau (nhưng với cùng một ý nghĩa): "một bảng băm là một cách để thực hiện một từ điển". Đó là, nếu bạn muốn các chức năng của một từ điển, một cách để làm điều đó (để triển khai thực hiện từ điển), là sử dụng một hashtable. - ToolmakerSteve


Collections & Generics rất hữu ích để xử lý nhóm đối tượng. Trong .NET, tất cả các đối tượng bộ sưu tập đều nằm dưới giao diện IEnumerable, lần lượt có ArrayList(Index-Value)) & HashTable(Key-Value). Sau .NET framework 2.0, ArrayList & HashTable đã được thay thế bằng List & Dictionary. Bây giờ, Arraylist & HashTable không còn được sử dụng trong các dự án hiện nay.

Đến với sự khác biệt giữa HashTable & Dictionary, Dictionary là nơi chung Hastable không phải là Chung. Chúng tôi có thể thêm bất kỳ loại đối tượng nào vào HashTablenhưng trong khi truy xuất, chúng tôi cần truyền nó đến loại được yêu cầu. Vì vậy, nó không phải là loại an toàn. Nhưng để dictionary, trong khi tự khai báo, chúng ta có thể chỉ định kiểu khóa và giá trị, vì vậy không cần phải cast trong khi lấy ra.

Hãy xem một ví dụ:

HashTable

class HashTableProgram
{
    static void Main(string[] args)
    {
        Hashtable ht = new Hashtable();
        ht.Add(1, "One");
        ht.Add(2, "Two");
        ht.Add(3, "Three");
        foreach (DictionaryEntry de in ht)
        {
            int Key = (int)de.Key; //Casting
            string value = de.Value.ToString(); //Casting
            Console.WriteLine(Key + " " + value);
        }

    }
}

Từ điển,

class DictionaryProgram
{
    static void Main(string[] args)
    {
        Dictionary<int, string> dt = new Dictionary<int, string>();
        dt.Add(1, "One");
        dt.Add(2, "Two");
        dt.Add(3, "Three");
        foreach (KeyValuePair<int, String> kv in dt)
        {
            Console.WriteLine(kv.Key + " " + kv.Value);
        }
    }
}

21
2017-09-17 11:10



thay vì chỉ định rõ ràng kiểu dữ liệu cho KeyValuePair, chúng ta có thể sử dụng var. Vì vậy, điều này sẽ làm giảm gõ - foreach (var kv trong dt) ... chỉ là một gợi ý. - Ron


Từ điển:

  • Nó trả về / ném ngoại lệ nếu chúng ta cố gắng tìm một khóa không tồn tại.

  • Nó nhanh hơn Hashtable vì không có boxing và unboxing.

  • Chỉ các thành viên tĩnh công cộng là luồng an toàn.

  • Từ điển là một kiểu chung chung có nghĩa là chúng ta có thể sử dụng nó với bất kỳ kiểu dữ liệu nào (Khi tạo, phải chỉ định các kiểu dữ liệu cho cả khóa và giá trị).

    Thí dụ: Dictionary<string, string> <NameOfDictionaryVar> = new Dictionary<string, string>();

  • Dictionay là một cách thực hiện an toàn kiểu Hashtable, Keys và Values được đánh máy mạnh mẽ.

Hashtable:

  • Nó trả về null nếu chúng ta cố gắng tìm một khóa không tồn tại.

  • Nó chậm hơn so với từ điển vì nó đòi hỏi quyền anh và unboxing.

  • Tất cả các thành viên trong Hashtable là chủ đề an toàn,

  • Hashtable không phải là loại chung,

  • Hashtable là cấu trúc dữ liệu được nhập sai, chúng ta có thể thêm khóa và giá trị của bất kỳ loại nào.


14
2018-05-28 07:53





Vì .NET Framework 3.5 cũng có một HashSet<T> cung cấp tất cả những ưu điểm của Dictionary<TKey, TValue> nếu bạn chỉ cần các phím và không có giá trị.

Vì vậy, nếu bạn sử dụng Dictionary<MyType, object> và luôn đặt giá trị thành null để mô phỏng loại bảng băm an toàn, bạn nên cân nhắc việc chuyển sang HashSet<T>.


14
2018-01-15 10:29