标签云

微信群

扫码加入我们

WeChat QR Code

In most programming languages, dictionaries are preferred over hashtables.What are the reasons behind that?


> This is not necessarily true. A hash table is an implementation of a dictionary. A typical one at that, and it may be the default one in .NET, but it's not by definition the only one. I'm not sure that this is required by the ECMA standard, but the MSDN documentation very clearly calls it out as being implemented as a hashtable. They even provide the SortedList class for times when an alternative is more reasonable.

2019年06月25日46分28秒

Promit I always thought the Dictionary was an implementation of the Hashtable.

2019年06月25日46分28秒

I think the reason is, that in a dictionary you can define the type of the key and the value for your selfe. the Hashtable can only take objects and saves the pairs based on the hash (from object.GetHashCode() ).

2019年06月25日46分28秒

Dan Your claim is quite mistaken ... a hash table only contains one instance of each key, and a search never yields multiple entries; if you want to associate multiple values with each key, make the hash table value a list of values. There's no such data structure as "a Dictionary" ... Dictionary is simply the name that some libraries use for their hash table. e.g., C#'s non-generic hash table is called HashTable. When they added generics to the language, they called the generic version Dictionary. Both are hash tables.

2019年06月25日46分28秒

Dan Your claim is mistaken ... a hash table (en.wikipedia.org/wiki/Hash_table) is a particular implementation of a dictionary, aka an associative array (en.wikipedia.org/wiki/Associative_array), and, being a dictionary, only contains one instance of each key, and a search never yields multiple entries; if you want to associate multiple values with each key, make the hash table value a list of values. And the .NET Dictionary and Hashtable classes are both hash tables.

2019年06月25日46分28秒

And also generic collections are a lot faster as there's no boxing/unboxing

2019年06月25日46分28秒

Not sure about a Hashtable with the above statement, but for ArrayList vs List<t> it's true

2019年06月25日46分28秒

Hashtable uses Object to hold things internally (Only non-generic way to do it) so it would also have to box/unbox.

2019年06月25日46分28秒

BrianJ: A "hash table" (two words) is the computer science term for this kind of structure; Dictionary is a specific implementation. A HashTable corresponds roughly to a Dictionary<object,object> (though with slightly different interfaces), but both are implementations of the hash table concept. And of course, just to confuse matters further, some languages call their hash tables "dictionaries" (e.g. Python) - but the proper CS term is still hash table.

2019年06月25日46分28秒

BrianJ: Both HashTable (class) and Dictionary (class) are hash tables (concept), but a HashTable is not a Dictionary, nor is a Dictionary a HashTable. They are used in very similar fashions, and Dictionary<Object,Object> can act in the same untyped manner that a HashTable does, but they do not directly share any code (though parts are likely to be implemented in a very similar fashion).

2019年06月25日46分28秒

We can use concurrentDictionary(in .NET 4.0) for threadsafe.

2019年06月25日46分28秒

Guillaume86, this is why you use TryGetValue instead msdn.microsoft.com/en-us/library/bb347013.aspx

2019年06月25日46分28秒

+1 for StringDictionary...btw StringDictionary isn't the same as Dictionary<string, string> when you use the default constructor.

2019年06月25日46分28秒

The ParallelExtensionsExtras code.msdn.microsoft.com/windowsdesktop/… contains an ObservableConcurrentDictionary which is great fir binding as well as concurrency.

2019年06月25日46分28秒

awesome explanation, it's really nice you also listed the similarities to lessen the questions that might comes to one's mind

2019年06月26日46分28秒

Fun. The Dictionary<T> source code looks a lot cleaner and faster.It might be better to use Dictionary and implement your own synchronization.If the Dictionary reads absolutely need to be current, then you'd simply have to synchronize access to the read/write methods of the Dictionary.It would be a lot of locking, but it would be correct.

2019年06月25日46分28秒

