전화번호부를 만들어볼까? - Hash Table

그동안 다뤄온 자료구조형태는 데이터를 찾기위해  끝단의 데이터를 빼주면서 찾거나(스택,큐), 해당데이터를 찾을때까지 데이터를 비교하면서 찾아다니거나(연결 리스트), 위에서 아래로 혹은 돌면서 자식 노드들을 살펴보거나(트리,B-트리) 의 방식을 이용했는데 저장에는 좋은방식들 일수도있겠지만, 데이터를 찾는데 시간이 걸린다는 단점이 있었다.

하지만 우리 핸드폰 내의 전화번호부처럼 글자순으로 데이터가 잘 정리되있다면 어떨까? 데이터를 훨씬 빨리 찾을 수 있지 않을까?

전화번호부

1.  Hash Table 이란?
해쉬테이블은 데이터를 해쉬함수를 이용해 배열의 인덱스로 변환하여, 환산된 인덱스의 배열방에 데이터들을 담는 것을 의미한다.
배열의 인덱스로 데이터를 가져오는것은 컴퓨터가 가장 쉽게 처리 할 수 있는 일이기 때문에, 데이터를 찾는데는 가장 효율적이라고 볼 수있다.

해시 테이블 구조

2. 데이터를 어떻게 숫자로 바꾸는데..?
데이터를 인덱스로 바꾸는것은 매우 까다로운 일이다. 경우의 수가 매우많기 때문이다. 좋은 해쉬함수 알고리즘을 만드는건 해쉬테이블의 기능에 있어서 가장 중요하다. 경우에 따라 한 인덱스의 배열방을 많은 데이터가 차지할 수도 있기 때문이다. 찾아본 결과 데이터의 아스키코드값을 구해 배열의 크기로 나눈값을 인덱스로 만드는 게 있었다. 그 외에도 데이터의 모양에 따라 적절한 해쉬함수 알고리즘을 선택해야 한다.

3. 한 방을 많은 데이터가 차지하면 어떡해..? 나머지 방은..?
배열의 한 방에 많은 데이터들이 있는 것을 '데이터의 충돌' 이라고 칭한다. 이를 방지하기 위해서 특정 인덱스의 방에 또다른 배열,객체를 만들어 들어오는 순서대로 방에 저장하거나, Linked list를 생성해 저장하거나, 빈방에 들어온 데이터들을 할당해 주는 방법 등... 충돌을 막기위한 많은 방법들이 있다.

충돌 해결법 

4. 의사 코드를 이용해 Hash Table의 기능 구현해보기

 1) Hash Table의 생성

  // 1. 입력받을 데이터들이 어떤 형식일 것 인지 확인한다.

  // 2. 데이터를 배열의 인덱스로 환산할 수 있는 규칙을 찾고, 해쉬 함수를 작성한다.

  // 3. 데이터를 담을 Hash Table을 배열로 생성한다. 

  // 4. 단, 충돌을 방지하기 위해 같은 인덱스 내에 여러개의 데이터가 들어온다면 내부에 이중배열, 객체를 생성하거나 Linked list를

        만들 수 있도록 조건을 설정해준다. 

 2) 데이터의 추가

  // 1. 데이터를 해쉬 함수에 넣어준다. (이후의 과정은 해쉬 함수와 테이블내의 규칙에 따라 정렬되므로 후술 X )

 3) 데이터의 삭제

  // 1. 삭제하고자 하는 데이터의 인덱스를 해시 함수를 통해 알아낸다.

  // 2. Hash Table 내에 데이터가 하나라면 그 인덱스를 empty 상태로 만들어주고, 데이터가 여러개라 

  //    이중배열 혹은 객체, Linked list가 있다면, 내부에 들어가 데이터 삭제하고자 하는 데이터와 값이 일치하면 삭제할 수 있도록한다.  

 
 4) 데이터의 조회

  // 1. 찾고자하는 데이터의 인덱스를 해시 함수를 통해 알아낸다.

  // 2. Hash Table 내에 데이터가 하나라면 해당 인덱스 내의 데이터를 바로 출력해주고, 데이터가 여러개라 

  //    이중배열 혹은 객체, Linked list가 있다면, 내부에 들어가 데이터 삭제하고자 하는 데이터와 값이 일치하면 삭제할 수 있도록한다.