Hash table in Python

Question

class HashTable:
    '''
    Only supports integers as keys right now.  
    Values cannot be None, obviously.  
    Every operation is theoretically most efficient.
    Uses probing as collision resolution strategy.
    '''

    def __init__(self, init_size=8, load_factor_max=0.75):
        # A hash table entry will be of the form <key, value, hash, reverse_index>.
        # Hash is stored just to facilitate quicker comparison matching while finding the key.
        # That last part `reverse_index` is the index in `used_slot_indices` corresponding to this entry.
        # Start with 8 elements, because that is what happens in the official Python dict.
        self.table = [None] * init_size
        self.num_entries = 0
        self.load_factor_max = load_factor_max

        # A **contiguous** list storing the slot indices of all the used entries in the table.
        # The reason why we are maintaining this is because we want hash table iteration to be fast.
        # The hash table array itself has a lot of Dummy/None values, but this list will
        # store that info contiguously.
        # Its actual length will always be equal to the number of new entries done.
        # But when some entries are removed, it will have some `None` values at the end.
        # The number of non-None entries will always be equal to `self.num_entries`.
        # If the hash table has the data [None, 1104, None, None, 5121, None], then this array
        # will be [1, 4] indicating the 0-indexed slot indices of the keys 1104 and 5121 respectively.
        self.used_slot_indices = []
        # Do not modify this; its a constant.
        self.DUMMY_ENTRY = ()
        ### Important Note: All the fields defined here should be handled in `self._copy_from_other()`.

    def __str__(self):
        ret_value = ''
        for idx, entry in enumerate(self.table):
            ret_value += '{}. {}\n'.format(idx, entry)
        return ret_value

    def size(self):
        return self.num_entries

    def get_entries(self):
        '''
        Returns the list of entries present in the hash table.  
        Does not preserve the insertion order. 
        '''
        entries = []
        for num_entry in range(self.num_entries):
            used_slot_index = self.used_slot_indices[num_entry]
            entry = self.table[used_slot_index]
            entries.append(entry)
        return entries

    def _compute_hash(self, key):
        return key % len(self.table)

    def _increment_probe_index(self, probe_index):
        '''
        Will return all values in the range `[0, len(self.table)]` exactly once.
        '''
        return ((5 * probe_index) + 1) % len(self.table)

    def _get_key_slot_index(self, key):
        '''
        Get the slot index in the table array where the key is present / ready-to-be-inserted.
        '''
        index = self._compute_hash(key)
        original_hash = index
        dummy_index = None
        current_probe_length = 0
        # Start probing...
        while True:
            current_probe_length += 1
            entry = self.table[index]
            if entry is None:
                # Found an empty slot, which means the key is absent.
                # Return dummy if possible, so that it will be used to insert any new entry when
                # called by `self.put()`
                return dummy_index or index
            if entry == self.DUMMY_ENTRY:
                # Save the slot index of the first dummy found.
                dummy_index = dummy_index or index
            # Comparing the hash first to avoid unnecessary key object comparisons which are costly
            elif entry[2] == original_hash and entry[0] == key:
                # Found the key!
                return index
            if current_probe_length > len(self.table):
                # Looked at all the slots, no need of proceeding further
                # This should never occur theoretically!!
                raise Exception("Hash table full!!")
            index = self._increment_probe_index(index)

    def _resize_if_needed(self):
        load_factor = (self.size() * 1.0) / len(self.table)
        if load_factor < self.load_factor_max:
            return
        # Just make a bigger hash table and copy all the entries.
        ht_bigger = HashTable(len(self.table) * 2, self.load_factor_max)
        for entry in self.get_entries():
            ht_bigger.put(entry[0], entry[1])
        self._copy_from_other(ht_bigger)

    def _copy_from_other(self, other_hash_table):
        '''
        Copy all the data from another hash table.
        '''
        self.table = other_hash_table.table
        self.num_entries = other_hash_table.num_entries
        self.load_factor_max = other_hash_table.load_factor_max
        self.used_slot_indices = other_hash_table.used_slot_indices

    def get(self, key):
        slot_index = self._get_key_slot_index(key)
        entry = self.table[slot_index]
        if entry and entry != self.DUMMY_ENTRY:
            return entry[1]
        return None

    def put(self, key, value):
        key_hash = self._compute_hash(key)
        new_entry = None
        slot_index = self._get_key_slot_index(key)
        if not self.table[slot_index]:
            # It is either None or Dummy
            # Adding a new key
            if len(self.used_slot_indices) == self.num_entries:
                # Expand the used_slot_indices list
                self.used_slot_indices.append([])
            # A new reverse-index value will always go at the end
            reverse_index = self.num_entries
            new_entry = (key, value, key_hash, reverse_index)
            self.used_slot_indices[reverse_index] = slot_index
            self.num_entries += 1
        else:
            # An entry is already present for the key. So overwrite...
            # Just change the value part. Rest of the tuple is same as the entry being overwritten.
            new_entry = (key, value, key_hash, self.table[slot_index][3])
        self.table[slot_index] = new_entry
        self._resize_if_needed()
        return value

    def _remove_from_used_slot_indices(self, entry):
        '''
        Removes the reverse index of the entry.
        It just copies the last non-None value in `used_slot_indices` to the reverse index,
        thus maintaining the coniguous property.
        '''
        # The index of this entry in `used_slot_indices`
        reverse_index = entry[3]
        if reverse_index == self.num_entries - 1:
            # If this is already the reverse index, then just make it None and return.
            self.used_slot_indices[reverse_index] = None
            return
        # Bring the last non-None value present in `used_slot_indices` to this place.
        self.used_slot_indices[reverse_index] = self.used_slot_indices[
            self.num_entries - 1]
        # Update the `reverse_index` part of the entry pointed to by the last
        # non-None value.
        # The slot index of the entry described above.
        slot_index = self.used_slot_indices[reverse_index]
        entry = self.table[slot_index]
        self.table[slot_index] = (entry[0], entry[1], entry[2], reverse_index)
        # Mark the last reverse index position as empty.
        self.used_slot_indices[self.num_entries - 1] = None

    def remove(self, key):
        slot_index = self._get_key_slot_index(key)
        if not self.table[slot_index]:
            raise KeyError('Key "{}" not found'.format(key))
        entry = self.table[slot_index]
        self.table[slot_index] = self.DUMMY_ENTRY
        self._remove_from_used_slot_indices(entry)
        self.num_entries -= 1


