#!/usr/bin/Python # ============================================================== # hash (single list) # ============================================================== import sys import random VERBOSE = False # -------------------------------------------------------------- # ---- create/initialize a hash list # -------------------------------------------------------------- def create_initial_hash_list(hash_list_length, hash_list_initial_value=None): return [hash_list_initial_value]*hash_list_length # -------------------------------------------------------------- # ---- insert value into the hash list # ---- return True if successful and False if not # -------------------------------------------------------------- def insert_into_hash(value,hash_list): if VERBOSE: print(f'insert {value}') # ---- length of hash list list_len = len(hash_list) # ---- calculate a hash key for the value hash_key = abs(value) % list_len key = hash_key # copy the value's hash key # ---- try to save the value while True: # ---- is the bucket empty? # ---- save the value, return true if hash_list[key] is None: hash_list[key] = value return True # ---- increment the key and try again key = (key + 1) % list_len if key == hash_key: break # end of list? return False # failure # -------------------------------------------------------------- # ---- delete a value from the hash list # ---- return True if successful and False if not # -------------------------------------------------------------- def delete_from_hash(value,hash_list): if VERBOSE: print(f'delete {value}') # ---- length of hash list list_len = len(hash_list) # ---- calculate a hash key for the value hash_key = abs(value) % list_len key = hash_key # copy the value's hash key # ---- try to find the value and delete it while True: # ---- delete value matches bucket value? if hash_list[key] == value: # ---- assumes empty bucket equals None hash_list[key] = None return True # ---- increment the key and try again key = (key + 1) % list_len if key == hash_key: break # end of list? return False # failure # -------------------------------------------------------------- # ---- search the hash list for a value # ---- return True if successful and False if not # -------------------------------------------------------------- def search_hash(value,hash_list): if VERBOSE: print(f'search for {value}') # ---- length of hash list list_len = len(hash_list) # ---- calculate a hash key for the value hash_key = abs(value) % list_len 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 hash_list[key] == value: return True # ---- increment the key and try again key = (key + 1) % list_len if key == hash_key: break # end of list? return False # failure # -------------------------------------------------------------- # ---- display the hash list # ---- (only display buckets with data) # -------------------------------------------------------------- def display_hash(hash_list,title=None): if title is None: print() else: print(title) for idx in range(0,len(hash_list)): if hash_list[idx] is not None: print(f'[{idx:2}] {hash_list[idx]}') # -------------------------------------------------------------- # ---- main # -------------------------------------------------------------- if __name__ == '__main__': # ---------------------------------------------------------- # ---- create/initialize hash list hash_length = 10 hash_list = create_initial_hash_list(hash_length) # ---------------------------------------------------------- # ---- insert six random integer values into the hash list for _ in range(6): value = random.randint(-440,440) tf = insert_into_hash(value,hash_list) 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 = insert_into_hash(special_value,hash_list) if not tf: print(f'insert into hash error ({special_value})') sys.exit() display_hash(hash_list,'---- after insert ----') print() # ---------------------------------------------------------- # ---- search for a hash value in the hash list tf = search_hash(special_value,hash_list) if tf: print(f'value found ({special_value})') else: print(f'value not found ({special_value})') display_hash(hash_list,'---- after search ----') print() # ---------------------------------------------------------- # ---- delete a hash value from the hash list tf = delete_from_hash(special_value,hash_list) if tf: print(f'value deleted ({special_value})') else: print(f'value not deleted ({special_value})') display_hash(hash_list,'---- after delete ----') print()