해시 함수: 빠른 검색의 수학

입력 (가변 크기) ──┐
                 ↓
              해시 함수
                 ↓
입력 (고정 크기) ──┘  (예: 256비트)

특징:
1. 결정적 (Deterministic): 같은 입력 → 항상 같은 출력
2. 균등 분포 (Uniform): 비슷한 입력도 다른 출력
3. 단방향 (One-way): 출력 → 입력 역산 불가
4. 빠름: O(1) 또는 O(n)

# 내장 hash() — 임의의 정수
print(hash("Hello"))   # 5235312840681...
print(hash(42))        # 42
print(hash((1, 2, 3))) # -2962840714241...
print(hash([1, 2, 3])) # TypeError — list는 mutable이라 hashable 아님


# 같은 입력 → 같은 출력
print(hash("Hello") == hash("Hello"))  # True


# 단, Python의 hash()는 보안용 아님 (단순 분산용)
# 보안 필요 시 hashlib 사용
import hashlib

m = hashlib.sha256()
m.update(b"Hello")
print(m.hexdigest())
# 185f8db32271fe25f561a6fc938b2e264306ec304eda518007d1764826381969

# 직접 HashMap 구현 — 체이닝 방식

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

    def _hash(self, key):
        # 키를 0~capacity-1 정수로 변환
        return hash(key) % self.capacity

    def put(self, key, value):
        bucket = self.buckets[self._hash(key)]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)  # 업데이트
                return
        bucket.append((key, value))  # 신규

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


m = HashMap()
m.put("Alice", 30)
m.put("Bob", 25)
m.put("Charlie", 35)

print(m.get("Alice"))  # 30
print(m.get("Bob"))    # 25

# 두 키가 같은 버킷에 매핑 = 충돌
# 비둘기집 원리: 입력 가능 수 > 버킷 수면 반드시 충돌

# 충돌 시뮬레이션
m = HashMap(capacity=3)
m.put("Alice", 30)
m.put("Bob", 25)
m.put("Charlie", 35)
m.put("Dave", 40)
m.put("Eve", 45)

# 버킷 분포 확인
for i, bucket in enumerate(m.buckets):
    print(f"버킷 {i}: {bucket}")
# 버킷 0: [('Bob', 25), ('Eve', 45)]      ← 충돌 (체이닝)
# 버킷 1: [('Alice', 30)]
# 버킷 2: [('Charlie', 35), ('Dave', 40)] ← 충돌

1. 체이닝 (Separate Chaining)
   각 버킷에 연결 리스트 → Python dict의 기본 구조

2. 개방 주소법 (Open Addressing)
   - Linear Probing: 다음 빈 칸 탐색
   - Quadratic Probing: i² 만큼 점프
   - Double Hashing: 두 번째 해시 함수

3. 로빈 후드 해싱 (Robin Hood Hashing)
   가까운 것은 가까이, 멀리 떨어진 것에 양보

# pip install bcrypt
import bcrypt

# 회원가입 시
password = b"my_secret_password"
salt = bcrypt.gensalt(rounds=12)  # 솔트 생성
hashed = bcrypt.hashpw(password, salt)
print(hashed)
# b'$2b$12$wIvK0iTXrh7L...'


# 로그인 시
def verify_password(input_pw, stored_hash):
    return bcrypt.checkpw(input_pw.encode(), stored_hash)


print(verify_password("my_secret_password", hashed))  # True
print(verify_password("wrong_pw", hashed))            # False


# bcrypt가 안전한 이유:
# 1. 솔트 — 같은 비밀번호도 매번 다른 해시
# 2. 의도적으로 느림 (rounds=12 → 약 0.3초) — 무차별 공격 방어
# 3. SHA-256보다 적합 (SHA는 빠름이 단점)

# 파일 다운로드 후 변조 여부 확인
import hashlib

def file_sha256(path):
    h = hashlib.sha256()
    with open(path, 'rb') as f:
        while chunk := f.read(8192):
            h.update(chunk)
    return h.hexdigest()


# 다운로드 사이트 제공: a3f1...8c92
expected = "a3f1c5d8b2e9..."
actual = file_sha256("downloaded_file.zip")

if actual == expected:
    print("✅ 무결성 검증 통과")
else:
    print("❌ 파일이 변조됨")

# 리스트 검색: O(n)
nums = list(range(1_000_000))
999_999 in nums  # 약 10ms

# set/dict 검색: O(1) 평균
nums_set = set(nums)
999_999 in nums_set  # 약 0.001ms

# 비밀: 해시 함수가 즉시 버킷 위치 계산
# → 충돌 없으면 O(1), 충돌 있어도 평균 O(1)


# Worst case는 O(n) — 모든 키가 한 버킷에 몰리면
# Python dict는 무작위화 + open addressing으로 방어