dsa.hashtable

  1""" Module containing hash table class. """
  2
  3class HashTable:
  4    """ 
  5    A hashtable implementation. 
  6    """
  7    def __init__(self, capacity=20):
  8        """
  9        Initialize a hashtable with a given capacity.
 10
 11        Args:
 12            capacity: The capacity of the hashtable.
 13        """
 14        self.capacity = capacity
 15
 16        self.array = []
 17        for _ in range(self.capacity):
 18            self.array.append([])
 19
 20        #: the number of items in the hashtable
 21        self.count = 0
 22        
 23    def hash_function(self, key: str) -> int:
 24        """ 
 25        Return a hash value based on a given key. 
 26
 27        Args:
 28            key: The key to convert to a hashvalue.
 29        Returns:
 30            Hash value modded to the hashtable capacity.
 31        """
 32        mult = 31
 33        hash_val = 0
 34        for character in key:
 35            hash_val *= mult
 36            hash_val += ord(character)
 37            hash_val %= (2**32)
 38
 39        return hash_val % self.capacity
 40        
 41    def key_exists(self, key: str) -> bool:
 42        """ 
 43        Returns a Boolean on whether a key exists in the hashtable or not .
 44
 45        Args:
 46            key: The key to check for in the hashtable.
 47        Returns:
 48            Boolean of key existence.
 49        """
 50        bucket = self.hash_function(key)
 51        
 52        for e in self.array[bucket]:
 53            if e[0] == key:
 54                return True
 55        return False
 56
 57    def set(self, key: str, value):
 58        """ 
 59        Set a key-value pair in the hashtable.
 60
 61        If key exists, replace the value otherwise, create a new key-pair.
 62
 63        Args:
 64            key: The key to check for.
 65            value: The value to set or create.
 66        """
 67
 68        bucket = self.hash_function(key)
 69
 70        # linear searh for key 
 71        for e in self.array[bucket]:
 72            if e[0] == key:
 73                e[1] = value
 74                break
 75        else:
 76            self.array[bucket].append([ key, value ])
 77            self.count += 1
 78
 79    def get(self, key: str):
 80        """ 
 81        Get corresponding value of a given key in the hash table.
 82
 83        Args:
 84            key: The key to check for.
 85            value: The value to set or create.
 86        Returns:
 87            corresponding value of key.
 88            None if key is not found.
 89        """
 90        bucket = self.hash_function(key)
 91
 92        for e in self.array[bucket]:
 93            if e[0] == key:
 94                return e[1]
 95
 96        return None
 97
 98    def delete(self, key: str):
 99        """ 
100        Delete key-value pair if specified key is found. 
101
102        Args:
103            key: The key to check for.
104        """
105        bucket = self.hash_function(key)
106
107        for i in range(len(self.array[bucket])):
108            kvpair = self.array[bucket][i]
109            if kvpair and kvpair[0] == key:
110                del self.array[bucket][i]
111                self.count -= 1
112                break
113    
114    def __repr__(self):
115        """
116        Return a string representation of the hashtable.
117        """
118        s = "{"
119        pairs = []
120        for bucket in self.array:
121            if bucket:
122                for chain_link in bucket:
123                    pairs.append(f"{chain_link[0]}:{chain_link[1]}")
124        s += ", ".join(pairs)
125        return s + "}"
126
127    def show_buckets(self):
128        """
129        Return a string displaying the contents of all buckets in the hashtable.
130        """
131        s = ""
132        for i, bucket in enumerate(self.array):
133            s += f"Bucket {i}: {bucket}\n"
134        return s