Hash Table의 의미와 중요성

우리가 코딩하면서, 가장 많이 사용하는 자료구조 개념은 무엇일까 생각해보았다.
또, 그 중 중요하면서 유용한 것이 무엇일까 생각해보았다.

배열(array), 해시 개념을 사용한 맵(map), 집합(set) 같은 자료구조가 아닐까 생각이 들었고,
(트리를 이용한 map, set도 있기 때문에 '해시 개념을 사용한'이라고 하였다)
검색과 생각 끝에 공통적인 개념이 사용됨을 알았다.

해시 테이블의 개념을 살펴보면, key - value를 이용하여 원하는 자료구조를
순차 탐색할 필요 없이 바로 찾아가는 것에 있다. 그리고 이를 흔히 말하는 상수 시간 O(1)로 볼 수 있다.

먼저, 배열을 살펴보자.
배열은 정수(0, 1, 2, ... )를 이용해서 해당 위치에 있는 자료를 바로 불러올 수 있다.
이것은 key - value로 나타내면, int형을 갖는 key와 각기 다른 타입을 갖는 value로 볼 수 있다.
즉, 배열은 key가 정수인 해시 테이블이라고 볼 수 있다.

그러면 배열을 선언하면, 내부적으로는 어떤 일이 일어날 것인지 추측해볼 수 있다.
일단, 배열의 원하는 원소에 바로 접근하려면, 기본 주소가 필요하다.
즉, 배열의 기본주소 Base Address를 저장할 변수가 필요하다.
다음으로는 value에 해당하는 자료형의 크기를 저장할 변수가 필요할 것이다.
왜냐하면, int 32형의 경우 4byte를, int 64형의 경우 8byte가 배열 한 칸을 움직이는 최솟값이 되기 때문이다.
(배열의 해당 원소의 주소 = base address + offset, offset = sizeof(자료형) * index)

그럼 좀 더 확장하여, 해시 테이블에서 사용되는 모든 타입의 key에 대해선 어떻게 계산할까?
key가 string이라고 가정하면, 문자열 abc와 문자열 bca는 위의 인덱스 개념처럼 서로 다른 위치를 가르치게 해야 한다.

그러면, 이 문자열들을 각기 다른 key를 갖게 해야 하는데,
컴퓨터 내부적으로는 숫자 이진수 0과 1로 이루어져 있기 때문에 그대로 나타낼 수 없다.

이를 위해서 어떠한 연산을 통해 숫자로 바꾸면 어떨까?
여기에서 hash function을 생각해볼 수 있다. (적절한 연산 메커니즘, 횟수에 따라서 킷값을 정한다.)

간단하게 생각해보면, 문자열 abc의 문자 하나를 아스키코드값에 따라서 숫자를 부여하고,
이를 더하거나 곱해주는 연산을 통해 배열처럼 정수를 갖는 key를 갖게 할 수 있다.

마찬가지로, 좀 더 복잡한 Object 개념도 내부적으로 어떤 멤버변수들을 갖는가에 따라서 위와 같이 생각해볼 수 있을 것 같다. (멤버 변수도 같고, 메소드도 같은 클래스가 존재할 수 있는데, 이를 구분하기 위해서는 만들어진 class 별로 고유한 해시 코드를 갖게 하지 않을까 생각해본다.)

해시 테이블은 수학적 개념(모듈러 연산, 해시 함수, 일대일 함수[충돌하지 않는 경우]), 컴퓨터 구조(이진수)를
고려한 자료구조이며, 이를 이용해 많은 작업을 빨리 할 수 있기에 많은 분야에서 사용된다.