def main():
    ht = HashTable()
    ht.put(1, 2)
    ht.put(9, 3)
    ht.put(17, 5)
    ht.remove(9)
    print(ht.get(17))
    ht.put(7, 10)
    ht.put(0, 11)
    ht.put(8, 10)
    ht.put(10, 10)
    ht.remove(17)
    ht.put(1, 3)
    ht.put(11, 12)
    ht.put(100, 3)
    ht.put(201, 12)
    ht.put(200, 12)
    print(ht.get_entries())


if __name__ == "__main__":
    main()

I would be grateful if I could get feedback about any of these or otherwise:

• Correctness
• Performance
• Readability
• Python standards/conventions
• Comment quality

Answer 1

Tests

Instead of that main, which I assume you wrote for testing...

You can create actual tests, with the unittests module.

import unittest

class HashTableTest(unittest.TestCase):
    def setUp(self):
        self.hashtable = HashTable()
        self.hashtable.put(1, 2)
        self.hashtable.put(9, 3)
        self.hashtable.put(17, 5)
    
    def test_get(self):
        self.assertEqual(self.hashtable.get(17), 5)

    def test_remove(self):
        self.hashtable.remove(17)
        self.assertEqual(self.hashtable.get(17), None)

    def test_get_entries(self):
        self.assertEqual(
            self.hashtable.get_entries(),  
            [(1, 2, 1, 0), (9, 3, 1, 1), (17, 5, 1, 2)]
        )


if __name__ == "__main__":
    unittest.main()

Magic Methods

You currently make use of the __str__ magic method, but the are plenty more, which you could make use of

• __len__
• __getitem__
• __setitem__
• __iter__

Misc

• A dictionary in Python has the ability to add a default get(key, default=None)

• Overall I think your comments are helpful, but sometimes you go overboard.

  Code should be self explanatory, Personally, I would prefer adding more text to the docstrings instead of those block comments (I find them sometimes hard to read)