해시 버킷이란 무엇인가요?

해시 버킷이란?

컴퓨팅에서 해시 테이블 [해시 맵]은 키 [고유한 문자열이나 정수]를 기반으로 개체에 사실상 직접적인 액세스를 제공하는 데이터 구조를 말합니다. 해시 테이블은 해시 함수를 사용해 인덱스를 버킷이나 슬롯 어레이로 연산하는데, 여기에서 원하는 값을 찾을 수 있습니다. 여기에 사용되는 키의 주된 특징을 소개합니다.

• 사용되는 키는 SSN, 전화번호, 계좌 번호 등 무엇이든 가능
• 반드시 고유한 키가 있어야 함
• 각각의 키가 값과 연결됨(즉 값에 매핑됨)

해시 버킷은 정렬이나 검색 용도로 데이터 항목을 배분하는 데 쓰입니다. 이 작업의 목표는 서로 연결된 목록을 약화하여 특정 항목의 검색 결과에 짧은 기간 내에 액세스할 수 있게 하는 것입니다. 버킷을 사용하는 해시 테이블은 사실상 어레이 하나와 연결된 목록 하나의 조합이라고 할 수 있습니다. 어레이의 각 요소 [해시 테이블]가 연결된 목록의 헤더가 됩니다. 같은 위치로 해시되는 모든 요소가 해당 목록에 저장됩니다. 해시 함수가 각각의 레코드를 버킷 중 하나에 속한 첫 슬롯에 할당합니다. 슬롯에 이미 자리가 찬 경우, 버킷 슬롯을 차례로 검색하여 열린 슬롯을 찾아냅니다. 버킷이 완전히 꽉 찬 경우, 해당 레코드는 테이블 끝에 있는 무한 용량 오버플로 버킷에 저장됩니다. 모든 버킷이 같은 오버플로 버킷을 공유합니다. 다만 잘 된 구현이라면 레코드를 여러 버킷에 골고루 분배하는 해시 함수를 써서 오버플로 버킷에 들어가는 레코드를 가능한 한 적게 합니다.

추가 자료

• 대규모 악용 사례 탐지: Uber Engineering의 LSH(Locality Sensitive Hashing)
• 버킷 예시 노트