Basic Implementation of Hash Table in Python

Question

Basic impl of hash_table in python. Supports set, get, and delete. Uses open addressing with linear probing function. Any ideas would be greatly appreciated! Thanks!

class Entry: """ holds key, value pairs """ def __init__(self, key, value): self.key = key self.value = value self.is_deleted = False class Map(object): """ a basic, minimal implementation of a hash map """ def __init__(self): """ constructs a new Map """ self.table = [None] * 10 self.load_factor = .75 self.current_size = 0 def __setitem__(self, key, item): """ stores the key value combo in the table implements open addressing collision resolution """ entry = Entry(key, item) for i in range(len(self.table)): index = self.__get_hash_code(key, i) if self.table[index] is None or self.table[index].is_deleted: self.table[index] = entry self.current_size += 1 if float(self.current_size) / len(self.table) >= self.load_factor: self.__resize_table() break def __getitem__(self, key): """ gets the value associated with the key """ for i in range(len(self.table)): index = self.__get_hash_code(key, i) if self.table[index] is not None: if self.table[index].key == key: if self.table[index].is_deleted: raise KeyError('Key is not in the map') else: return self.table[index].value elif self.table[index] is None: raise KeyError('Key is not in the map') raise KeyError('Hmm something has gone wrong here') def __get_hash_code(self, key, value): return (hash(key) + value) % len(self.table) def __resize_table(self): new_table = [None] * (len(self.table) * 2) for i in range(len(self.table)): new_table[i] = self.table[i] self.table = new_table def delete(self, key): """ deletes a value from the hash table """ for i in range(len(self.table)): index = self.__get_hash_code(key, i) if self.table[index] is not None: if self.table[index].key == key: if self.table[index].is_deleted: raise KeyError('Key is not in the map') else: self.table[index].is_deleted = True self.current_size -= 1 break 

Answer 1

Your code looks generally quite good. I just have a few suggestions:

• Don't forget to define __str__() and __repr__() for each class
• I dislike the use of the "magic number" constants in the __init__() of the Hash_Map. They really ought to be either passed as parameters, read from a config somewhere, or clearly marked in a parameter section as pseudo-constants.
• The line for i in range(len(self.table)): appears multiple times. This style of loop is considered non-Pythonic. Python has the enumerate() built-in that returns a succession of tuples consisting of both the item and its index. I'd prefer for (i,item) in enumerate(self.table):
• If there's a clash, hash(key) will unnecessarily be called multiple times. Note that index = self.__get_hash_code(key, i) is called each time through the i loop, but the first thing it does is call hash(key) even though it may have already been computed. Better to compute hash(key) once outside the loop since it won't change.

• Multiple references to self.table[index]. The interpreter might be able to optimize them away, but the code will be shorter (and less error-prone) if it performs the lookup once and stores in a temp. (Or just use enumerate() like my previous suggestion)

• In def __get_hash_code(self, key, value): the third parameter is poorly named. It's not the value of the element, it's the linear probing parameter.

• There's a bug related to the interaction of __get_hash_code() and __resize_table() which can lead to \$O(n)\$ performance, defeating the purpose of using a hashtable.