[기술 면접] 8. Hash table은 어떤 자료구조인가요?

저번 시간에 이어, 이번엔 Hash table은 어떤 자료구조인지와 Collision 시 해결 방법에 대해 알아보겠습니다. 이번 시간은 자료구조 개념 중에 정말 중요하다고 할 수 있는 부분입니다. 서비스 플랫폼 기업 K사와 L사에서 마주한 기억이 있습니다.

Q: Hash table은 어떤 자료구조인가요?

효율적인 탐색(빠른 탐색)을 위한 자료구조로 key-value쌍의 데이터를 입력받습니다. hash function h에 key값을 입력하여 얻은 해시값 h(k)를 위치로 지정하여 key-value 데이터 쌍을 저장합니다. 저장/삭제/검색 시간 복잡도는 모두 O(1)이며 해당 공간을 slot 또는 bucket이라고 합니다.

• Direct-address Table : 직접 주소화 테이블로 key값으로 k를 갖는 원소는 index k에 저장합니다. 불필요한 공간 낭비와 다양한 자료형을 담을 수 없게 된다는 단점이 있습니다.

Q: Hash table에서 발생하는 Collision은 무엇이고 어떻게 해결할 수 있나요?

key의 해시값이 중복되는 경우를 말합니다. key가 다르더라도 해시값이 같을 수 있는데 이러한 collision이 적게 발생하고 연산속도가 빨라야 좋은 hash function이라고 할 수 있으며, 어쩔 수 없이 Collision이 발생한 경우 separate chaining이나 open addressing 등의 방식을 사용하여 해결합니다.

• separate chaining: Linked List를 사용하여 Collision 발생 시 노드(slot)를 추가하여 데이터를 저장합니다. 최악의 경우 O(n)이 발생할 수 있습니다.

• open addressing: Collision 발생 시 특정 규칙에 따라 hash table의 비어있는 slot을 찾습니다. 추가적인 메모리를 사용하지 않으므로, Linked List나 tree 자료구조를 사용하는 separate chaining방식에 비해 메모리를 적게 사용합니다. open addressing 방식은 찾는 방법에 따라 크게 Linear Probing, Quadratic Probing, Double Hashing으로 나뉩니다.
  • Linear Probing(선형 조사법) & Quadratic Probing(이차 조사법): 선형 조사법은 충돌이 발생한 해시값으로 부터 일정 값만큼 건너 뛰어 빈 slot에 데이터를 저장하며 이차 조사법은 제곱수로 건너 뛰어 빈 slot을 찾아 데이터를 저장합니다.
    • 충돌 횟수가 많아지면 특정 영역에 데이터가 집중적으로 몰리는 클러스터링 현상이 발생하여 평균 탐색 시간이 증가하게 된다는 단점이 있습니다.
  • Double Hashing(이중해시, 중복해시): Collision 시 open addressing 해결 방식 중 하나로, 클러스터링 문제가 발생하지 않도록 합니다. 최초의 해시값을 얻고 충돌 발생 시 또 다른 해시 함수를 이용합니다.

마치며

이번 시간에는 Hash Table과 Collision 해결 방법에 대해 알아보았습니다. 개념이 어려울 수 있지만, Collision 해결 방법에 대한 내용을 위와 같이 설명할 수 있다면, 면접관에게 깊은 인상을 줄수 있을 것입니다. 반드시 숙지하시길 권해드립니다.

다음 시간에는 퀵소트에 대해 알아보겠습니다.