30. Hash Separate Chaining(해시+링크드리스트) 구현 알고리즘

1. 개요

 Hash 기법은 쉬움.

 Hash는 검색 속도를 O(1) Constant Time에 해결하게 해주는 기법.

 Hash란 키 값에 따라 데이터를 Direct로 참조하는 기법. 

 기본은 Table에서 시작.

 하지만 Table에서 중복이 조금 덜 되게 만들어주는 것이 Hash 기법. (배열도 Hash의 일종)

 Hash는 전체적으로 4가지 방법이 존재. (선형 탐색, 2차 탐색, 이중 해싱, 체이닝 해쉬)

 하지만 4가지 중 중복 문제로 인해 사용되는 기법은 이중 해싱과 체이닝 해싱.

 Hash Table에서 키(key) 분산이 잘 되도록 테이블 크기는 소수(Prime Number)로 설정.

  

 Hash의 5가지 기본 연산

 (1) CreateHashTable(): Hash Table을 생성.

 (2) HashSearch(): Hash Table을 검색.

 (3) HashInsert(): Hash Table에 키 값에 따라 데이터 삽입.

 (4) HashDelete(): Hash Table에 키 값에 따라 데이터 삭제.

 (5) DeleteHashTable(): Hash Table을 삭제.

 Hash의 4가지 구성 요소

 (1) Hash Table: 데이터가 처리되는 장소.

 (2) Hash Function: 키 값 찾는 함수.

 (3) Collision(충돌): Hash 함수의 값이 같을 경우 위치 중복을 나타냄.

 (4) Collision(충돌) 해결 기법

 Load Factor(적재인수)라는 값을 통해 전체 Hash Table의 효율성을 판단할 수 있고, 재조정도 가능함.

 Load Factor = (예상되는 데이터 개수) / (Table 크기)

 Load Factor는 일반적으로 10~20 사이. 이 의미는 10~20번까지의 검색만 필요. 즉, O(1) 검색 시간 소요.

*Hash 기법은 데이터의 추가나 삭제보다 검색이 많을 경우에 사용.

2. 문제

 Hash Separate Chaining를 기본 기능을 구현하고 충돌 해결 기법 역시 구현하라.

3. 코드

3-1) 구조체 및 함수 선언

3-2) 메인

3-3) CreateHashTable()

3-4) GetKey()

3-5) HashSearch()

3-6) HashInsert()

3-7) HashDelete()

3-8) DeleteHashTable()

3-9) PrintHashTable()

3-10) ReHash()

3-11) 출력

      *테스트 출력 화면을 보이기 위해 ReHash()를 메인 함수에서 테스트 한 출력 과정

        실제로 ReHash() 함수는 HashInsert()에 포함된다.

4. 정리

 Hash Separate Chaining을 구현하면서 알아두어야 할 점.

 Load Factor에 따라서 어떻게 데이터가 재분배 되는지 알아야 한다.

 검색, 삽입, 삭제 모두 평균적으로 O(1)에 수렴한다.

 해시 테이블이 적합하지 않은 경우들

 (1) 정렬된 데이터가 필요할 때

 (2) 멀티미디어 데이터를 저장할 때

 (3) 키의 길이가 길고 가변적이어서 키에 대한 사전 검색이 필요할 때

 (4) 조건에 따라 데이터가 동적으로 변해야 할 때

 (5) 데이터의 키가 유일하지 않을 때

 기억해야 할 것

 * 더블 포인터는 이차원 배열로도 사용이 가능하고 또한 포인터 배열로도 사용 가능하니까 혼돈하지 말자!