Hash table implementation in Python

Question

I wrote an implementation of a hash table in Python.
This implementation uses chaining for handling collisions, based on lists.
I also use an expansion/shrink factor of 2.
The expansion is done when the amount of key entries is bigger than the amount of slots from the hash table. Shrinking is done when the amount fo key entries is 1/4 of the total amount of slots.
*slots -> the main list where the hashing indexing is performed.

Here is my implementation:

class HashTable:
    """
    Hash table data structure implementation.
    This implementation uses chaining for collision resolution.
    This data structure basically receives a pair (key, value) 
    and add it to the hash tabel structure.
    """
    MIN_SIZE = 8

    def __init__(self, hashing_function='division'):
        self._size = self.MIN_SIZE
        self._slots = [[] for _ in range(self._size)]
        self._hashing_function = hashing_function
        self._len = 0

    def _hash(self, key):
        """
        Applies hashing process to a given key and return an index 
        from the table slots. This is done in two steps :
        1. Checks if the key is a string and returns the equivalent 
        sum of its ASCII values.
        2. Applies the key hashing to an index in the slots range
        """
        key = sum(ord(c) for c in key) if type(key) is str else key
        return {
            'division': lambda: key % self._size
        }.get(self._hashing_function, lambda: None)()

    def get(self, key, default=None):
        """
        Returns the value for given key if the key exists, 
        else returns default value.
        Default value is None if not specified.
        """
        index = self._hash(key)
        slot = self._slots[index]
        for pair in slot:
            return pair[1] if pair[0] == key else default

    def exist(self, key):
        """
        Check if key already exists inside the hash table.
        """
        index = self._hash(key)
        slot = self._slots[index]
        return key in dict(slot)

    def put(self, key, value):
        """
        Inserts a key and value pair inside the hash table.
        The collisions are ignored as a chaining approach is taken.
        Repeated keys can not be added.
        """
        if not self.exist(key):
            index = self._hash(key)
            self._slots[index].append((key,value))
            self._len += 1
            if self._len > self._size:
                self._expand()

    def remove(self, key, default=None):
        """
        Removes and returns a given key value and its associated value pair.
        If given key is not found, the given default value is returned.
        If default value is not provided, None is returned.
        """
        index = self._hash(key)
        slot = self._slots[index]
        pop_index = None
        for i in range(len(slot)):
            if slot[i][0] == key: pop_index = i
        if pop_index is not None:
            removed_pair = slot.pop(pop_index)
            self._len -= 1
            # If the amount of entries is 1/4 of the total amount of slots and
            # the total amount of slots is greater then the minimun size, than
            # a shirnking is applied ot the hash table
            if self._len == self._size/4 and self._size > self.MIN_SIZE:
                self._shrink()
            return removed_pair
        else:
            return default

    def _expand(self):
        """
        Expands the slots capacity from the hash table, applying a 
        rehash on all (key, value) pairs to match the new size of the
        hash table.
        Applied when number of key entries is bigger than the amount of slots.
        """
        temp_slots = []
        for slot in self._slots:
            temp_slots += slot

        self._size *= 2
        self._len = 0
        self._slots = [[] for _ in range(self._size)]

        for pair in temp_slots:
            self.put(pair[0], pair[1])

    def _shrink(self):
        """
        Shrinks the slots capacity from the hash table, applying a 
        rehash on all (key, value) pairs to match the new size of the
        hash table.
        Applied when number of key entries is 1/4 of the amount of slots.
        """
        temp_slots = []
        for slot in self._slots:
            temp_slots += slot

        self._size //= 2
        self._len = 0
        self._slots = [[] for _ in range(self._size)]

        for pair in temp_slots:
            self.put(pair[0], pair[1])

Please, fell free to do any kind of comments about performance, a more pythonic way of doing something or anything else! :)

Answer 1

Here's one suggestion related to usability. Say I want to make this code work:

h = HashTable()
h.put('hello', 'world')
h.put((1,2), (3, 4))
h.put(95.7, 76.2)

I have to define a custom hash function to handle the tuples and floats as keys. The only way I can add a custom hash function, however, is to modify your hash table code and add it to the map in the body of the _hash method. That means I can't just use your code; I have to be able to modify it to customize it.

The custom hash function I would write would look something like this:

def custom_hash():
    if type(key) is tuple:
        # turn tuple into integer
    elif type(key) is float:
        # turn float into integer
    # Otherwise the key has already been converted
    return key % self._size

I have to add another case to my conditional every time I need to support a new type as key. Suppose I want to use dates as keys, or booleans, or named tuples, or some new class I define. This function could turn really long and ugly after a while.

The built-in Python dictionary avoids this by having objects which can be used as keys implement a __hash__ method as described at https://stackoverflow.com/a/8998010/3376926. Then your _hash method becomes this:

def _hash(key):
    return key.__hash__() % self._size

The key itself has logic to convert itself into an integer that your code doesn't need to know anything about, and I can add all the new key types I want without needing to modify your source.