Hash
개념
- 임의의 크기를 가진 데이터(Key)를 고정된 크기의 데이터(Value)로 변화시켜 저장하는 것
- 키에 대한 해시값을 사용하여 값을 저장하고 키-값 쌍의 개수에 따라 동적으로 크기가 증가하는 associate array이다
- 키에 대한 해시값을 구하는 과정을 hashing(해싱)이라고 하며 이때 사용하는 함수(알고리즘)를 해시함수라고 한다
- 해시값 자체를 index로 사용하기 때문에 평균 시간 복잡도가 O(1)로 매우 빠르다
해시함수
- 위에 설명한 것과 같이 키에 대한 해시값을 만드는 함수
- 계산이 복잡하지 않고 키값에 대해 중복 없이 해시값을 고르게 만들어 내는 함수가 좋은 함수 (충돌이 일어나지 않을수록 좋다)
- 대표적으로 나눗셈 법(Division Method)과 곱셉 법(Multiplication Method)이 있다
map container
- Associative - 연관 컨테이너 (associative container) 중 하나입니다.
- 노드 기반으로 이루어져 있고 균형 이진트리 구조입니다.
- Map - map은 key와 value로 이루어져 있으며 이는 pair 객체 형태로 저장됩니다.
- Unique Key - key는 고유한 값이므로 중복이 불가능합니다. (중복 key는 multimap에서 가능합니다.)
- Ordered - map도 set과 마찬가지로 삽입이 되면서 자동으로 정렬이 됩니다. (default는 less/오름차순입니다.)
- Allocator-aware - map container는 저장공간의 필요에 따라서 allocator 객체를 사용합니다. (동적 할당합니다.)
- 그림으로 대략적인 모습을 보겠습니다.
map의 사용법
- <map> 헤더 파일에 포함됩니다.
- 기본 생성 방법은 : map < [Data type 1], [Data type 2] > [변수 이름];
ex) map <int, int> m1;
ex) map <string, int> m2;
- map에 삽입을 하기 위한 insert는 pair 객체를 인자로 받아야 합니다. (key 값과 value는 쌍을 이루기 때문)
- ex) m1.insert(pair <int, int>(10, 20));
ex) m2.insert(pair <string, int>("BlockDMask", 27));
map의 생성자와 연산자
- map <int, int> m;
- 기본 선언 방법
- map m(pred);
- pred를 통해 정렬 기준(오름, 내림)을 세웁니다.
- map m2(m1);
- m1을 복사한 m2를 생성합니다.
- 연산자 ("==", "!=", "<", ">", "<=", ">=") 사용 가능합니다.
- 연산자 m [key] = val; 을 통해서 원소( key, value )를 추가 또는 수정이 가능합니다.
