Python Hash Table and insertion

Question

I'm attempting to implement a basic hash table in Python using linked lists. Any tips would be appreciated (including better hash functions). I intend this to handle collisions with separate chaining.

I include my gist for my linked list:

Question: Are there any things I handled incorrectly or could have implemented in a better way?

I also checked my function against the unit-test and make sure it all 11 tests and passes them.

#!python

from linkedlist import LinkedList

class HashTable(object):

    def __init__(self, init_size=8):
        """Initialize this hash table with the given initial size."""
        self.buckets = [LinkedList() for i in range(init_size)]
        self.size = 0  # Number of key-value entries

    def __str__(self):
        """Return a formatted string representation of this hash table."""
        items = ['{!r}: {!r}'.format(key, val) for key, val in self.items()]
        return '{' + ', '.join(items) + '}'

    def __repr__(self):
        """Return a string representation of this hash table."""
        return 'HashTable({!r})'.format(self.items())

    def _bucket_index(self, key):
        """Return the bucket index where the given key would be stored."""
        return hash(key) % len(self.buckets)

    def load_factor(self):
        """Return the load factor, the ratio of number of entries to buckets.
        Best and worst case running time: Theta(n) it always depends on the number
        of items that need to be counted, one by one"""
        return float(self.size) / (len(self.buckets))

    def keys(self):
        """Return a list of all keys in this hash table.
        Best and worst case running time: O(n^2)"""
        # Collect all keys in each of the buckets
        all_keys = []
        for bucket in self.buckets:
            for key, value in bucket.items():
                all_keys.append(key)
        return all_keys

    def values(self):
        """Return a list of all values in this hash table.
        Best and worst case running time: O(n^2)"""
        # Collect all values in each of the buckets
        all_values = []
        for bucket in self.buckets:
            for key, value in bucket.items():
                all_values.append(value)
        return all_values

    def items(self):
        """Return a list of all entries (key-value pairs) in this hash table.
        Best and worst case running time: O(n^2)"""
        # Collect all pairs of key-value entries in each of the buckets
        all_items = []
        for bucket in self.buckets:
            all_items.extend(bucket.items())
        return all_items

    def length(self):
        """Return the number of key-value entries by traversing its buckets.
        Best and worst case running time: O(1)"""
        return self.size

    def contains(self, key):
        """Return True if this hash table contains the given key, or False.
        Best case running time: O(1) near beginning of list of keys
        Worst case running time: O(n) near end of list of keys """
        # Find the bucket the given key belongs in
        index = self._bucket_index(key)
        bucket = self.buckets[index]
        entry = bucket.find(lambda key_value: key_value[0] == key)
        return entry is not None  # True or False

    def get(self, key):
        """Return the value associated with the given key, or raise KeyError.
        Best case running time: O(1) if entry is near beginning of list in first bucket
        Worst case running time: O(n) in most cases it will be theta(n) and depend
        on where it is located in the list of items"""
        # Find the bucket the given key belongs in
        index = self._bucket_index(key)
        bucket = self.buckets[index]
        # # Find the entry with the given key in that bucket, if one exists
        entry = bucket.find(lambda key_value: key_value[0] == key)
        # Return the given key's associated value
        if entry is not None:
            assert isinstance(entry, tuple)
            assert len(entry) == 2
            return entry[1]
        else: 
            raise KeyError('Key not found: {}'.format(key))

    def set(self, key, value):
        """Insert or update the given key with its associated value.
        Best case running time: O(1) if it's near beginning of LL
        Worst case running time: O(n) in most cases, depends on position in LL"""
        # Find the bucket the given key belongs in
        index = self._bucket_index(key)
        bucket = self.buckets[index]
        # Find the entry with the given key in that bucket, if one exists
        # Check if an entry with the given key exists in that bucket
        entry = bucket.find(lambda key_value: key_value[0] == key)      
        if entry is not None:  # Found
            # In this case, the given key's value is being updated
            # Remove the old key-value entry from the bucket first
            bucket.delete(entry)                                         
        else:
            # If not found, increase size by one to account for new item
            self.size += 1
        # Insert the new key-value entry into the bucket in either case
        bucket.append((key, value))
        # Check if load_factor exceeds threshold, if it does, resize hashtable
        if self.load_factor() > 0.75:
            self._resize()

    def delete(self, key):
        """Delete the given key and its associated value, or raise KeyError.
        Best case running time: O(1) if near beginning of LL
        Worst case running time: O(n) in most cases, depends on position in LL"""
        # Find the bucket the given key belongs in
        index = self._bucket_index(key)
        bucket = self.buckets[index]
        # Find the entry with the given key in that bucket, if one exists
        entry = bucket.find(lambda key_value: key_value[0] == key)
        if entry is not None:  # Found
            # Remove the key-value entry from the bucket
            bucket.delete(entry)
            self.size -= 1
        else:  # Not found
            raise KeyError('Key not found: {}'.format(key))

    def _resize(self, new_bucket_count=None):
        """Resize this hash table's buckets and rehash all key-value entries.
        Should be called automatically when load factor exceeds a threshold
        such as 0.75 after an insertion (when set is called with a new key).
        Best and worst case running time: ??? under what conditions? [TODO]
        Best and worst case space usage: ??? what uses this memory? [TODO]"""
        # If unspecified, choose new size dynamically based on current size
        if new_bucket_count is None:
            new_bucket_count = len(self.buckets) * 2  # Double the bucket
        # Option to reduce size if buckets are sparsely filled (low load factor)
        elif new_bucket_count is 0:
            new_bucket_count = len(self.buckets) // 2  # Half the bucket
        # Get a list to temporarily hold all current key-value entries
        old_items = self.items()
        # Create a list of new buckets to be used for rehashing
        self.buckets = [LinkedList() for _ in range(new_bucket_count)]
        # Reset size
        self.size = 0
        # Insert each key-value entry into the new list of buckets,
        for key, value in old_items:
            self.set(key, value)


