hash table , nonempty slot already contains the key ,the odd data value is replaced with the new data value
<p>I am learning hash table in python and one question occurs here.</p>

<p>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 ?</p>

<p><a href="https://interactivepython.org/runestone/static/pythonds/SortSearch/Hashing.html" rel="nofollow">https://interactivepython.org/runestone/static/pythonds/SortSearch/Hashing.html</a></p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>First, we need to differentiate between the <code>hash value</code>, <code>key</code> and <code>value</code>.</p>

<p><code>Hash value</code> is the ID of the slot in the hash table and it is generated by the hash function.</p>

<p><code>Key</code> is the data that you want to map from.</p>

<p><code>value</code> is the data that you want to map to.</p>

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

<p>When you try to add a new slot with <code>key</code> and <code>value</code> the put function will do the following:</p>

<p>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:</p>

<p>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 <code>hash value</code>, so this is considered collision and it is resolved by the ways mentioned in the link you sent.</p>

<p>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 <code>value</code> with the new one.</p>

<p>Example:
If the hash contains these slots:</p>

<pre><code>"foo": 5
"bar": 7
</code></pre>

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

<pre><code>"foo": 10
"bar": 7
</code></pre>

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

python data-structures hash hashmap hashtable