Hash 개념 정리, std::unordered_map

1. 해시 테이블이란

해시테이블은 key, value로 데이터를 저장하는 자료구조이다.

[해시함수]

ex) 1~10의 값을 저장할 때, %연산을 이용하여 배열크기를 줄여 사용

%연산이 같은 두개이상의 원소를 같은 배열원소에 넣는 경우. 이 때 충돌이 발생할 수 있다.

 

 

2. #include <unordered_map>

해시 테이블로 구현한 자료구조로 map보다 더 빠른 탐색이 가능하다.

중복된 데이터를 허용하지 않고, map에 비해 데이터가 많을 시 더 좋은 성능을 보인다.

empty()	맵이 비어있는지 확인하는 함수 비어있으면 1을 반환한다.
size()
operator [] um [ "key" ] = 2;	map_name[key] = value
find(key)	key에 해당하는 원소를 찾는 함수
count(key)	key에 해당하는 원소의 개수를 반환하는 함수
insert( {key, value} ) ex) um.insert(make_pair("key", 1);	pair <key, value> 를 추가하는 함수
erase ( key)
clear()
operator =
unordered_map <string, int> um;
탐색방법 begin(), end() key : iter->first, value : iter->second 반복문 사용시 auto , pair< key_type, value_type>

 

std::map 은 키의 순서를 유지한다

std::unordered_map은 해시테이블을 사용해 키의 순서를 유지하지 않는다.