Alternatively, if your reads don't have to be absolutely current, you could treat the dictionary as immutable.You could then grab a reference to the Dictionary and gain performance by not synchronizing reads at all (since it's immutable and inherently thread-safe).To update it, you construct a complete updated copy of the Dictionary in the background, then just swap the reference with Interlocked.CompareExchange (assuming a single writing thread; multiple writing threads would require synchronizing the updates).

2019年06月25日46分28秒

.Net 4.0 added the ConcurrentDictionary class which has all public/protected methods implemented to be thread-safe.If you don't need to support legacy platforms this would let you replace the Hashtable in multithreaded code: msdn.microsoft.com/en-us/library/dd287191.aspx

2019年06月26日46分28秒

anonymous to the rescue. Cool answer.

2019年06月26日46分28秒

I recall reading that HashTable is only reader-writer thread-safe in the scenario where information is never deleted from the table.If a reader is asking for an item which is in the table while a different item is being deleted, and the reader would to look in more than one place for the item, it's possible that while the reader is searching the writer might move the item from a place which hasn't been examined to one which has, thus resulting in a false report that the item does not exist.

2019年06月25日46分28秒

MS docs say: "Retrieving a value by using its key is very fast, close to O(1), because the Dictionary <(Of <(TKey, TValue >)>) class is implemented as a hash table." - so you should be guaranteed a hashtable when dealing with Dictionary<K,V>. IDictionary<K,V> could be anything, though :)

2019年06月25日46分28秒

rix0rrr - I think you've got that backwards, a Dictionary uses a HashTable not a HashTable uses a Dictionary.

2019年06月25日46分28秒

JosephHamilton - rix0rrr got it right: "A hash table is an implementation of a dictionary." He means the concept "dictionary", not the class (note the lower case). Conceptually, a hash table implements a dictionary interface. In .NET, Dictionary uses a hash table to implement IDictionary. It's messy ;)

2019年06月25日46分28秒

I was talking about in .NET, since that's what he referenced in his response.

2019年06月25日46分28秒

JosephHamilton: implements (or implementation of) does not even remotely mean the same thing as uses. Quite the opposite. Perhaps it would have been clearer if he said it slightly differently (but with the same meaning):"a hash table is one way to implement a dictionary". That is, if you want the functionality of a dictionary, one way to do that (to implement the dictionary), is to use a hashtable.

2019年06月25日46分28秒

instead of explicitly assigning the datatype for KeyValuePair, we could use var. So, this would reduce typing - foreach (var kv in dt)...just a suggestion.

2019年06月26日46分28秒

"It returns/throws Exception if we try to find a key which does not exist." Not if you use Dictionary.TryGetValue

2019年06月26日46分28秒

Can you fix that MSDN quote? Something is missing or wrong; it is not grammatical and somewhat incomprehensible.

2019年06月25日46分28秒

We can use generic lists (List<string>) in soap based web service. But, we cannot use dictionary (or hashtable) in a webservice. I think the reason for this is that the .net xmlserializer cannot handle dictionary object.

2019年06月25日46分28秒

"Some thread safety" is not the same as "Thread safety"

2019年06月26日46分28秒

One of the advantages of a hashtable over a dictionary is that if a key does not exist in a dictionary, it will throw an error. If a key does not exist in a hashtable, it just returns null.

2019年06月25日46分28秒

In C# I would still avoid using System.Collections.Hashtable as they don't have the advantage of generics.You can use Dictionary's TryGetValue or HasKey if you don't know if the key will exist.

2019年06月25日46分28秒

Whoops, not HasKey, it should be ContainsKey.

2019年06月26日46分28秒

System.Collections.Generic.Dictionary<TKey,TValue> doesn't derive from DictionaryBase.

2019年06月26日46分28秒

"So we can be sure that DictionaryBase uses a HashTable internally." -- That's nice, but it has nothing to do with the question.

2019年06月26日46分28秒