Hash Table Part 1

hash_table.py

from linked_list import LinkedList

class HashTable(object):

    def __init__(self, items = None):
        """Initialize this HashTable and set items if specified"""
        
        self.slots = [LinkedList() for i in range(8)] # start with 8 slots
        self.size = 0

    def _get_hash_index(self, key):
        """Return a hash index by hashing the key and finding the remainder of the hash
        divided by the number of slots in the HashTable"""
        
        # knowing that the number of buckets will always be a power of 2
        # we can use bitwise AND `hash & l-1` instead of modulo
        return self._hash_str(key) & (len(self.slots)-1)

    def _hash_str(self, string):
        """Return a hash of the given string. hash_str uses the djb2 algorithm to compute 
        the hash value of a string http://www.cse.yorku.ca/~oz/hash.html"""
        hash = 5381
        for char in string[1:]:
            # (hash << 5) + hash is equivalent to hash * 33
            hash = (hash << 5) + hash + ord(char)
        return hash