꿈 꾸는 누렁이

지난 이야기..

문제점

뭐 위와 같은 문제들이 있다. 위의 문제의 전제는 등록되는 수는 100명도 안되고, 거의 그대로지만 번호만 오지게 큰 스케일로 변환되는 경우이다. 

해결 아이디어

그러면 어떻게 하면 될까? 

큰 인덱스 키 값의 크기를 줄이면 된다!

<인덱스를 축소 변환하는 과정>

1. 어차피 등록되는 인원은 100명이 안될 것이기 때문에 20171300 ~ 20171399 라고 범위를 어림 잡는다 
2. 그러면 말이 20171300 부터 20171399까지 이지 결국엔 0부터 99까지라고 봐도 문제가 없다.
3. 그렇다면 인덱스를 대입하기 전에 20171300이 오면 무조건 0으로 변환해주고, 20171344가 오면 무조건 44로 변환해주며, 20171399가 오면 무조건 99로 변환해주어 인덱스에 대입되도록 하면 어떨까?
4. 등록번호 % 100 을 한 결과라면 무조건적으로 위의 결과를 얻는다.
5. 그렇다면 user acc[100] 을 그대로 넣고 acc[uid%100] 으로 접근하면 배열의 크기를 비정상적으로 늘리는 고민을 해볼 필요도 없게되는 것이다.

이러한 과정에서 축소 변환해주는 역할을 하는 것을 해쉬(hash)라고 하며, 해당 역할을 하는 함수를 해쉬 함수라고 한다.

해쉬 함수는 다음과 같다. 겁나 간단하다.

이러한 해쉬 함수는 위에서 밑줄 친 것처럼 다양한 값의 형태에 따라 달라진다. 해쉬되어야 할 키 값의 상황? 문맥? 에 따라서 적용되는 해쉬 함수의 내용이 달라지고, 정답이 없다는 뜻이다.

적용된 코드 분석

등록을 할 때에 hash 함수를 이용하며,

값을 꺼낼 때에도 hash 함수를 이용하여 인덱스를 축소 변환하여 인덱싱한다.

전체 코드 및 실행 결과

그런데 또 문제점

짜증나게 또 문제가 발생하는 것이다.. 이번엔 등록해야하는 수가 갑자기 늘어나 버려서 다음과 같은 현상이 발생하는 것이다. 

1. 한 200명~300명 정도 난다.
2. 그래서 배열의 길이를 넉넉하게 user acc[400]; 정도로 주었다.
-> 이 방법 또한 썩 마음에 들지 않는다. 왜냐하면 등록 수가 늘어날때마다 계속 변경을 해줘야 하기 때문이다.
3. 그런데 문제는 여기서부터이다. 20171350과 20171450의 해쉬 결과는 50으로 같다.
-> 왜냐하면 100으로 나눈 나머지이기 때문에!(직접 나눠보라)
4. 20171350 등록 번호인 사람과 20171450 등록번호인 사람의 해쉬 결과가 50으로 같으므로 둘다 acc[50]에 정보가 등록될 것이다.. 그러니까 먼저 저장되는 값은 손실 된다는 의미이다. 원래 기대 결과는 20171350은 [50]에 20171450은 [150] 에 저장되는 것을 기대했는데 말이다.

지금 두 가지 문제가 발생하였다.

첫 번째는 문제는 등록되는 수가 넘쳐날 때마다 테이블의 크기를 갱신해야하는 상황이 발생한다.

두 번째는 문제는 분명히 다른 등록번호임에도 불구하고, 해쉬된 결과로 같은 인덱싱 번호가 나왔다. 

먼저, 두 번째 문제와 같이 같은 해쉬 결과가 나오는 것을 충돌(Collision)이라고 한다. 이러한 충돌을 막으려면 어떻게 해야할까? 해쉬 함수를 기가 막히게 잘 만들어야 한다. 해쉬 함수는 해쉬하려고 넘어오는 키 값의 범위나 종류나 형태, 양상에 따라 달라질 수 있기 때문에 매우 주관적이며, 답이 없다. 

A회사에서 만든 해쉬 함수가 기가 막히게 성능이 잘 나오다가도 B회사에서 A회사의 해쉬 함수를 쓰면 동작이 잘 안될 수도 있다. 그렇지만 최대한 공통으로 적용할 수 있는 여러 알고리즘? 들이 존재한다.

자릿수 선택, 폴딩 방법, 선형 조사법, 이차 조사법, 이중 해쉬, 체이닝 ... 등

이렇게 여러 방법들이 존재하지만 이 방법들의 공통점은 해쉬 해야할 키 값을 어떻게 변환해야 충돌이 덜 일어나는가에서부터 시작하는 방법들이다.

가장 좋은 해쉬 방법을 만드는 것은 키 값의 부분을 활용하여 해쉬된 키 값을 만들 것이 아니라, 키 값의 전체를 활용하여 해쉬된 키 값을 만들어야 한다는 것이다.

위의 예제에서도 키 값의 마지막 두 자리 수만 가지고 장난질 했기 때문에 문제가 되었다. 키 전체를 활용할수록 콜리전이 발생할 확률이 매우 낮아진다.

첫 번째 문제는 해쉬 함수의 구현에 따라 달라진다. 해쉬 함수를 통해 변환되는 해쉬된 키 값의 범위를 어떻게 정하느냐에 따라 적절한 할당 크기를 정할 수 있기 때문이다.

테이블과 해쉬 등은 성능은 좋지만 이러한 충돌(collision) 문제로 인해, 그리고 키를 이용하여 제어해야하는 곳에서만 주로 사용해야하기 때문에 사용되는 곳이 제한된다. 

테이블과 해쉬를 살펴봤는데 해쉬 테이블은 기본 동작 원리나 문제점 그리고 적용 가능한 작업의 특징 정도로만 공부하고 넘어가는게 좋을 것 같다.

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

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

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

테이블이란 무엇인가?

이것이 테이블 자료구조이다. 키와 값으로 구성되어 있는 구조를 테이블 자료구조이다. 보통 언어에 따라 다르지만 키와 값으로 구성되어있는 자료구조를 사전(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]; 이렇게 비정상적인 배열 선언을 할 수도 없는 노릇이다.

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