해시 테이블의 원소가 늘면 왜 재해시가 필요하며 요청 지연에 어떤 영향을 주나요?

해시 테이블은 원소가 늘어 부하율이 높아지면 충돌과 탐사 길이가 커지므로 버킷 수를 늘립니다. 버킷 수가 바뀌면 보통 hash(key) % bucketCount 또는 비트 마스크의 결과가 달라져 기존 원소도 새 위치로 옮겨야 합니다. 이 전체 재배치를 재해시라고 부르며, 평소 삽입보다 한 번의 지연과 메모리 피크가 커질 수 있습니다.

확장 중 일관성과 지연을 보호합니다

예를 들어 네 버킷에서 키 5는 1번에 있었지만 여덟 버킷에서는 5번에 놓일 수 있습니다. 단순히 버킷 배열 뒤에 빈 칸만 추가하면 충돌 분포가 개선되지 않으므로 원소를 새 배열에 다시 넣습니다. 이때 키의 해시 자체를 다시 계산하지 않아도 되지만 새 용량에 대한 인덱스는 계산해야 합니다. 체이닝은 노드를 옮기고 개방 주소법은 탐사 구조 전체를 새로 구성해야 합니다. 이를 재해시(rehashing) 또는 테이블 리사이징(table resizing)이라고 합니다.

확장 임계값을 넘긴 삽입은 기존 원소를 여러 개 이동하므로 O(n)이 될 수 있습니다. 기하급수적으로 늘리면 긴 연산열의 분할 상환 비용은 작아지지만, 그 순간 새 배열과 옛 배열을 함께 보유할 수 있어 메모리 피크가 생깁니다. 예상 원소 수를 알면 미리 용량을 예약해 요청 경로의 확장을 줄일 수 있지만, 사용하지 않는 버킷을 미리 확보하는 비용을 부담합니다.

지연과 동시성을 계약에 넣습니다

개별 지연이 중요한 서비스는 점진적 재해시를 검토할 수 있습니다. 새 테이블을 만들고 매 연산마다 일부 버킷을 옮기며 조회는 옛·새 테이블을 모두 확인합니다. 같은 키 갱신은 어느 테이블에 있는지 찾아 한 곳만 수정하고, 이동 중 중복이 생기지 않게 상태 전이를 정의해야 합니다. 구현이 복잡해지고 한동안 메모리가 더 필요하므로 단순한 일괄 재해시와 실제 p99를 비교하겠습니다.

동시 접근에서는 리사이즈 상태를 보호하지 않으면 한 스레드가 옛 버킷을 읽는 동안 다른 스레드가 원소를 옮겨 누락을 볼 수 있습니다. 전역 락, 버킷별 동기화, 불변 세대 교체 중 어떤 방식을 쓰는지 확인하겠습니다. 검증은 확장 직전·직후의 조회, 삭제와 재삽입, 반복자·참조 무효화, 메모리 피크, 최대 지연에서 누락·중복이 없는지 확인하는 방식으로 진행하겠습니다.

재해시 중 새 테이블과 옛 테이블을 함께 읽는다면 같은 키가 두 곳에 잠시 존재할 수 있습니다. 새 세대를 우선하고 옛 세대를 보조하는 조회 규칙, 갱신을 한 곳에만 적용하는 규칙, 복사·게시·옛 위치 정리의 순서를 정해야 합니다. 이동 완료를 표시하기 전에 옛 원소를 지우면 선점이나 장애 때 누락될 수 있습니다. 이동이 끝난 뒤에도 독자가 옛 배열의 참조를 들고 있을 수 있으므로, 모든 독자가 빠져나갔다는 회수 조건을 확인하기 전에는 옛 배열을 해제하면 안 됩니다.

축소도 부하가 다시 올라 확장과 축소가 반복되는 진동을 만들 수 있으므로 히스테리시스 임계값을 둡니다. 예상 크기 예약은 요청 경로 지연을 줄이지만 메모리를 선점합니다. 점진적 재해시라면 두 테이블 조회와 메모리 회수 조건까지 검증하고, 반복자·참조를 외부에 노출하는 API의 무효화 계약을 확인하겠습니다.

재해시를 요청 처리 중 동기적으로 수행하면 특정 요청의 p99가 튈 수 있고, 백그라운드로 넘기면 옛 세대가 오래 살아 메모리를 압박할 수 있습니다. 따라서 진행률·남은 원소 수·세대별 메모리를 관측하고, 일정 시간 안에 끝나지 않으면 새 확장을 막거나 요청을 제한하는 정책을 둡니다. 점진적 방식에서 삭제된 키가 다시 이동되는 경로와 재시작 복구도 필요합니다. 리사이즈 완료를 게시하는 순간은 모든 원소와 갱신이 새 테이블에 반영됐다는 원자적 전환이어야 하며, 그 뒤에만 옛 테이블을 회수하겠습니다.

점진적 재해시가 매 요청 한 버킷만 옮겨도 그 버킷에 충돌 키가 수만 개면 한 요청이 오래 걸립니다. 엄격한 지연 상한에는 버킷 수뿐 아니라 이동 원소 수나 시간 예산이 필요합니다. 읽기만 계속되는 서비스에서 이전 테이블이 영원히 남지 않도록 별도 진행 경로도 두되, 그 작업의 CPU와 새·옛 테이블 메모리를 전체 예산에 포함하겠습니다.