Programming

  minte9
LearnRemember



Data Structures / Hash Tables 

What is hashing?
Does Python have built-in hash table?
What's the big O when searching in a dictionary?

Fast Reading / O(1)

In an unordered array, a search would take O(N) steps adn O(log N) for an ordered array. Using a data structure like hash table, we can make the search O(1)! 
 
# Hash Table
menu = {'a': 1, 'b': 2,  'c': 3}

# Searching a dictionary takes only O(1) steps
item = menu['b']

# Output result
print(item) # 2

Hash Function / Numbers

The process of taking characters and converting them to numbers is called hashing. 
 
mapping = {'A': 1, 'B': 2, 'C': 3, 'D': 4, 'E': 5}

def hashing(x: str) -> str:
    hash = ''
    for char in x:
        hash += str(mapping[char])
    return hash

def hashing_sum(x: str) -> int: # using addition
    hash = 0
    for char in x:
        hash += mapping[char]
    return hash

def hashing_product(x: str) -> int: # multiplication
    hash = 1
    for char in x:
        hash *= mapping[char]
    return hash

print("Hashing | BAD =", hashing('BAD'))
print("Hasghing to Sum | BAD =", hashing_sum('BAD'))
print("Hasghing to Product | BAD =", hashing_product('BAD'))

"""
    Hashing | BAD = 214
    Hasghing to Sum | BAD = 7
    Hasghing to Product | BAD = 8
"""

Table Storage / Process

Let's imagine a simple thesaurus application to exemplify hash table storing data proces. The user search for an word and the app returns just one synonym. 
 
class MyHashTable:

    # Initialize internal table (an array with 16 empty cells)
    def __init__(self):
        self.table = [None] * 16
        self.mapping = {'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5}

    # Hash multiplication function
    def hash_entry(self, x):
        hash = 1
        for char in x:
            hash *= self.mapping[char]
        return hash

    def add_entry(self, key, value):
        hash = self.hash_entry(key)
        self.table[hash] = value    # O(1) - Look Here

    def get_entry(self, key):
        hash = self.hash_entry(key)
        return self.table[hash]    # O(1)

thesaurus = MyHashTable()

thesaurus.add_entry('bad', 'evil')
thesaurus.add_entry('cab', 'taxi')

value1 = thesaurus.get_entry('bad')
value2 = thesaurus.get_entry('cab')

print(value1)
print(value2)

# evil
# taxi




References