How is the hash value of an object stored in a dictionary?

Question

Hey guys!

Friend of mine got asked the following question in an interview recently and im looking for a definitive answer for him.

How is the hash value of an object stored in a dictionary?

Cheers in advance!

Answer 1

Not all dictionaries work the same. I am going to assume you are referring to a hash table and specifically the Dictionary class. In that case the hash value is not stored anywhere in the data structure. It is only used to locate buckets. The specific implementation used maintains two arrays. One is for the buckets and one is for the entries. Items are always added to the next available slot in the entry array. The hash value has no influence on that whatsoever. The bucket array contains indexes into the entry array. The hash value is used to located the appropriate slot in the bucket array and then from there the index into the entry array can be extracted. The neat thing about this implementation is that enumerations of the Dictionary class are in temporal order (assuming of course there are no deletions followed by insertions). That, of course, is an implemenation detail that should never be relied upon, but it is an interesting artifact of the algorithm used.