[CS / Array vs Linked List] ep11. Hash table는 어떤 자료구조인가요?

🤔 면접 질문

 
Q1. Hash Table는 어떤 자료구조인가요?
 
A1. hash table은 효율적인 탐색(빠른 탐색)을 위한 자료구조로써 key-value쌍의 데이터를 입력받습니다. hash function h에 key값을 입력으로 넣어 얻은 해시값 h(k)를 위치로 지정하여 key- value 데이터 쌍을 저장합니다. 저장, 삭제, 검색의 시간 복잡도는 모두 O(1)입니다. 
 
 
 
 

💡 면접🐕🍯 tip

 
CS 면접에서 가장 자주 나오는 질문중에 하나다.
Hash table이 면접 단골질문인 이유는 다음과 같다.
 

☝ 실무에서도 활용도가 높은 자료구조다.
✌ Linked list, Array 더 나아가면 Tree까지
       질문할 수 있다.
🤟시간복잡도에 대해서 물어보기 좋다.

 
한편, 좋은 hash function의 조건을 물어보는 경우도 있다. 좋은 hash function의 핵심적인 조건은 해시값이 고르게 분포되게 하는 것이다.
 
 
 
 

🚀 심화 면접 질문

 
Q1. 좋은 hash function의 조건은 뭘까요?
 
A1. 각 상황마다 good hash function은 달라질 수 있으나 대략적인 기준은 연산 속도가 빨라야 하고, 해시값이 최대한 겹치지 않아야 합니다.