맵과 해쉬의 차이는 무엇인가?
맵 (Map) 과 해쉬 (Hash) 의 차이는 무엇인가?
일단 먼저 맵과 해쉬는 연관 컨테이너(Associative Container)이며 순서를 유지하는 것이 아닌 빠른 검색하는 과정에 초점을 맞춘 컨테이너이다.
맵 (Map)과 해쉬 (Hash)
https://doanhan.tistory.com/28?category=581362
[C++] 연관 컨테이너, 집합과 맵
[C++] 연관 컨테이너, 집합과 맵 연관 컨테이너 (Associative Container) 삽입/제거된 요소의 순서를 유지는 하는 순차컨테이너의 특성을 무시하고 요소를 검색하는 과정을 최대한 빠르게 수행하는데
doanhan.tistory.com
맵은 같은 Key 값을 가지는 Pair들을 저장하는 컨테이너로 같은 Key값을 가지는 Pair는 최대 한개만 존재한다.(Multi Map 예외) 주로 전화번호부에서 전화번호(Key)와 이름(Value)에 이용할 수 있다.
맵을 구현하는 방법은 hash table, tree-based 두가지가 있다. C++ STL에서는 맵을 트리 구조 중 정렬이 된 이진 탐색트리인 RBT(Red Black Tree) 구현되어 있다. 그런데 이 정렬이 되어있다는 점이 불필요한 오버헤드를 불러일으킬수 있다. 그래서 정렬을 하지 않는 다른 방법이 해쉬 테이블(Hash table)이다. 이것은 배열과 해쉬 함수(Hash function)를 사용하여 map을 구현한 자료구조이다.
https://doanhan.tistory.com/32?category=581362
[C++] 해시 (Hash)
[C++] 해시 (Hash) 해시 (Hash) 해시는 해시함수의 결과물이며, 저장소에서 값과 매칭되어 저장되며 해시테이블의 구성 요소이다. ▹ 이진 트리가 아닌 해시 테이블로 구성되어있다. ▹ 올바른 키와
doanhan.tistory.com
위처럼 해쉬 함수를 통해서 Key의 값으로 어떠한 정수가 나오게 되는데 이것을 해쉬(Hash)라고 한다.
맵과 해쉬의 차이를 말하자면 일단 맵은 이진 탐색 트리를 베이스로 하기 때문에 정렬이 되어있지만 해쉬는 그렇지 않다. 그리고 시간복잡도는 맵은 O(logN) 적절한 해쉬 함수를 사용한 해쉬는 O(1)로 해쉬가 더 빠르다고 할 수 있다.