c++ map, hash tables, dictionaries (맵, 해시테이블, 딕셔너리) -only 간략한 개념 설명만

* 본문은 <C++로 구현하는 자료구조와 알고리즘>(범한서적주식회사, 2013)을 공부하면서 작성한 글입니다. 향후 객체지향 및 자료구조 수업을 들으며 정확한 + 최신 내용 이해를 반영하여 보완해 나갈 것입니다.

 

일단 수업 커리큘럼 범위에 포함되진 않으므로 호기심을 해결하는 수준의 공부만 하고, 코드는 후에 필요할 경우에 공부한다.

 

 

1. Map

파이썬의 딕셔너리 타입과 동일한 개념이다. STL을 지원하며, size(), empty(), find(K), operator[k] (키 k의 값에 대한 레퍼런스 생성. 키가 없으면 키 k를 갖는 새로운 엔트리 생성), insert(pair(k,v))(그 위치에 대한 반복자 반환), erase(k), erase(p) (반복자 p가 가리키는 엔트리 삭제), begin(), end() 같은 메서드가 포함되어 있다.

 

아래는 사용 예시 코드다.

 

 

 

2. Hash Tables

- 엔트리는 키&값 쌍인 (k,v)를 말하는 것이다.

- 블록체인에서도 나왔던 그 원래 해시의 의미: 임의값을 고정 길이로 변환하는 것

- 해싱 함수(Hashing Function): Key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수

- 키: 원소에 대한 '주소'

- 해시 테이블을 사용할 경우 맵 연산의 실행 시간은 최악의 경우 O(n) 이지만, 해시 테이블은 평균 O(1) 시간에 실행할 수 있다.

- 해시 테이블 구성: 버켓 배열과 해시 함수로 구성

 

장점
  - 데이터 저장/읽기 속도가 빠르다. (검색 속도가 빠르다.)
  - 해쉬는 키에 대한 데이터가 있는지(중복) 확인이 쉬움: 배열은 원하는 데이터가 있는지 찾으려면 (검색 기법이 다양하긴 하지만) 일일이 검색해야 하는 것과 대조됨. 이런 데이터 검색은 데이터 중복 검사에도 응용!

 

단점 
  - 일반적으로 저장공간이 좀더 많이 필요하다: 바로 밑에서 설명하는 "나누는 수(이거 뭐라그러더라...)"가 너무 작으면 안되는 이유와 같은 내용이다. 필연적으로 어느 정도 크기의 테이블이 필요한 것.
  - ⭐️여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요함: 이게 뭔소린가 하니, 해시테이블 각 테이블 당 데이터 한개만 저장한단 가정하에 그렇다는 거였음... 난 당연히 한 테이블 당 링크드 리스트 하나 정도는 될 줄.... 알고보니 이 링크드리스트는 필수적인 부분이 아녔으며, 이 부분이 바로 저 말에서 "별도 자료구조"를 지칭하는 것이었다. 그래서, 예를 들어 숫자를 테이블 수로 나눠 나온 나머지 값이 해시 테이블의 어느 위치에 저장할지 결정하는 "Division법" 해시 테이블의 경우, 테이블의 수가 더 크다면 (나누는 수가 더 크다면) 추가적 자료구조도 없으면서 중복이 덜할 수 있는 해시테이블이 된다.

 

주요 용도
  - 검색이 많이 필요한 경우
  - 저장, 삭제, 읽기가 빈번한 경우
  - 캐쉬 구현시 (중복 확인이 쉽기 때문)

  - 컴파일러의 심벌 테이블, 환경 변수의 레지스트리 <---심벌 이름들로 구성. 각 이름들이 변수의 타입과 값들에 대한 주소 역할.

 

코드는 아래 링크로 공부하고 있었지만 그냥 stl 쓰거나 필요하면 그냥 내가 짜는걸로... 만족할 만한 오픈소스 코드를 찾지 못했다.

http://www.algolist.net/Data_structures/Hash_table/Chaining

 

 

3. Dictionary

이 역시 엔트리로 저장하는 자료구조다. 맵에서는 엔트리들이 유일한 키를 가져야 하는 반면, 딕셔너리에서는 여러 엔트리들이 같은 키를 가질 수 있다. 갖은 단어가 복수의 정의를 가질 수 있는 영어 사전과 같다고 볼 수 있다.

딕셔너리의 응용 분야로는 다음과 같은 것을 들 수 있다 - 

- 저자 리스트를 만들었다고 했을 때, 실제 서로 다른 저자들이 같은 성과 이름을 가질 수 있기 때문에 같은 키를 갖는 엔트리를 다뤄야 하는 경우가 발생한다.

- 큰 성의 여러 방을 방문하는 플레이어드을 포함하는 멀티유저 컴퓨터 게임. 이 경우 방과 플레이어 간의 매핑이 필요할 수 있다.