[251128금] 해시 충돌에 대해서 설명해주세요

해시(Hash) 자료 구조란?

: 키-값쌍으로 이뤄진 자료구조로, 키를 통해 값을 O(1)로 찾을 수 있다. 

 

해시 충돌이란?

: 다른 키를 사용해도 같은 결과가 나올때 해시 충돌이 난다.

 

해시 충돌 완화 방법은?

1) 개방 주소법 : 특정 값이 들어가야 하는 자리가 이미 사용되고 있는 경우 다른 해시 버킷(자리)에 데티어 삽입

  - 선형 탐사법 : 임의의 고정된 크기만큼 한 칸씩 옮기면서 빈 버킷을 찾는 방법

  - 제곱 탐사법 : 한 칸 씩이 아니라 제곱으로 늘리면서 빈 버킷을 찾는 방법

  - 이중 해싱 : 보조 해싱 방법을 하용하는 방법

 

2) 분리 연결법 : 연결리스트나 트리 형태로 관리하여 버킷에 들어가여 값의 수에 제한을 두지 않음