[DS] 자료구조 HashTable - DAT(Direct Adressing Table)

해시테이블

해시 테이블이란 해시함수를 사용하여 변환한 값을 색인(index)로 삼아 키(Key)와 데이터(Value)를 저장하는 자료구조를 말한다. 기본 연산으로는 탐색(Search), 삽입(Insert), 삭제(Delete)가 있다.

 

 

Direct Adress Table

먼저 가장 간단한 형태의 해시테이블로 이름 뜻대로 키 값을 주소로 사용하는 테이블을 말한다. 이는 키 값이 100이라고 했을떄 배열의 인덱스 100에 원하는 데이터를 저장하는 것이다.

 

// int형 배열 Bucket에 0~255 인덱스 중 char형 배열의 아스키 코드 의 값 자체를 Index로 활용한다

// 출력결과는 A = 65, B = 66, C = 67. D = 68, E = 69, A = 65이니

// 65~69번쨰 인덱스에 0에서 ++ 해주니 1씩 들어가게되고, A가 하나 더 있으니 65만 2가 된다.

 

 

Hash Table - DAT(Direct Addressing Table)

 

// 즉 이 코드는 A는 아스키코드 65이니 Bucket[65] = 1과 같다

 

 

Hash Table

해시함수를 사용하여 특정 해시값을 알아내고 그 해시값을 인덱스로 변환하여 키 값과 데이터를 저장하는 자료구조이다.

이는 보통 알고 있는 해시 테이블을 애기하며 개념자체가 어려운 것은 아니지만 문제가 되는 것은 충돌이다. 충돌에 대해서

이해하기 위해선 먼저 적재율 에 대해서 이해해야한다.

 

적재율이란 해시 테이블의 크기 대비, 키의 개수를 말한다. 즉, 키의 개수를 K, 해시 테이블의 크기를 N이라고 했을 떄

적재율은 K/N이다, Direct Address Table은 키 값을 인덱스로 사용하는 구조이기 떄문에 적재율이 1 이하이며

적재율이 1초과인 해시 테이블의 경우는 반드시 충돌이 발생하게 된다.

 

만약, 충돌이 발생하지 않다고 할 경우 해시 테이블의 탐색, 삽입, 삭제 연산은 모두 O(1) 에 수행되지만

충돌이 발생할 경우 탐색과 삭제 연산이 최악에 O(K) 만큼 걸리게 된다. 이는 같은 인덱스에 모든 키 값과 데이터가

저장된 경우로 충돌이 전부 발생했음을 말한다. 따라서, 충돌을 최대한으로 줄여서 연산속도를 빠르게 하는 것이

해시 테이블에 핵심인데 이에 중요하게 작용하는 것이 바로 해시함수를 구현하는 해시 알고리즘이다.

해시 알고리즘이 견고하지 못하게 되면 해시함수로 도출된 값들이 같은 경우가 빈번하게 발생하게 되므로

잦은 충돌로 이어지게 되는 것이다.

 

 

활용예시

 

배열에 존재하는 알파벳 갯수 찾기

// A,B,C,D,E,A번쨰 인덱스에 1씩 증가시켜주고

// A = 65부터 Z = 90까지 for문을 돌면서 몇개인지 샐수있다.

// HashTable을 사용하지 않고 for문만 돌려서도 가능하다.

2가지 방법에 장단점

HashTable을 사용했을때 : HashTable을 사용할 경우 Bucket이란 넉넉한 배열(4x256)byte을 준비해야해서

너무 많은 메모리 공간을 차지하게된다. 대신 코드는 쉬워짐.

for문을 사용했을떄 : 코드가 조금 복잡해진다. 대신 정해진 공간만 사용함. Bucket을 만들필요X

 

출력 결과

 

 

배열에 존재하는 알파벳 종류 찾기

 

출력 결과

 

 

 

배열에 존재하는 알파벳 종류와 각 갯수 출력

 

출력결과

 

 

배열에 글자를 순서대로 정렬하여 출력

버블정렬, 선택정렬보다 훨씬 간단하다.

// 0대신 '\0'도 가능하다

// 아스키코드는 어차피 정렬되어있으니 (A = 65, B = 66, C = 67....) 자동으로 정렬된다.

 

출력결과

 

 

 

패턴 찾기

// BTABCQABC중 ABC가 몇개있는지 찾는다.

// BTA,TAB,ABC,BCQ,CQA,QAB,ABC를 비교해야하니 7번 돌아야한다. (0번인덱스~6번인덱스)

// 하나라도 틀린다면 Return False로 바로 함수를 빠져나온다

 

출력결과