Hash

title: 2025-12-21 author: 강병호 date: 2025-12-21 category: TIL/강병호/2025/12 (파일 경로 : TIL/{이름}/{연}/{월}) layout: post (자유) —

해시(Hash) 자료 구조는 키값 쌍으로 이루어진 데이터 구조로 키를 이용해 값을 O(1) 시간 복잡도로 찾을 수 있습니다. 해시 자료 구조는 키를 해시 함수에 넣어서 나오는 결과를 기반으로 값을 관리하는데요. 해시 함수는 다른 키를 사용해도 같은 결과가 나오는 경우가 존재합니다. 이를 해시 충돌(Hash Collision) 이라고 합니다.

해시 충돌은 어떻게 완화하는가?

해시 충돌을 완화하기 위한 접근 방법으로 개방 주소법과 분리 연결법이 대표적인데요. 개방 주소법(Open Addressing) 은 특정 값이 들어가야 하는 자리(버킷)가 이미 사용되고 있는 경우 다른 해시 버킷에 데이터를 삽입하는 반면, 분리 연결법(Separate Chaining) 은 버킷을 연결 리스트나 트리 형태로 관리하여 버킷에 들어갈 값의 수에 제한을 두지 않도록 하여 충돌을 완화합니다.