해시테이블,HashTable

map vs hash_map

map

- stl container map은 균형 이진 트리인 레드 블랙트리로 이루어져 있다.

- 삽입/삭제/검색 시간 복잡도는 O(logN)이다.

 

hasp_map

- c++11 표준 기준으로 unorder_map이다.

- 삽입/삭제/검색 시간 복잡도는 O(1)이다

- 해시값일 이용해서 데이터를 관리한다. 때문에 많은 메모리를 사용하고 대신에 속도가 빠르다.

- 해쉬값을 관리하는 방법에는 선형 조사법(inear probing), 이차 조사법(quadramic probing), 체이닝 등이 있다.

 

C# dictionary는 무엇일까?

c# dictionary = c++ map (x)

c# dictionary = hash_map(c++ unordered_map)