꿈 꾸는 누렁이

지난 이야기..

문제점

뭐 위와 같은 문제들이 있다. 위의 문제의 전제는 등록되는 수는 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]; 이렇게 비정상적인 배열 선언을 할 수도 없는 노릇이다.

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

멤버함수 가상함수의 동작 원리

• 가상함수

객체 포인터가 참조를 할 때, 포인터 연산의 기준으로 두는 것은 실제 가리키는 객체의 자료형이 아니라, 선언된 포인터의 자료형을 기준으로 한다. 그로 인해 포인터 변수의 자료형에 따라서 호출되는 함수의 종류가 달라진다.

이와 같은 상황을 발생하지 않도록 가상함수 라는 문법을 제공.

위 소스에서 포인터 변수의 자료형을 기준으로 판단하여 호출되는 함수를 결정하는 상황을 발생시킬 수 있는 오버라이딩 된 함수들이다. 이러한 오버라이딩 된 함수들을 "가상 함수"로 만듦으로써, 실제 가리키는 객체의 자료형을 기준으로 판단하여 호출 함수를 결정하게 만들 수 있다.

가상함수로 만드는 것은 위의 소스처럼 해당 함수 앞에 "virtual" 키워드를 붙임으로써 완성한다.

함수를 가상함수로 만들게 되면 이를 "오버라이딩 하는" 함수들 또한 virtual 키워드를 붙이지 않더라도 자동으로 가상 함수화 된다.

• 순수 가상함수, 추상 클래스

클래스 중에는 객체 생성을 목적으로 하지 않는 클래스가 존재한다. 상속을 위한 Base 클래스로서 존재하는 클래스들이 존재하는데, 이를 객체로 생성하게 되는 것은 개발자의 실수이다.

이러한 실수를 방지하기 위해 가상함수를 순수 가상함수로 선언하여 객체의 생성을 방지한다.

순수 가상함수란? 함수의 몸체가 정의되지 않은 함수를 말한다. 이를 포함한 클래스는 불완전한 클래스이기 때문에 객체를 생성하게 되면 컴파일 에러가 발생한다. 이러한 순수 가상함수가 멤버 함수로 포함된 불완전한 클래스를 추상 클래스라고 한다.

• 가상 소멸자

소멸자 또한 가상함수 선언이 된다. Base 클래스를 Derived 클래스가 상속하였을 때, Derived 클래스의 생성자를 호출하고 바디를 실행하기 이전에 Base 클래스 생성자를 호출한다. 이 두 생성자는 멤버 변수의 동적 할당을 수행한다고 가정한다! 이 때, 객체 포인터를 이용하여 객체를 할당하였다면 소멸자 또한 객체 포인터의 자료형을 기준으로 판단하여 경우에 따라서는 Derived 클래스의 소멸자가 실행되지 않을 수 있다.

이를 방지하기 위해서 소멸자에 virtual 키워드를 붙임으로써 해결한다.

• 다형성(polymorphism)

문장은 같은데 결과는 다른 것을 다형성이라고 한다. ( 동질이상, 열혈 C++ 참고 )
오버라이딩, 순수 가상함수 개념이 다형성에 해당한다. 이는 참조자(레퍼런스) 에서도 똑같이 적용된다.

• 멤버함수의 진실

멤버 변수는 객체 내에 존재한다. 그러나 사실, 멤버 함수는 객체 안에 존재하지 않는다. 멤버 함수는 사실, 메모리 한 공간에 위치하고, 해당 클래스로 선언되어 생성된 객체들이 이 한 공간에 위치한 멤버 함수들을 공유하는 형태로 존재한다.

• V-Table

위와 같은 두 클래스는 V Table이라는 가상 함수 테이블을 구성하게 된다. 객체 생성이 되지 않더라도 컴파일러에 의해 가상함수 테이블을 만든다.

위의 예제에 해당하는 가상 함수 테이블은 2개가 다음과 같은 형태로 구성이 된다.

유심히 살펴봐야 할 부분은 Derived 클래스의 테이블인데, 이 테이블에서는 상속을 받은 입장인대도 불구하고, Base::f1의 정보가 존재하지 않는다. 이는 오버라이딩 된 가상 함수의 정보는 존재하지 않고, 유도 클래스의 오버라이딩 한 가상 함수만이 존재한다.