def test_hash_table():
    ht = HashTable(4)
    print('HashTable: ' + str(ht))

    print('Setting entries:')
    ht.set('I', 1)
    print('set(I, 1): ' + str(ht))
    ht.set('V', 5)
    print('set(V, 5): ' + str(ht))
    print('size: ' + str(ht.size))
    print('length: ' + str(ht.length()))
    print('buckets: ' + str(len(ht.buckets)))
    print('load_factor: ' + str(ht.load_factor()))
    ht.set('X', 10)
    print('set(X, 10): ' + str(ht))
    ht.set('L', 50)  # Should trigger resize
    print('set(L, 50): ' + str(ht))
    print('size: ' + str(ht.size))
    print('length: ' + str(ht.length()))
    print('buckets: ' + str(len(ht.buckets)))
    print('load_factor: ' + str(ht.load_factor()))

    print('Getting entries:')
    print('get(I): ' + str(ht.get('I')))
    print('get(V): ' + str(ht.get('V')))
    print('get(X): ' + str(ht.get('X')))
    print('get(L): ' + str(ht.get('L')))
    print('contains(X): ' + str(ht.contains('X')))
    print('contains(Z): ' + str(ht.contains('Z')))

    print('Deleting entries:')
    ht.delete('I')
    print('delete(I): ' + str(ht))
    ht.delete('V')
    print('delete(V): ' + str(ht))
    ht.delete('X')
    print('delete(X): ' + str(ht))
    ht.delete('L')
    print('delete(L): ' + str(ht))
    print('contains(X): ' + str(ht.contains('X')))
    print('size: ' + str(ht.size))
    print('length: ' + str(ht.length()))
    print('buckets: ' + str(len(ht.buckets)))
    print('load_factor: ' + str(ht.load_factor()))


if __name__ == '__main__':
    test_hash_table()



#!python

from hashtable import HashTable
import unittest
# Python 2 and 3 compatibility: unittest module renamed this assertion method
if not hasattr(unittest.TestCase, 'assertCountEqual'):
    unittest.TestCase.assertCountEqual = unittest.TestCase.assertItemsEqual


