1

I am learning hash table in python and one question occurs here.

when hash function begins , I should generate a empty "map" hash the list.But why "nonempty slot already contains the key ,the odd data value is replaced with the new data value", isn't it should find the next empty slot and store there,why replace ?

https://interactivepython.org/runestone/static/pythonds/SortSearch/Hashing.html

hashfunction implements the simple remainder method. The collision resolution technique is linear probing with a “plus 1” rehash function. The put function (see Listing 3) assumes that there will eventually be an empty slot unless the key is already present in the self.slots. It computes the original hash value and if that slot is not empty, iterates the rehash function until an empty slot occurs. If a nonempty slot already contains the key, the old data value is replaced with the new data value. Dealing with the situation where there are no empty slots left is an exercise.

Tony Wang
  • 971
  • 4
  • 16
  • 33

2 Answers2

1

First, we need to differentiate between the hash value, key and value.

Hash value is the ID of the slot in the hash table and it is generated by the hash function.

Key is the data that you want to map from.

value is the data that you want to map to.

So, Mapping means that you have a unique key that refers to some value, and the values are not necessarily distinct.

When you try to add a new slot with key and value the put function will do the following:

It hashes the key to get the ID of the slot in the list and if the slot with this ID is empty, the insertion is done successfully, otherwise there are two paths:

1- The found slot is not empty but its key doesn't equal the new key, this means that 2 different keys had the same hash value, so this is considered collision and it is resolved by the ways mentioned in the link you sent.

2- The found slot is not empty but its key equals the new key, this means that you are updating this slot, so it will replace the old value with the new one.

Example: If the hash contains these slots:

"foo": 5
"bar": 7

Then you tried to insert hash["foo"] = 10, this will hash the key (foo) and find its slot ID in the hash table(list), and it will also find that there exists a slot with key foo, so it will replace the value and the hash table will become like this:

"foo": 10
"bar": 7

But if you tried to insert hash["abc"] = 7, this will hash the key abc, and if the hash value is mapping to a non-empty slot with a key different from abc, in this case the put function will consider this a collision and will try to find another empty slot.

khairy
  • 116
  • 3
0

Think Hash Table as the python dictionary. Suppose we created a dictionary

dictionary = {
    "a":10,
    "b":20,
}

Here "a" is the key and 10 is it's value. So if we update 

dictionary['a'] = 15

instead of putting it into a new slot it will update that position 'a'.

A python dictionary is an implementation of the hashtable. So I have given this example. So, for the same key, if it already exists, we update it.

To know more about how a python dictionary is implemented you can see this post

Adnan Sabbir
  • 181
  • 1
  • 13