[알고리즘] 해시 테이블

map vs hash_map

map : 레드 블랙 트리

추가, 탐색, 삭제가 logN의 시간복잡도를 가짐

hash map(unordered_map)

추가, 탐색, 삭제가 1의 시간복잡도를 가짐

 

hash_map은 메모리를 내주고 속도를 취한다.

예를 들면 유저의 수대로 메모리에 공간을 만들어 거기에 데이터를 집어넣는 것이다.

이러한 방식을 테이블이라고 하고, 키를 알면 데이터를 바로 알아낼 수 있다.

 

그리고 해시는 보안 때문에 데이터를 임의의 값으로 바꾸는 것이다.

간혹 해시(키)값이 중복해서 충돌하는 문제가 발생하는데, 해결방법은 선형 조사법, 이차 조사법이 있다.

선형 조사법: 해시 키에 충돌하지 않을 때까지 1씩 더함

이차 조사법: 더 분산된 키를 넣는 방법으로 1^2, 2^2씩 더함 

 

MMORPG처럼 데이터가 엄청 많을 경우 체이닝을 이용할 수 있다.

키당 한값만 넣는 것이 아니라 키 하나에 여러 값이 들어간 리스트 등이 들어가는 것이다.