HashMap

hash_map 특징

• 트리를 통해 원소들을 정렬하지 않는다
• hash라는 자료구조를 통해 map,set 보다 빠른 검색속도를 가진다.

헤시함수

• 해시함수(hash function)란 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수입니다.
• 매핑 전 원래 데이터의 값을 키(key), 매핑 후 데이터의 값을 해시값(hash value), 매핑하는 과정 자체를 해싱(hashing)라고 합니다.

헤쉬테이블

• 해쉬테이블은 key값에 해쉬 함수를 적용시켜 얻은 값을 얻어, 해쉬 티이블에 분산하여 저장하는 자료 구조
• 저장 할때 key값을 해시 함수에 대입하여 버킷번호가 나오면 그 버킷의 빈슬롯에 자료를 저장한다.

헤시 테이블 장점

• 적은 리소스로 많은 데이터를 효율적으로 관리하기 위해서입니다.
• 해시함수로 무한에 가까운 데이터(키)들을 유한한 개수의 해시값으로 매핑함으로써 작은 크기의 캐쉬 메모리로도 프로세스를 관리할 수 있게 됩니다.

클러스터

• 일부 지역의 주소들을 집중적으로 반환 하는 결과로 데이터들이 한 곳에 모이는 문제

충돌

• 서로 다른 입력 값에 대해 동일한 해시값, 헤시 테이블 내에 동일한 주소를 반환하는 것

Chaining(체이닝)

• 충돌이 발생하면 각 데이터를 해당 주소에 있는 링크드 리스트에 삽입하여 문제를 해결하는 방법
• 개방해싱 알고리즘이다

 

Chaining(개방주소법)

• 충돌이 발생하면 해시 테이블 내의 새로운 주소를 탐사하여 충돌된 데이터를 입력하는 방식

 

 

Map,Set과의 차이점

• Map,Set : 정렬된 상태로 자료를 저장하고, 싶을 때 (범위 검색에 유용)
• hash_map, hash_set : 정렬이 필요 없고, 오직 빠른 검색을 원할 때 (단일 검색에 유용)

hash_map 사용시기

• 해시테이블은 많은 자료를 저장하고 있어도 검색이 빠르다.
• 그러나 저장한 자료가 적을 때는 메모리 낭비와 검색시 오버헤드가 생긴다.
• 컨테이너 추가나 삭제 하는 것은 list,vector,deque 보다 빠르다
• 수천의 자료를 저장하여 검색을 하는 경우 hash_map을 사용 하는 것이 좋다

hash_map 삽입 ( key타입, value 타입)

 m_hashmap.inset(hash_map<int,float>::Value_type(10,45.6f));     //key 10, value 45.6f 추가
 m_hashmap.inset(m_hashmap.begin() ,hash_map<int,float>::Value_type(10,45.6f));    //첫번쨰 위치에 추가
 m_hashmap.inset(m_hashmap.1.begin(),hashmap2end());  //hashmap1의 모든 요소를 hashmap2에 추가

hash_map 삭제 (erase)

hashmap1.erase(hashmap1.begin());    // 첫번쨰 위치의 요소 삭제
hashmap1.erase(hashmap1.begin(),hashmap1.end())  //begin()부터 end()까지 요소 삭제
hashmap1.(11)   // key가 11인 요소 삭제, 지정한 키와 같은 요소 삭제

hash_map 검색

• 검색은 key을 사용하여 같은 key을 가지고 있는 요소를 찾는다.
• key와 같은 요소를 찾으면, 그 요소의 반복자를 리턴한다.
• 못 찾은 경우 end()을 가리키는 반복자를 리턴한다.