# Built-in hash()
print(hash(42)) # Integer hash
print(hash('hello')) # String hash
print(hash((1, 2))) # Tuple hash
# print(hash([1, 2])) # TypeError! Lists are unhashable
# Hash is consistent within a process
print(hash('test') == hash('test')) # True
# Hash of integers is often the integer itself
print(hash(100)) # 100class HashTable:
def __init__(self, size=10):
self.size = size
self.buckets = [[] for _ in range(size)]
def _hash(self, key):
return hash(key) % self.size
def put(self, key, value):
idx = self._hash(key)
bucket = self.buckets[idx]
for i, (k, v) in enumerate(bucket):
if k == key:
bucket[i] = (key, value)
return
bucket.append((key, value))
def get(self, key):
idx = self._hash(key)
bucket = self.buckets[idx]
for k, v in bucket:
if k == key:
return v
raise KeyError(key)
def __setitem__(self, key, value):
self.put(key, value)
def __getitem__(self, key):
return self.get(key)
def __str__(self):
items = []
for i, bucket in enumerate(self.buckets):
if bucket:
items.append(f'{i}: {bucket}')
return '{' + ', '.join(items) + '}'
ht = HashTable(5)
ht['name'] = 'Alice'
ht['age'] = 25
ht['city'] = 'NYC'
print(ht)
print(ht['name']) # 'Alice'class OpenAddressHT:
def __init__(self, size=10):
self.size = size
self.keys = [None] * size
self.values = [None] * size
def _hash(self, key):
return hash(key) % self.size
def put(self, key, value):
idx = self._hash(key)
while self.keys[idx] is not None:
if self.keys[idx] == key:
self.values[idx] = value
return
idx = (idx + 1) % self.size
self.keys[idx] = key
self.values[idx] = value
def get(self, key):
idx = self._hash(key)
while self.keys[idx] is not None:
if self.keys[idx] == key:
return self.values[idx]
idx = (idx + 1) % self.size
raise KeyError(key)class ResizableHT:
def __init__(self, initial_size=8, load_factor=0.75):
self.size = initial_size
self.load_factor = load_factor
self.count = 0
self.buckets = [[] for _ in range(self.size)]
def put(self, key, value):
if self.count / self.size >= self.load_factor:
self._resize()
idx = hash(key) % self.size
for i, (k, v) in enumerate(self.buckets[idx]):
if k == key:
self.buckets[idx][i] = (key, value)
return
self.buckets[idx].append((key, value))
self.count += 1
def _resize(self):
old = self.buckets
self.size *= 2
self.buckets = [[] for _ in range(self.size)]
self.count = 0
for bucket in old:
for k, v in bucket:
self.put(k, v)class Point:
def __init__(self, x, y):
self.x, self.y = x, y
def __eq__(self, other):
return self.x == other.x and self.y == other.y
def __hash__(self):
return hash((self.x, self.y))
# Now usable as dict key!
points = {}
p = Point(1, 2)
points[p] = 'origin'
print(points[Point(1, 2)]) # 'origin'def two_sum(nums, target):
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return None
print(two_sum([2, 7, 11, 15], 9)) # [0, 1]Implement a `HashTable` class using chaining with: `__init__(size=8)`, `_hash(key)`, `put(key, value)`, `get(key)`, `delete(key)`, `__setitem__`, `__getitem__`, `__contains__`, `__len__`, and `__str__`. Add auto-resizing when load factor exceeds 0.75. Implement `two_sum(nums, target)` using a hash map. Implement `frequency_count(items)` returning a dict of item counts. Demonstrate all with clear output.