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) -> 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 str(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) -> 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, 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):
 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):
 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
135    
136    def __len__(self):
137        """
138        Return the number of items in the hashtable.
139        """
140        return self.count
141    
142    def __getitem__(self, key):
143        """
144        Get the value associated with the key using indexing.
145
146        Args:
147            key: The key to look up.
148        Returns:
149            The value associated with the key.
150        """
151        return self.get(key)
152    
153    def __setitem__(self, key, value):
154        """
155        Set the value associated with the key using indexing.
156
157        Args:
158            key: The key to set.
159            value: The value to associate with the key.
160        """
161        self.set(key, value)
162
163    def __delitem__(self, key):
164        """
165        Delete the key-value pair associated with the key using indexing.
166
167        Args:
168            key: The key to delete.
169        """
170        self.delete(key)
171
172    def __contains__(self, key):
173        """
174        Check if the key exists in the hashtable using 'in' operator.
175
176        Args:
177            key: The key to check for existence.
178        Returns:
179            True if key exists, False otherwise.
180        """
181        return self.key_exists(key)
182    
183    def pop(self, key, default=None):
184        """
185        Remove specified key and return the value.
186        If key is not found, return default.
187        """
188        bucket = self.hash_function(key)
189        for i, kvpair in enumerate(self.array[bucket]):
190            if kvpair and kvpair[0] == key:
191                value = kvpair[1]
192                del self.array[bucket][i]
193                self.count -= 1
194                return value
195        return default