#!/usr/bin/Python
# ==============================================================
# hash object (single list)
# ==============================================================
import sys
import random
# --------------------------------------------------------------
# ---- class definition: hash table
# --------------------------------------------------------------
class HashTable:
# ----------------------------------------------------------
# ---- initilize hash table
def __init__(self,length):
self.hash_list = [None]*length
self.length = length
self.verbose = False
# ----------------------------------------------------------
# ---- insert a value into the hash table
# ---- return True if successful and False if not
def insert(self,value):
if self.verbose: print(f'insert {value}')
# ---- calculate a hash key for the value
hash_key = abs(value) % self.length
key = hash_key # copy the value's hash key
# ---- insert the value into the hash table
while True:
# ---- is the bucket empty?
# ---- save the value, return true
if self.hash_list[key] is None:
self.hash_list[key] = value
return True
# ---- can not insert value
# ---- increment the key and try again
key = (key + 1) % self.length
if key == hash_key: break # end of hash table?
return False # failure
# ----------------------------------------------------------
# ---- delete a value from the hash table
# ---- return True if successful and False if not
def delete(self,value):
if self.verbose: print(f'delete {value}')
# ---- calculate a hash key for the value
hash_key = abs(value) % self.length
key = hash_key # copy the value's hash key
# ---- try to find the value and delete it
while True:
# ---- delete value matches bucket value?
# ---- delete value, return true
if self.hash_list[key] == value:
self.hash_list[key] = None
return True
# ---- no match found
# ---- increment the key and try again
key = (key + 1) % self.length
if key == hash_key: break # end of hash table?
return False # failure
# ----------------------------------------------------------
# ---- search the hash list for a value
# ---- return True if successful and False if not
def search(self,value):
if self.verbose: print(f'search for {value}')
# ---- calculate a hash key for the value
hash_key = abs(value) % self.length
key = hash_key # copy the value's hash key
# ---- try to find the value
while True:
# ---- value matches the bucket's value?
# ---- return True
if self.hash_list[key] == value: return True
# ---- no match found
# ---- increment the key and try again
key = (key + 1) % self.length
if key == hash_key: break # end of hash table?
return False # failure
# ----------------------------------------------------------
# ---- display the hash list
# ---- (only display buckets with data)
def display(self,title=None):
if title is None: print()
else: print(title)
for idx in range(0,len(self.hash_list)):
if self.hash_list[idx] is not None:
print(f'[{idx:2}] {self.hash_list[idx]}')
# ----------------------------------------------------------
# ---- toggle verbose flag
def verbose_flag(self):
if self.verbose: self.vebose = False
else: self.vebose = True
# --------------------------------------------------------------
# ---- main
# --------------------------------------------------------------
if __name__ == '__main__':
# ----------------------------------------------------------
# ---- create/initialize hash table
hash_length = 10
hash = HashTable(hash_length)
hash.verbose_flag()
# ----------------------------------------------------------
# ---- insert six random integer values into the hash table
for _ in range(6):
value = random.randint(-440,440)
tf = hash.insert(value)
if not tf:
print(f'insert into hash error ({value})')
sys.exit()
# ----------------------------------------------------------
# ---- insert a special value so I can test
# ---- the delete and search functions
special_value = 101010
tf = hash.insert(special_value)
if not tf:
print(f'insert into hash error ({special_value})')
sys.exit()
hash.display('---- after insert ----')
print()
# ----------------------------------------------------------
# ---- search for a hash value in the hash list
tf = hash.search(special_value)
if tf:
print(f'value found ({special_value})')
else:
print(f'value not found ({special_value})')
hash.display('---- after search ----')
print()
# ----------------------------------------------------------
# ---- delete a hash value from the hash list
tf = hash.delete(special_value)
if tf:
print(f'value deleted ({special_value})')
else:
print(f'value not deleted ({special_value})')
hash.display('---- after delete ----')
print()