[1분 면접] 해시 충돌에 대해서 설명해주세요.

📌 해시 충돌

해시 key-value 쌍으로 이뤄진 자료 구조로, Key 값을 사용하여 조회 O(1) 시작 복잡도로 찾을 수 있다.

해시 자료 구조는 키를 해시 함수에 넣어서 나오는 결과를 기반으로 값을 관리는데,

서로 다른 키가 동일한 결과가 나오는 경우를 해시 충돌이라고 한다. 

 

해시 충돌 완화

1. 개방 주소법 (Open Addressing)

• 특정 값이 들어가야 하는 버킷이 이미 사용되고 있는 경우, 다른 해시 버킷에 데이터 삽입

 

2. 분리 연결법 (Separate Chaining)

• 버킷을 연결 리스트나 트리 형태로 관리하여 버킷에 들어갈 값의 수에 제한을 두지 않음

 

 

해시 테이블 만들어지는 로직 

https://wodonggun.github.io/algorithm/%ED%95%B4%EC%8B%9C-%EC%A0%95%EB%A6%AC.html

1. Key 값을 Hash Function에 넣으면 Hash code가 생성된다. 
2. 적적한 로직으로 Hash code를 인덱스로 변환해준다.
3. 그리고 해당 인덱스에 데이터를 저장한다. 
4. 만일 데이터가 이미 존재하는 경우 Open Addressing 또는 Separate Chaining으로 해결한다. 

(참고로 버킷은 해시 테이블에서 같은 인덱스에 저장되어있는 묶음을 의미한다.)

---

📌 내 답변

해시 충돌은 해시 자료구조에서 발생하는 현상이다.

해시는 미리 제한된 크기의 배열 구조를 갖는다.

그리고 특정 값을 해시 함수를 통해 해시 코드로 만들고 이를 이용하여 배열의 인덱스로 만든다.

이 과정에서 동일한 인덱스가 나올 수 있는게, 이것을 해시 충돌이라고 부른다. 

예를 들어 해시 코드가 10, 20이고 배열의 인덱스를 구하는 로직이 %10이라면 둘다 똑같이 0의 해시 인덱스를 갖게된다.

그리고 이 결과 해시 충돌이 발생하는것이다. 이러한 상황에서는 해당 해시 코드들을 연결리스트로 만들어서 해시 충돌 현상을 해결 할 수 있다.

 

Self Feedback

• Hash code, Hash Function, 버킷 용어가 헷갈림
• 충돌 해결 방법에 대해서 연결 리스트 방식만 제안함

---

[출처 및 참고 자료]

http://maeil-mail.kr/question/147

매일메일 - 기술 면접 질문 구독 서비스