꿈 꾸는 누렁이

자 오늘은 테이블과 해시이다.

자료구조는 자료를 저장하는 구조를 나타내는 것이지만, 그 구조 속에 들어 있는 값을 찾아서 꺼내는 것 또한 자료 구조의 영역 범위 내이다.

그래서 배열 리스트, 연결 리스트, 스택, 큐, 그래프, 트리 등에서 탐색에 해당하는 부분을 구현해왔다. 그 중 테이블이라는 자료구조에 대해 볼 것인데, 이 구조는 특별하다. 탐색 속도가 어마어마하게 빠르다. 기록해보자.

테이블이란 무엇인가?

이것이 테이블 자료구조이다. 키와 값으로 구성되어 있는 구조를 테이블 자료구조이다. 보통 언어에 따라 다르지만 키와 값으로 구성되어있는 자료구조를 사전(Dictionary), 맵(Map) 구조라고도 한다.

테이블 자료 구조에서의 핵 중요한 규칙

1. 테이블 자료구조에서는 키와 값이 한 쌍의 형태로 이루어 저장이 된다.
이 때 값은 뭐 하나가 되어도 좋고 여럿이 되어도 좋다.

2. 테이블 자료구조에서는 키 값은 중복되어서는 아니 된다.
아래의 그림을 보자

학생을 관리하는 테이블이다. 소위 말하는 학번이라는 것은 각 학생들에게 부여되는 고유 번호이다. 그러니까 학번 1번을 외치는 것만으로도 수 많은 학생들 중에서 '나루토'를 특정 지을 수 있어야한다. 이것이 실생활에서 적용되는 예이다. 

그런데 위의 테이블에서 학번 3번을 부르면 네! 하고 손을 드는 학생이 에렌과 아르민으로 두 명인 상황이 만들어졌다. 이런 경우에는 학번을 부르고 나서 이름까지 불러야 그제서야 에렌과 아르민을 특정 지을 수 있는 것이다.

만약 이런 상황에서 3번으로 중복되는 에렌과 아르민이 포함되어 있는 전교생 수천명이 시험을 본다고 생각하자. 그러면 자동적으로 OMR 채점을 진행할텐데 이 때 기계는 각 학생들을 구분할 때, 학번을 이용하여 학생을 특정 짓지만 에렌과 아르민 자식들이 포함되어 있는 경우가 존재하기 때문에 모든 학생들을 대상으로 학번과 이름을 한 번에 확인해야한다.

테이블 자료구조에는 보통 키 값을 이용하여 데이터를 특정짓기 때문에 위와 같은 경우를 만들지 않기 위해서 키의 중복을 허용하지 않도록 하겠다. (뭐 허용을 시키는 경우도 있긴 하지만 말이다.)

3. 키가 없으면 값을 저장할 수 없다.

키를 활용해 값을 특정 지어야 하기 때문에 키를 비울 수는 없다.

4. 값을 특정 짓는다는 것의 의미.

위 그림을 봤을 때, 3번이라는 학번을 통해 에렌을 특정 지었는데 달리 말하면 탐색이 완료되었다는 소리이다. 

이 개념들을 숙지한 채로 아래의 예시를 보면 된다.

기본적인 테이블 예시

테이블이 될 구조체 정의

구조체 정의를 이용하여 배열로 선언하면 테이블 형태의 구조를 만들 수 있다.

테이블에 데이터를 등록하는 함수

인덱싱이 특이하다는 것을 확인할 수 있다.

메인 함수 실행 부분

임의로 입력된 값을 키 값으로 활용한다.

49번 줄에서는 키 값을 이용해 원하는 값을 바로 뽑아낸다. 이런 것이 가능한 이유가 무엇인가? 

데이터를 삽입할 때, 키의 값 '번째'에 해당하는 배열 칸에 넣었으니,

값을 뽑아올 때에도 키를 인덱스로 던져주면 키의 값 '번째'에 해당하는 배열 칸에서 뽑아온다.

