Hash Table Data Structure(해시 테이블 자료구조)

1. 해시 테이블(Hash Table) 이란?

데이터의 관리 및 유지하는데 있어서 최대한 빠르게 원하는 데이터에 접근하기 위한 자료구조이다.
검색하고자 하는 Key값을 입력받아 해쉬함수를 통해 HashCode를 생성하고, 그 HashCode를 배열의 index로 환산하여 해당 index에 값(value)을 저장한다.

즉, 인덱스와 값은 언제나 연관성을 가지고 있다.

 

장점:

• 빠른 서치

• 유연한 키값

단점:

• 비정렬된 구조
• 한방향 서칭
• 메모리 비효율적 구조

 

만약 colision 발생시 대처방법
1) Linear Probing(선형탐사)

해시 함수로부터 얻어낸 주소에 이미 다른 데이터가 입력되어 있으면 현재 주소를 기준으로 고정 폭으로 다음 주소로 이동해 비어있는 주소에 입력한다.
서치방법 : 원하는 데이터를 서칭할 때 해시 함수로 얻은 주소에 다른 값이 들어가 있으면 동일한 방식으로 현재 주소를 기준으로 고정 폭으로 다음 주소로 이동해 데이터를 찾아낸다.
2) Quadratic Probing(제곱탐사)

선형탐사에 비해 이동 폭을 제곱수로 늘려 비어있는 주소를 찾아 입력한다.
3) Double Hashing

2개의 해시 함수를 준비해서 하나는 최초의 주소를 얻을 때 또 다른 하나는 충돌이 일어났을 때 탐사 이동폭을 얻기 위해 사용
4) Rehashing

해시 테이블의 크기를 늘리고, 늘어난 해시테이블의 크기에 맞추어 테이블 내의 모든 데이터를 다시 해싱하는 것
5) Chaining

해시함수를 통한 얻은 주소가 같을 경우 연결리스트를 통해 데이터를 이어가는 정리방식

 

구성요소
버킷(Bucket): key에 해당하는 value들의 묶음(해당 슬롯의 묶음)
슬롯(Slot): key에 해당하는 value의 값(연결리스트로 연결된 값 하나하나를 의미)
레코드(Record): 해싱된 주소(물리적인 주소)
해시 값(Hash Value): hash code + 인덱싱 결과 값
홈 주소(Home Address): 해당 키값을 해시 함수에 넣어 반환된 주소
해시 충돌(Collision): 서로 다른 키값이 해시 함수에서 동일한 값을 받아 충돌함
오버플로우(Overflow): 더이상의 데이터를 저장할 공간이 없는 상태

 

2. 해시 테이블의 활용

• 전자서명
• 블록체인
• 인증
• 보안 알고리즘 등

 

3. 구현을 위한 의사코드(Pseudo Code)

1. 데이터를 담을 수 있는 객체 생성
2. 키값을 아스키코드로 변환한다.
3. 해시함수를 통해 원하는 해시코드를 가져온다.
4. 적절한 연산을 통해 해시코드를 인덱스로 변환한다.
5. 해당 인덱스에 데이터를 추가한다.
    5-1. 만약 중복되는 인덱스가 나오면 다음과 같은 방법으로 해결한다.
    	5-1-1. 고정 폭으로 다음 인덱스값으로 이동해 비어 있는지 확인 후 비어있으면 추가한다.
        5-1-2. 연결리스트를 통해 데이터를 체인화 시켜 동일한 인덱스에 추가한다.
        5-1-3. 리해싱을 통해 테이블의 크기를 늘리고 그 크기에 맞게 모든 데이터를 다시 해싱한다.

 

 

4. 참고자료(References)

https://www.youtube.com/watch?v=KyUTuwz_b7Q
https://wodonggun.github.io/wodonggun.github.io/algorithm/%ED%95%B4%EC%8B%9C-%EC%A0%95%EB%A6%AC.html
https://www.interviewcake.com/concept/java/hash-map