563. 해시 충돌(Collision) 해결 기법과 DB 매핑 오버헤드

⚠️ 이 문서는 데이터베이스 해시 인덱스나 메모리 캐시(Redis, Memcached)에서 데이터를 눈 깜짝할 새($O(1)$) 찾아내기 위해 사용하는 해시 함수가 필연적으로 겪게 되는 '서로 다른 데이터가 똑같은 해시 주소를 배정받는 충돌(Collision)' 현상과, 이를 해결하기 위한 체이닝(Chaining) 및 선형 탐사(Linear Probing) 방식의 디스크/메모리 성능 오버헤드를 다룹니다.

핵심 인사이트 (3줄 요약)

  1. 본질: 해시 함수는 무한한 우주의 데이터를 한정된 개수의 방(Bucket)에 구겨 넣는 마법이다. 방의 개수가 유한하므로, 언젠가는 한 방에 두 명의 데이터가 배정되는 '충돌'이 반드시 수학적(비둘기집 원리)으로 일어난다.
  2. 가치: 이 충돌을 어떻게 기발하게 처리하느냐에 따라 DB의 탐색 속도가 결정된다. 충돌이 너무 잦아지면 자랑하던 $O(1)$의 초고속 검색 속도가 $O(N)$으로 곤두박질치는 최악의 성능 저하(Performance Degradation)를 겪게 된다.
  3. 기술 체계: 꽉 찬 방에 연결 리스트로 줄을 세우는 '체이닝(Chaining)' 방식과, 옆에 있는 빈방을 찾아 헤매는 '개방 주소법(Open Addressing / 선형 탐사)' 방식이 양대 산맥으로 쓰인다.

Ⅰ. 해시 충돌의 필연성과 비둘기집 원리

아무리 똑똑한 해시 함수라도 비좁은 방 앞에서는 무력하다.

  1. 비둘기집 원리 (Pigeonhole Principle):
    • 비둘기가 10마리인데 비둘기집이 9개뿐이라면, 최소한 1개의 집에는 비둘기가 2마리 이상 들어가야 한다는 절대적인 수학 법칙이다.
    • 데이터베이스에서 해시 공간(버킷 배열의 크기)이 $100$개인데, 저장할 데이터가 $101$개가 들어오면 무조건 충돌이 발생한다.
  2. 충돌 (Collision)의 발생:
    • Hash("Alice") % 10의 결과가 3번 방이었는데, 나중에 가입한 Hash("Bob") % 10의 결과도 똑같이 3번 방이 나오는 현상이다.
    • DB 엔진은 이 불청객 Bob을 어떻게 처리할지 1밀리초 안에 결정해야 한다.

📢 섹션 요약 비유: 호텔 방이 100개뿐인데 손님이 150명 예약했습니다. 프런트 직원이 아무리 방 배정을 똑똑하게 해도, 누군가는 반드시 모르는 사람과 같은 방(충돌)을 써야만 하는 피할 수 없는 물리적 한계입니다.

Ⅱ. 해결책 1: 체이닝 (Chaining) - 자비로운 꼬리 물기

방이 꽉 찼다면 방 밖으로 줄을 세운다. Java의 HashMap이 쓰는 방식이다.

  1. 작동 원리 (연결 리스트):
    • 3번 방에 Alice가 이미 들어있는데 Bob이 3번 방으로 배정받았다.
    • 3번 방 안에 억지로 우겨 넣지 않고, 3번 방 밖으로 '포인터(Pointer)'라는 끈을 달아 Bob을 묶어둔다. (연결 리스트 생성)
    • 나중에 Charlie도 3번 방에 오면, Bob 뒤에 끈으로 다시 묶는다. [3번 방] -> Alice -> Bob -> Charlie
  2. 성능 오버헤드와 DB 적용의 한계:
    • 장점: 빈방(버킷)을 낭비하지 않고 방이 꽉 차도 계속 데이터를 무한정 저장할 수 있다.
    • 단점 (Cache Miss): 꼬리에 꼬리를 무는 포인터 탐색은 메모리나 디스크상에서 데이터가 물리적으로 흩어져(파편화) 있게 된다. 이 때문에 CPU 캐시 적중률(Cache Hit Rate)이 바닥을 치고, 디스크에서는 랜덤 I/O를 유발해 속도가 느려진다.

📢 섹션 요약 비유: 방이 꽉 차면 방 밖 복도에 캠핑 의자를 두고 손님들을 일렬로 앉혀서 기다리게 하는 것입니다. 방은 넉넉히 쓸 수 있지만, 배달부가 3번 방 손님 3명에게 피자를 배달하려면 복도를 길게 따라가며 한 명씩 찾아야 해서(포인터 탐색) 배달 시간(오버헤드)이 길어집니다.

Ⅲ. 해결책 2: 개방 주소법과 선형 탐사 (Linear Probing)

내 방이 없으면 남의 빈방을 뺏어버린다. 파이썬의 dict나 하드웨어 캐시가 사랑하는 방식이다.

  1. 선형 탐사 (Linear Probing) 작동 원리:
    • 3번 방에 Alice가 있는데 Bob이 3번 방을 배정받았다.
    • Bob은 3번 방 밖에서 기다리지 않고, 바로 옆 방인 4번 방 문을 두드려본다. 비어있으면 4번 방을 낼름 차지한다. 4번 방마저 꽉 차 있으면 5번 방, 6번 방으로 계속 옆으로 한 칸씩 이동하며 빈방을 찾는다.
  2. 성능 오버헤드의 장단점:
    • 장점 (Cache Hit 극대화): 데이터가 배열에 연속적으로 물리적으로 다닥다닥 붙어 저장되므로, CPU가 캐시 메모리로 읽어 들일 때 한 번에 왕창 퍼 올릴 수 있어 속도가 어마어마하게 빠르다.
    • 단점 (Clustering 현상): 한 번 충돌이 나서 옆 방을 뺏기 시작하면, 데이터들이 특정 구간에 떡지듯 뭉치는 '군집화(Clustering)' 현상이 발생한다. 데이터가 꽉 찰수록 빈방을 찾기 위해 수십 개의 방을 열어봐야 하므로 성능이 곤두박질친다.
  3. 해결책 (Rehashing / 리사이징):
    • 방이 70~80% 정도 차면(Load Factor 초과), DB는 일시정지하고 방을 2배(200개)로 늘린 거대한 새 호텔을 짓는다. 그리고 기존 손님들을 새로운 해시 함수로 모조리 다 다시 배정(Rehashing)하는 엄청난 이사 작업을 백그라운드에서 수행해야 한다.

📢 섹션 요약 비유: 3번 방이 꽉 차면 짐을 들고 바로 옆 4번 방, 5번 방 문을 두드려 빈방에 무단 침입하는 방식입니다. 데이터가 몰려있는 곳은 다 같이 붙어있어서 청소하기(캐시 읽기) 편하지만, 호텔이 꽉 차갈수록 빈방 찾느라 복도를 끝도 없이 헤매야 하므로, 호텔 지배인(DB)은 방이 70%쯤 차면 아예 2배 크기의 새 호텔을 짓고 모두 강제 이사를 시키는 엄청난 대공사(Rehashing)를 벌여야 합니다.