ハッシュ関数の内部動作と衝突処理

ハッシュマップとは

# Python dict is a hash map
hm = {}
hm['alice'] = 95
hm['bob']   = 87
hm['carol'] = 91

print(hm['alice'])          # O(1) lookup: 95
print('bob' in hm)          # O(1) membership: True
del hm['bob']               # O(1) deletion
print(hm)                   # {'alice': 95, 'carol': 91}

ハッシュ関数と __hash__ メソッド

# Built-in hash in Python
print(hash(42))           # integer hashes to itself (CPython)
print(hash('hello'))      # string hash (randomised per run)
print(hash((1, 2, 3)))    # tuple hash: depends on contents

# Unhashable types
try:
    hash([1, 2, 3])       # lists are mutable -> not hashable
except TypeError as e:
    print('Error:', e)

# Custom class: define __hash__ and __eq__
class Point:
    def __init__(self, x, y): self.x = x; self.y = y
    def __hash__(self): return hash((self.x, self.y))
    def __eq__(self, other): return self.x == other.x and self.y == other.y

points = {Point(1, 2): 'A', Point(3, 4): 'B'}
print(points[Point(1, 2)])  # 'A'

衝突：2つのキーが同じバケットにハッシュされる場合

# Simplified chaining hash map
class ChainingHashMap:
    def __init__(self, capacity=8):
        self.capacity = capacity
        self.buckets  = [[] for _ in range(capacity)]

    def _idx(self, key):
        return hash(key) % self.capacity

    def put(self, key, val):
        bucket = self.buckets[self._idx(key)]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, val)
                return
        bucket.append((key, val))

    def get(self, key):
        for k, v in self.buckets[self._idx(key)]:
            if k == key:
                return v
        return None

hm = ChainingHashMap()
hm.put('a', 1); hm.put('b', 2)
print(hm.get('a'))  # 1
print(hm.get('c'))  # None

オープンアドレス法：線形探索

class LinearProbingHashMap:
    DELETED = object()  # tombstone sentinel

    def __init__(self, capacity=8):
        self.capacity = capacity
        self.keys  = [None] * capacity
        self.vals  = [None] * capacity
        self.size  = 0

    def _probe(self, key):
        idx = hash(key) % self.capacity
        while self.keys[idx] is not None and self.keys[idx] != key:
            idx = (idx + 1) % self.capacity
        return idx

    def put(self, key, val):
        idx = self._probe(key)
        if self.keys[idx] is None:
            self.size += 1
        self.keys[idx] = key
        self.vals[idx] = val

    def get(self, key):
        idx = self._probe(key)
        if self.keys[idx] == key:
            return self.vals[idx]
        return None

hm = LinearProbingHashMap()
hm.put('x', 10); hm.put('y', 20)
print(hm.get('x'))  # 10

負荷率とサイズ変更

import sys

d = {}
prev_size = sys.getsizeof(d)
for i in range(30):
    d[i] = i
    new_size = sys.getsizeof(d)
    if new_size != prev_size:
        print(f'Resized at n={i+1}: {prev_size} -> {new_size} bytes')
        prev_size = new_size

平均 O(1) と最悪 O(n)

# Python randomised hash seed prevents worst-case hash-flooding
import os
print('PYTHONHASHSEED:', os.environ.get('PYTHONHASHSEED', 'random'))
# By default Python randomises the hash of strings each run
# This prevents an attacker from crafting keys that all collide
# To reproduce results in testing: PYTHONHASHSEED=0 python script.py

Python の dict と defaultdict と Counter

from collections import defaultdict, Counter

# defaultdict for grouping
groups = defaultdict(list)
for word in ['apple', 'ant', 'banana', 'bee', 'avocado']:
    groups[word[0]].append(word)
print(dict(groups))
# {'a': ['apple','ant','avocado'], 'b': ['banana','bee']}

# Counter for frequency
c = Counter('abracadabra')
print(c.most_common(3))  # [('a',5),('b',2),('r',2)]
print(c['a'] - Counter('aa')['a'])  # counter subtraction

ハッシュマップとハッシュセット

# set for membership testing
visited = set()
for node in [1, 3, 5, 3, 7, 1]:
    if node not in visited:
        print('New node:', node)
        visited.add(node)

# Set operations: union, intersection, difference
A = {1, 2, 3, 4}
B = {3, 4, 5, 6}
print('Union:', A | B)         # {1,2,3,4,5,6}
print('Intersection:', A & B)  # {3,4}
print('Difference:', A - B)    # {1,2}

ハッシュマップをゼロから実装する（面接向け）

class HashMap:
    def __init__(self, capacity=16):
        self.capacity = capacity
        self.size     = 0
        self.buckets  = [[] for _ in range(capacity)]

    def _hash(self, key):
        return hash(key) % self.capacity

    def put(self, key, val):
        b = self.buckets[self._hash(key)]
        for i, (k, v) in enumerate(b):
            if k == key:
                b[i] = (key, val)
                return
        b.append((key, val))
        self.size += 1
        if self.size / self.capacity > 0.7:
            self._resize()

    def get(self, key, default=None):
        for k, v in self.buckets[self._hash(key)]:
            if k == key:
                return v
        return default

    def _resize(self):
        old = self.buckets
        self.capacity *= 2
        self.buckets = [[] for _ in range(self.capacity)]
        self.size = 0
        for bucket in old:
            for k, v in bucket:
                self.put(k, v)

hm = HashMap()
for i in range(20):
    hm.put(i, i * 2)
print(hm.get(10))   # 20
print(hm.capacity)  # should have resized

ハッシュマップが機能しない場合：ハッシュ化できないキー

from collections import defaultdict

def groupAnagrams(strs):
    groups = defaultdict(list)
    for s in strs:
        key = tuple(sorted(s))  # tuple is hashable; list is not
        groups[key].append(s)
    return list(groups.values())

print(groupAnagrams(['eat','tea','tan','ate','nat','bat']))
# [['eat','tea','ate'], ['tan','nat'], ['bat']]

まとめ：ハッシュマップの計算量

理解度チェック

レッスンのまとめ