Skip to content

Instantly share code, notes, and snippets.

@scwood
Last active March 15, 2023 16:20
Show Gist options
  • Save scwood/b9a106b1450bfa67b1d5860b91a64c96 to your computer and use it in GitHub Desktop.
Save scwood/b9a106b1450bfa67b1d5860b91a64c96 to your computer and use it in GitHub Desktop.
python hash table using linear probing
class HashTable(object):
def __init__(self):
self.max_length = 8
self.max_load_factor = 0.75
self.length = 0
self.table = [None] * self.max_length
def __len__(self):
return self.length
def __setitem__(self, key, value):
self.length += 1
hashed_key = self._hash(key)
while self.table[hashed_key] is not None:
if self.table[hashed_key][0] == key:
self.length -= 1
break
hashed_key = self._increment_key(hashed_key)
tuple = (key, value)
self.table[hashed_key] = tuple
if self.length / float(self.max_length) >= self.max_load_factor:
self._resize()
def __getitem__(self, key):
index = self._find_item(key)
return self.table[index][1]
def __delitem__(self, key):
index = self._find_item(key)
self.table[index] = None
def _hash(self, key):
# TODO more robust
return hash(key) % self.max_length
def _increment_key(self, key):
return (key + 1) % self.max_length
def _find_item(self, key):
hashed_key = self._hash(key)
if self.table[hashed_key] is None:
raise KeyError
if self.table[hashed_key][0] != key:
original_key = hashed_key
while self.table[hashed_key][0] != key:
hashed_key = self._increment_key(hashed_key)
if self.table[hashed_key] is None:
raise KeyError
if hashed_key == original_key:
raise KeyError
return hashed_key
def _resize(self):
self.max_length *= 2
self.length = 0
old_table = self.table
self.table = [None] * self.max_length
for tuple in old_table:
if tuple is not None:
self[tuple[0]] = tuple[1]
@Dhanushreddy09
Copy link

I have a small question. Please answer if you could , I just manipulated the above code by removing load factor regarding code. It is working fine for one successive linear probe but not from second probe and it isn't even completing the whole process. This is my code
`class HashTable(object):
def init(self):
self.max_length=11
self.table = [None]*self.max_length
self.length=0

def length(self):
    return self.length

def get_item(self,key):
    index=self.find_item(key)
    return self.table[index][1]
    

def store(self,key,value):
    self.length+=1
    hv=self.calculate_hash(key)
    while self.table[hv] is not None:
        if self.table[hv][0]==key:
            self.length-=1
            print("Entered key already exists")
            break
        hv=self.increment(key)
    key_value=(key,value)
    self.table[hv]=key_value  
    
def calculate_hash(self,key):
    return hash(key) % self.max_length

def increment(self,key):
    hv= (key+1) % self.max_length
    if hv==self.max_length:
        hv=0
    return hv

def find_item(self,key):
    hv=self.calculate_hash(key)
    if self.table[hv] is None:
        raise KeyError
    while self.table[hv][0]!=key:
        hv=self.increment(hv)
    return hv

def delete(self,key):
    self.length-=1
    index=self.find_item(key)
    while index is None:
        self.length+=1
        break
    self.table[index]=None

hash_table=HashTable()

#1st test case
hash_table.store(11804562,"Dhanush")
print(hash_table.find_item(11804562))
print(hash_table.get_item(11804562))

#2nd
hash_table.store(11804573,"Sravan")
print(hash_table.find_item(11804573))
print(hash_table.get_item(11804573))

#3rd
hash_table.store(11804584,"Omeswar")
print(hash_table.length)
#print(hash_table.find_item(11804584))
#print(hash_table.get_item(11804584))`
The hash_value of three keys in above test cases is zero, It is working for 2nd test case but not for 3rd. Once try to run ,debug and give me some feedback regarding that.
Thanks in advance !

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment