15

I have some hashtable. For instance I have two entities like

john = { 1stname: jonh, 2ndname: johnson }, eric = { 1stname: eric, 2ndname: ericson }

Then I put them in hashtable:

ht["john"] = john; ht["eric"] = eric;

Let's imagine there is a collision and hashtable use chaining to fix it. As a result there should be a linked list with these two entities like thisenter image description here How does hashtable understand what entity should be returned for key? Hash values are the same and it knows nothing about entities structure. For instance if I write thisvar val = ht["john"]; how does hashtable (having only key value and its hash) find out that value should be john record and not eric.

Improve this question
1
  • take a look at this Commented Jan 17, 2017 at 12:38

2 Answers 2

Reset to default
25

I think what you are confused about is what is stored at each location in the hashtable's adjacent list. It seems like you assume that only the value is being stored. In fact, the data in each list node is a tuple (key, value).

Once you ask for ht['john'], the hashtable find the list associated with hash('john') and if the list is not empty it searches for the key 'john' in the list. If the key is found as the first element of the tuple then the value (second element of the tuple) is returned. If the key is not found, then it means that the element is not in the hashtable.

To summarize, the key hash is used to quickly identify the cell in which the element should be stored if present. Actual key equality is tested for to decide whether the key exists or not.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

How does key equality work in case of complex objects? Value in hashtable is an object with different properties but you use only key to get it. Hashtable doesn't know about object structure and what property of this object I use as key.
Looks like i've got it. I suppose hash table should keep full key together with entire object to define whether this key equals required key, right?
As I mentioned in the answer, the key is stored along with the object in the hashtable: (key, value). In your case the key is part of the value but that isn't always the case. So the hashtable doesn't care about your value at all until the moment it finds the key you search for. Then it returns the value associated without analyzing it in any way.
Additionally I started to read source code of c# dictionary and I see it keeps key together with value internally.
2

Is this what you are asking for? I have already put this in comments but seems to me you did not follow link

Collision Resolution in the Hashtable Class

Recall that when inserting an item into or retrieving an item from a hash table, a collision can occur. When inserting an item, an open slot must be found. When retrieving an item, the actual item must be found if it is not in the expected location. Earlier we briefly examined two collusion resolution strategies:

  • Linear probing
  • Quardratic probing

The Hashtable class uses a different technique referred to as rehasing. (Some sources refer to rehashing as double hashing.)

Rehasing works as follows: there is a set of hash different functions, H1 ... Hn, and when inserting or retrieving an item from the hash table, initially the H1 hash function is used. If this leads to a collision, H2 is tried instead, and onwards up to Hn if needed. The previous section showed only one hash function, which is the initial hash function (H1). The other hash functions are very similar to this function, only differentiating by a multiplicative factor. In general, the hash function Hk is defined as:

Hk(key) = [GetHash(key) + k * (1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1)))] % hashsize

Mathematical Note With rehasing it is important that each slot in the hash table is visited exactly once when hashsize number of probes are made. That is, for a given key you don't want Hi and Hj to hash to the same slot in the hash table. With the rehashing formula used by the Hashtable class, this property is maintained if the result of (1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1))and hashsize are relatively prime. (Two numbers are relatively prime if they share no common factors.) These two numbers are guaranteed to be relatively prime if hashsize is a prime number. Rehasing provides better collision avoidance than either linear or quadratic probing.

sources here

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.