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 remove(self, key):
 99        """
100        Remove key-value pair if specified key is found. Raise KeyError if not found.
101
102        Args:
103            key: The key to check for.
104        Raises:
105            KeyError: If the key is not found in the hashtable.
106        """
107        bucket = self.hash_function(key)
108        for i in range(len(self.array[bucket])):
109            kvpair = self.array[bucket][i]
110            if kvpair and kvpair[0] == key:
111                del self.array[bucket][i]
112                self.count -= 1
113                return
114        raise KeyError(key)
115    
116    def __repr__(self):
117        """
118        Return a string representation of the hashtable.
119        """
120        s = "{"
121        pairs = []
122        for bucket in self.array:
123            if bucket:
124                for chain_link in bucket:
125                    pairs.append(f"{chain_link[0]}:{chain_link[1]}")
126        s += ", ".join(pairs)
127        return s + "}"
128
129    def show_buckets(self):
130        """
131        Return a string displaying the contents of all buckets in the hashtable.
132        """
133        s = ""
134        for i, bucket in enumerate(self.array):
135            s += f"Bucket {i}: {bucket}\n"
136        return s
137    
138    def __len__(self):
139        """
140        Return the number of items in the hashtable.
141        """
142        return self.count
143    
144    def __getitem__(self, key):
145        """
146        Get the value associated with the key using indexing.
147
148        Args:
149            key: The key to look up.
150        Returns:
151            The value associated with the key.
152        """
153        return self.get(key)
154    
155    def __setitem__(self, key, value):
156        """
157        Set the value associated with the key using indexing.
158
159        Args:
160            key: The key to set.
161            value: The value to associate with the key.
162        """
163        self.set(key, value)
164
165    def __delitem__(self, key):
166        """
167        Remove the key-value pair associated with the key using indexing.
168
169        Args:
170            key: The key to remove.
171        """
172        self.remove(key)
173
174    def __contains__(self, key):
175        """
176        Check if the key exists in the hashtable using 'in' operator.
177
178        Args:
179            key: The key to check for existence.
180        Returns:
181            True if key exists, False otherwise.
182        """
183        return self.key_exists(key)
184    
185    def pop(self, key, default=None):
186        """
187        Remove specified key and return the value.
188        If key is not found, return default.
189        """
190        bucket = self.hash_function(key)
191        for i, kvpair in enumerate(self.array[bucket]):
192            if kvpair and kvpair[0] == key:
193                value = kvpair[1]
194                del self.array[bucket][i]
195                self.count -= 1
196                return value
197        return default
198        
199    def enumerate(self):
200        """
201        Return the enumeration of key-value pairs in the hashtable.
202
203        Returns:
204            Enumeration of key-value pairs.
205        """
206        pairs = []
207        for bucket in self.array:
208            for chain_link in bucket:
209                pairs.append(chain_link)
210        return enumerate(pairs)
211    
212    def __eq__(self, other):
213        """
214        Compare this hashtable to another for equality.
215
216        Args:
217            other: The object to compare with.
218
219        Returns:
220            True if both are HashTable instances and their key-value pairs are equal, False otherwise.
221        """
222        if not isinstance(other, HashTable):
223            return False
224        def to_dict(ht):
225            d = {}
226            for bucket in ht.array:
227                for chain_link in bucket:
228                    d[chain_link[0]] = chain_link[1]
229            return d
230        return to_dict(self) == to_dict(other)
231    
232    def __iter__(self):
233        """
234        Iterate over all keys in the hashtable.
235        """
236        for bucket in self.array:
237            for chain_link in bucket:
238                yield chain_link[0]