말이 탐색이지, 사실 탐색이라고 할 것도 없이 그냥 인덱싱일 뿐이다. 그냥 *(배열이름+인덱스(키값)) 이렇게 연산해주면 접근 가능하기 때문에 포스팅 초반에 겁나 빠르다고 한 것이다.

전체 코드 및 실행 결과

문제점

근데 위와 같은 테이블은 빠른건 빠른거지만 중요한 문제가 있다.

1. 학번이 원래 0부터 100까지의 자리였지만 갑자기 년도+번호와 같은 식으로 변해버리면 분명히 문제가 된다.
원래 99번이었던 번호가 20210099로 바뀐다면 이 또한 문제가 될 것이다. 

기존의 방법대로라면 user acc[20210100]; 이렇게 선언을 해야, 20210099 같은 인덱스가 먹혀도 먹힐 것이다. 그런데 이러한 크기의 배열 선언이 과연 정상일까?

모든 키가 0부터 시작해서 뭐 적절히 1,000 값으로 끝나면 좋겠지만 실제로는 그렇지가 않다. 학번은 보통 해당 년도와 고유 번호를 합쳐서 만든다. 군번은 말할 것도 없다 이런 번호 키들을 수용하기 위해서 user acc[20210100]; 이렇게 비정상적인 배열 선언을 할 수도 없는 노릇이다.

이를 다음 포스팅 때 해결하고자 한다.

Map은 연관 컨테이너에 속하는 컨테이너의 한 종류이다. 파이썬의 Dictionary 사전과 같은 자료구조를 갖는다.

Map은 사전처럼 Key(단어)를 갖고, 그 Key에 해당하는 Value(뜻)를 갖는다. 왼쪽 그림처럼 Apple이라는 단어를 찾으면 사과라는 뜻이 나오 듯, key 값을 넣으면 value 값이 나오는 형태이다.

Map에 자료를 추가하거나, 자료를 찾기 위해서는 insert(), find() 등의 함수를 사용하지만 Map의 특성으로 인해서 추가와 탐색을 한 형태로 나타낼 수 있다.

첫 번째, 기존의 동일한 key가 map에 존재하는데, 동일한 key로 다시 value 값을 등록하는 경우는 갱신된다.
두 번째, 기존의 동일한 key가 map에 존재한다면, 기존의 key값에 해당하는 value 값을 반환시킬 수 있다.
세 번째, key가 map에 존재하지 않는데, key로 value 값을 등록하는 경우 map에 새롭게 추가된다.
네 번째, key가 map에 존재하지 않는다면, key 자체도 없고 그에 따라서 value도 없으므로 반환되는 값이 없다.

간단한 예제로 마무리 지을 것이다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

// https://colorscripter.com/ #include <iostream> #include <string> #include <map>   using namespace std;   int main(void) {     map<string, string> my_map; // key에 해당하는 string, value에 해당하는 string       my_map["a"] = "apple";     my_map["b"] = "banana";     my_map["c"] = "carrot";       cout << "--- key로 접근하여 value을 출력하기. " << endl;     cout << my_map["a"] << endl;     cout << my_map["b"] << endl;     cout << my_map["c"] << endl;       cout << "--- iterator 이용하여 key와 value 출력하기. " << endl;     map<string, string>::iterator it;     for (it = my_map.begin(); it != my_map.end(); it++)         cout << it->first << " : " << it->second << endl;       return 0; }   Colored by Color Scripter

cs

10번 라인과 같이 key 값의 자료형과, value 값의 자료형들을 명시해야한다. 또한 22번 라인에도 또한 동일한 자료형을 명시하여 iterator 선언해야한다.

24번 라인에서 map내의 iterator 클래스의 멤버 first와 second는 각각 key와 value를 나타낸다.

map을 공부하다보니 pair 및 multimap도 관련이 생기고, tuple도 정리해야겠다는 생각이 들었다.

다음 시간에 정리해보자.