Technical Interview Master Plan [1] - Hash Map을 알아도 왜 빈도수·중복 문제에서 자꾸 막히는가

코딩인터뷰를 위해 Hash Maps 그리고 Sets 에 대해 알아봅니다.

Hash Maps 그리고 Sets.

Introduction to Hash Maps and Sets

마트에서 일하는 상황을 떠올려 보겠습니다. 여기서 고객은 과일의 가격을 물었습니다. 만약 당신이 과일 리스트에 대한 종이 목록을 가지고 있다면, 과일 리스트를 보고 특정 과일을 찾기 위해 목록을 하나하나 찾아야 하죠. 아마 이 작업은 시간이 걸릴겁니다. 과일 리스트가 길어지면 길어질 수록 시간이 더 걸리게 되는 것 입니다. 그러나 과일 리스트를 기억하고 있다면, 모든 과일에 대한 가격을 즉시 알 수 있습니다. 그렇게 되면 바로 고객에게 특정 과일에 대한 가격을 알려줄 수 있을 것입니다. 이 작업이 hash maps 의 작업방식이며, 정보를 빨리 찾는것을 가능하게 해줍니다.

Hash maps

해시맵은 Hash table 해시테이블 또는 Dictionary 딕셔너리로 많이 알려져 있습니다. 이는 언어에 따라 달라집니다. 해시맵은 키(Key) 와 (Value)값을 쌍으로 저장하는 데이터 구조 입니다. 자, 그럼 과일 그리고 과일의 가격을 예시로 어떻게 구성될 수 있는지 알아보겠습니다.

Fruit ----------> Price
apple -----------> 5.00
bananas ---------> 4.50
carrot ----------> 2.75 

과일 가격에 대한 머릿속 지도를 가지고 있는 것은 개념적으로 해시 맵을 사용하여 과일 가격에 즉시 접근하는 것과
유사합니다. 여기서 과일 이름은 키(Key) 이고 가격은 값(Value) 입니다. 과일 이름을 키로 사용해서 가격을 조회하면,
해시 맵은 즉시 그 가격을 반환합니다. 

hashmap
key      value 
---------------
apple   | 5.00
bananas | 4.50 
carrot  | 2.75

해시 맵은 조회(lookup), 삽입(insertion), 삭제(deletion) 에 대해 매우 효율적이며, 이러한 연산을 일반적으로 상수 시간인 O(1) 에 수행합니다. 해시 맵은 컴퓨터 과학에서 가장 다재다능하고 널리 사용되는 자료구조 중 하나이며, 요소의 빈도를 세는 작업, 데이터 캐싱 등과 같은 다양한 작업에 사용될 수 있습니다.

해시 맵의 속성, Properties of hash maps