CODEWITHSUNDEEP
pythondatabase
user5977290
user5977290

Reputation: 31

Hashtable explanation

class HashTable:
    def __init__(self):
        self.size = 11
        self.slots = [None] * self.size
        self.data = [None] * self.size

def put(self,key,data):
  hashvalue = self.hashfunction(key,len(self.slots))

  if self.slots[hashvalue] == None:
    self.slots[hashvalue] = key
    self.data[hashvalue] = data
  else:
    if self.slots[hashvalue] == key:
      self.data[hashvalue] = data  #replace
    else:
      nextslot = self.rehash(hashvalue,len(self.slots))
      while self.slots[nextslot] != None and \
                      self.slots[nextslot] != key:
        nextslot = self.rehash(nextslot,len(self.slots))

      if self.slots[nextslot] == None:
        self.slots[nextslot]=key
        self.data[nextslot]=data
      else:
        self.data[nextslot] = data #replace

I've been reading this bit of data structure on hashtable, and need explanation on this part below.

If key is already present, why is data being replaced?

if self.slots[hashvalue] == key:
  self.data[hashvalue] = data  #replace

Also, can someone explain this part? Nextslot would be empty slot. And we just rehash and if it's not empty and key is not present, rehash again?

  nextslot = self.rehash(hashvalue,len(self.slots))
  while self.slots[nextslot] != None and \
                  self.slots[nextslot] != key:
    nextslot = self.rehash(nextslot,len(self.slots))

Upvotes: 1

Views: 124

Answers (1)

Russel Simmons
Russel Simmons

Reputation: 361

If key is already present, why is data being replaced?

That's just how hash tables normally behave, because people usually want them to behave that way. Setting a key that is already present "overwrites" the previous value.

Also, can someone explain this part? Nextslot would be empty slot.

Nextslot is not guaranteed to be empty, it's just the next slot we're going to check. Think of it this way: As long as the slot we're checking is taken by a different key, we need to keep trying the next slot (which is picked by rehashing). If we find an empty slot, great, use it. If we find that the slot is taken but it's the same key, then overwrite it. So that loop keeps rehashing until it finds a slot that is empty OR a slot that has the same key (which we can overwrite).

Upvotes: 1

Related Questions