class HashTableTest(unittest.TestCase):

    def test_init(self):
        ht = HashTable(4)
        assert len(ht.buckets) == 4
        assert ht.length() == 0
        assert ht.size == 0

    def test_keys(self):
        ht = HashTable()
        assert ht.keys() == []
        ht.set('I', 1)
        assert ht.keys() == ['I']
        ht.set('V', 5)
        self.assertCountEqual(ht.keys(), ['I', 'V'])  # Ignore item order
        ht.set('X', 10)
        self.assertCountEqual(ht.keys(), ['I', 'V', 'X'])  # Ignore item order

    def test_values(self):
        ht = HashTable()
        assert ht.values() == []
        ht.set('I', 1)
        assert ht.values() == [1]
        ht.set('V', 5)
        self.assertCountEqual(ht.values(), [1, 5])  # Ignore item order
        ht.set('X', 10)
        self.assertCountEqual(ht.values(), [1, 5, 10])  # Ignore item order

    def test_items(self):
        ht = HashTable()
        assert ht.items() == []
        ht.set('I', 1)
        assert ht.items() == [('I', 1)]
        ht.set('V', 5)
        self.assertCountEqual(ht.items(), [('I', 1), ('V', 5)])
        ht.set('X', 10)
        self.assertCountEqual(ht.items(), [('I', 1), ('V', 5), ('X', 10)])

    def test_length(self):
        ht = HashTable()
        assert ht.length() == 0
        ht.set('I', 1)
        assert ht.length() == 1
        ht.set('V', 5)
        assert ht.length() == 2
        ht.set('X', 10)
        assert ht.length() == 3

    def test_size(self):
        ht = HashTable()
        assert ht.size == 0
        ht.set('I', 1)
        assert ht.size == 1
        ht.set('V', 5)
        assert ht.size == 2
        ht.set('X', 10)
        assert ht.size == 3

    def test_resize(self):
        ht = HashTable(2)  # Set init_size to 2
        assert ht.size == 0
        assert len(ht.buckets) == 2
        assert ht.load_factor() == 0
        ht.set('I', 1)
        assert ht.size == 1
        assert len(ht.buckets) == 2
        assert ht.load_factor() == 0.5
        ht.set('V', 5)  # Should trigger resize
        assert ht.size == 2
        assert len(ht.buckets) == 4
        assert ht.load_factor() == 0.5
        ht.set('X', 10)
        assert ht.size == 3
        assert len(ht.buckets) == 4
        assert ht.load_factor() == 0.75
        ht.set('L', 50)  # Should trigger resize
        assert ht.size == 4
        assert len(ht.buckets) == 8
        assert ht.load_factor() == 0.5

    def test_contains(self):
        ht = HashTable()
        ht.set('I', 1)
        ht.set('V', 5)
        ht.set('X', 10)
        assert ht.contains('I') is True
        assert ht.contains('V') is True
        assert ht.contains('X') is True
        assert ht.contains('A') is False

    def test_set_and_get(self):
        ht = HashTable()
        ht.set('I', 1)
        ht.set('V', 5)
        ht.set('X', 10)
        assert ht.get('I') == 1
        assert ht.get('V') == 5
        assert ht.get('X') == 10
        assert ht.length() == 3
        assert ht.size == 3
        with self.assertRaises(KeyError):
            ht.get('A')  # Key does not exist

    def test_set_twice_and_get(self):
        ht = HashTable()
        ht.set('I', 1)
        ht.set('V', 4)
        ht.set('X', 9)
        assert ht.length() == 3
        assert ht.size == 3
        ht.set('V', 5)  # Update value
        ht.set('X', 10)  # Update value
        assert ht.get('I') == 1
        assert ht.get('V') == 5
        assert ht.get('X') == 10
        assert ht.length() == 3  # Check length is not overcounting
        assert ht.size == 3  # Check size is not overcounting

    def test_delete(self):
        ht = HashTable()
        ht.set('I', 1)
        ht.set('V', 5)
        ht.set('X', 10)
        assert ht.length() == 3
        assert ht.size == 3
        ht.delete('I')
        ht.delete('X')
        assert ht.length() == 1
        assert ht.size == 1
        with self.assertRaises(KeyError):
            ht.delete('X')  # Key no longer exists
        with self.assertRaises(KeyError):
            ht.delete('A')  # Key does not exist


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

Answer 1

Few high-level ideas and minor nitpicks:

• have you considered json.dumps() to use for the HashTable's string representation

• the keys() and values() methods can make use of a list comprehension:

  def keys(self):
      """Return a list of all keys in this hash table.
      Best and worst case running time: O(n^2)"""
  
      # Collect all keys in each of the buckets
      return [key 
              for bucket in self.buckets
              for key, _ in bucket.items()]
  
  def values(self):
      """Return a list of all values in this hash table.
      Best and worst case running time: O(n^2)"""
  
      # Collect all values in each of the buckets
      return [value 
              for bucket in self.buckets
              for _, value in bucket.items()]
  

  Please check if you can use bucket.keys() and bucket.values() directly, instead of looping over .items().

• actually, can be applied for items() as well:

  return [item
          for bucket in self.buckets
          for item in bucket.items()]
  

• consider using Type Annotations. For instance, look how you've added this inline comment:

  return entry is not None  # True or False
  

  With type hints, you could've removed the comment and add a return type as a hint:

  def contains(self, key) -> bool:
  

• unused loop variable. Since i is unused in the self.buckets = [LinkedList() for i in range(init_size)] expression, use _ as a variable name:

  self.buckets = [LinkedList() for _ in range(init_size)]
  

• format Documentation Strings properly. There are some recommendations like, add a newline into the beginning of a docstring if it consists of multiple lines, end it with a dot etc.