minte9
SoftwareDevelopment / ALGORITHMS





Hashing Basics 

 
# HASHING - BASICS
# ----------------
# Concept:
#   - Hashing is the process of taking characters and converting them to number.
#
# Note:
#   - Real hash functions are one-way and produce fixed-size outputs.
#   - These examples are simplified for learning.
# -------------------------------------------------------

mapping_example = {'A': 1, 'B': 2, 'C': 3, 'D': 4, 'E': 5}

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

hash = hashing_encoding('BAD')
print(hash)  
# ---------------------------
# 214


# 2) Hashing additive
# -------------------
def hasing_sum(x: str) -> str:
    res = 0
    for char in x:
        res += mapping_example[char]
    return res

hash = hashing_encoding('BAD')
print(hash)
# ----------------------
# 7

Hash Table 

 
# HASH TABLE - O(1)
# -----------------
# Example:
#   - Simple thesaurus application to exemplify hash table storing data process.
#   - The user searches for an word and the application returns one synonim (O(1)).
#
# Implementation:
#   - 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:
#   - A tiny character-to-number map used by our hash function.
#   - Only lowercase letters are supported in this example.
# -------------

class HashTable:
    
    def __init__(self):
        self.capacity = 16
        self.table = [None] * self.capacity
        self.size = 0

    def _hash(self, x: str) -> int:  # List key is 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

Python - Dictionary 

 
# HASH TABLE - DICTIONARY
# -----------------------
# Buitl-in:
#   - In Python, dict() is a highly optimized hash table.
#   - In Java, we have HashMap 
#
# Fast lookps:
#   - O(1) on average
#
# Concept:
#   - 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


# 1) Using literal syntax {}
# --------------------------
prices = {
    "apple": 0.50,
    "banana": 0.30,
    "orange": 0.80,
}

# Searching
item = prices['banana']  # O(1)

# Inserting
prices["kiwi"] = 0.90  # O(1)

# Deleting 
del prices["banana"]  # O(1)

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


# 2) Using dict()
# ---------------
prices = dict([
    ("apple", 0.50),
    ("banana", 0.30),
    ("orange", 0.80),
])
print(prices)
# ------------------------------------------
# {'banana': 0.3, 'orange': 0.8, 'kiwi': 0.9}


# 3) Using 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: