minte9
LearnRemember   ALGORITHMS







PVM / Python / Data Structures / Hash Tables

1. Hashing Basics

Hashing is the process of taking characters and converting them to number. Real hash functions are one-way and produce fixed-size outputs. These examples are simplified for learning. 
 py
# Hasing
items = {'A': 1, 'B': 2, 'C': 3, 'D': 4, 'E': 5}

# Hashing encoding
def hashing_encoding(x: str) -> str:
    res = ""
    for char in x:
        res += str(items[char])
    return res

print(hashing_encoding('BAD'))  # 214

# Additive hash
def hasing_sum(x: str) -> str:
    res = 0
    for char in x:
        res += items[char]
    return res

print(hasing_sum('BAD'))  # 7

2. Hash Table

To exemplify hash table storing data process we use a simple thesaurus application. The user searches for an word and the application returns one synonim. Time complexity is O(1). We implement a tiny custom "hash table" for strings made of letters a-e. It does not handle many real-world edge cases. This version is simplified for teaching. Mapping is done with a tiny character-to-number map used by our hash function. Only lowercase letters are supported in this example. 
 py
# Hasing example (thesaurus application)
class HashTable:
    
    def __init__(self):
        self.capacity = 16
        self.table = [None] * self.capacity
        self.size = 0

    def _hash(self, x: str) -> int:
        h = 0
        base = 257
        for ch in x:
            h = (h * base + ord(ch)) % self.capacity
        return h

    def __setitem__(self, key, val):
        idx = self._hash(key)
        self.table[idx] = val  # Average O(1)
        self.size += 1

    def __getitem__(self, key):
        idx = self._hash(key)
        return self.table[idx]  # Average O(1)

thesaurus = HashTable()

# Insert
thesaurus['bad'] = 'evil'
thesaurus['cab'] = 'taxi'

# Search
print(thesaurus['bad'])  # evil
print(thesaurus['cab'])  # taxi

# Update
thesaurus['cab'] = 'taxiii'
print(thesaurus['cab'])  # taxiii

3. Dictionary

In Python the built-in dict() is a highly optimized hash table. In Java, the equivalent is HashMap(). Dictionaries have fast lookps, O(1) on average. An unordered array search is O(n). An ordered array binary search is O(log n). A hash table is O(1) average-case for get, set, delete. 
 py
# Dictionary initionalized with literal syntax {}
# ===============================================
prices = {
    "apple": 0.50,
    "banana": 0.30,
    "orange": 0.80,
}

item = prices['banana']     # O(1) Searching
prices["kiwi"] = 0.90       # O(1) Inserting
del prices["banana"]        # O(1) Deleting

print(prices)               
# {'apple': 0.5, 'orange': 0.8, 'kiwi': 0.9}


# Dictionary initionalized with build-in dict()
# =============================================
prices = dict([
    ("apple", 0.50),
    ("banana", 0.30),
    ("orange", 0.80),
])

print(prices)
# {'banana': 0.3, 'orange': 0.8, 'kiwi': 0.9}


# Dictionary initionalized with build-in zip()
# ============================================
keys = ["apple", "banana", "kiwi"]
values = [0.50, 0.30, 0.90]
prices = dict(zip(keys, values))

print(prices)
# {'apple': 0.5, 'banana': 0.3, 'kiwi': 0.9}




References: