해쉬 테이블 ( HashTable )

해쉬 테이블 ( Hashtable )

해쉬 테이블은 Key , Value 를 저장하는 데이터 구조이다.

해쉬 테이블은 *해쉬함수를 사용하여 키를 해쉬값으로 매핑하고, 이 해쉬값을 인덱스 또는 주소삼아 데이터를 key와 함께 저장하는 자료구조 이다. 단순하게 key - value 로 이루어진 자료구조라고 생각하면 된다

 

*해쉬 함수 ( Hash Function ) 

해쉬와 해쉬테이블을 알기전에 Hash Function(해쉬함수) 라는 것을 알아야 한다. 

데이터를 최대한 빠르게 찾기 위해서는 저장하는 위치도 잘 생각해서 저장해야 한다 

해쉬 함수의 정의는 key를 고정된 길이 hash로 변경해주는 역할을 한다. 이 과정을 hasing 이라고 한다

key를 해쉬함수라는 함수에 input으로 넣어서 Output으로 나오는 것이 Hash(해시) 라고 생각하면 되고, 이 Hash가 저장위치가 된다고 생각하면 된다. 결국 Hash Function은 key로 해쉬를 만들어내는 함수이다.

[ 해시알고리즘 ] 해시함수의 특성 및 개념 이해 - 블록체인을 중심으로

---

해시 테이블 구성

• Key
  • 고유한 값, Hash Function의 Input
  • key 값을 그대로 저장소의 인덱스로 사용할 경우 key의 길이만큼의 정보를 저장하고 공간도 따로 마련해야 하기 때문에 고정된 길이의 해쉬로 변경한다.
• Hash Function
  • key를 고정된 길이의 hash로 변경해주는 역할을 한다
  • 서로 다른 key가 hasing 후 같은 hash값이 나오는 경우가 있다. 이를 해시충돌이라고 부른다.
• value
  • 저장소 ( 버킷, 엔트리 ) 에 최종적으로 저장되는 값으로, hash와 매칭되어 저장되어 진다.
• Hash Table
  • 해쉬 함수를 사용하여 키를 해쉬값으로 매핑하고, 이 해쉬값을 주소또는 색인 삼아 데이터( value ) 를 key와 함께 저장하는 자료구조이다.
  • 데이터가 저장되는 곳을 버킷, 엔트리 라고 한다.

A : 인덱스	B : 값
C : 1	D : 123
2	234
3	345
4	456

A : 인덱스 , 키

B : 해쉬값, 벨류

C : 버켓

D : 엔트리

---

해쉬 테이블의 장,단점

장점 : 해쉬테이블은 key - value가 1:1 로 매핑되어 있기 때문에 삽입, 삭제, 검색의 과정에서 모두 평균적으로 시간복잡도를 가지고 있다.

 

단점 :

1. 해시 충돌이 발생 한다.

2. 순서 / 관계가 있는 배열에는 어울리지 않는다.

3. 공간 효율성이 떨어진다. 데이터가 저장되기 전에 저장공간을 미리 만들어놔야한다.

( 공간을 만들었지만 공간에 채워지지 않는 경우가 발생한다. )

4. hash function의 의존도가 높다 해쉬함수가 복잡하다면 hash를 만들어 내는데 오래 걸린다.

---

충돌 대처

Chaining ( 체이닝 )

- 체이닝은 저장소 ( 버킷 ) 에서 충돌이 일어나면 기존 값과 새로운 값을 연결리스트로 연결하는 방법이다.

 

장점 : 미리 충돌을 대비해서 공간을 많이 잡아놓을 필요가 없다. 충동리 나면 그때 공간을 만들어서 연결만 해주면 된다.

단점 : 같은 hash에 자료들이 많이 연겨되면 검색시 효율이 낮아진다.

 

Linear Probing ( 리니어 프로빙 ) 

- 선형탐색법은 이미 만들어 놓은 버켓을 먼저 소모한다. 

 

Resizing ( 리사이징 ) 

- 테이블의 크기를 늘려준 다음에 기존에 데이터들을 다시 해쉬함수에 보내고 다시 테이블을 재정렬을 한다.