알고리즘 / 해시(Hash)

알고리즘의 해시

해시에는 해시(Hash), 해시 함수(Hash Function), 해싱(Hashing),

해시 테이블(Hash Table) 이렇게 4가지로 나뉘어 진다.

 

각 요소들에 대해 알아보자.

 

해시(Hash)

해시는 검색과 저장을 빠르게 하는 자료구조이다.

데이터를 저장할 때는 Key-Value 형태로 데이터가 저장되고,Key값이 배열의 인덱스로 저장되기 때문에 검색과 저장이 빠르게 일어난다.

 

해시 함수(Hash Function)와 해싱(Hashing)

해시 함수는 Key값을 고정된 길이의 Hash로 변환하는 기능을 한다.

해시 함수에서 Key값을 hash로 변환하는 과정을 해싱(hashing)이라 한다.

해싱 과정을 통해 해시 값(hash value)또는 해시 코드(hash code)로 변경하며, 이 해시 값이 저장 위치가 된다.

 

다른 Key가 같은 hash가 되는 경우 해시 충돌(Hash Collision)이라 하는데,

함수를 작성할 때 해시 충돌을 일으키는 확룔을 낮게 작성하는 것이 중요하다.

 

 

해시 테이블(Hash Table)

해시 테이블은 연관 배열구조를 이용하며 데이터를 Key와 Value로 저장하는 자료구조이다.

 

해시 테이블은 해시 함수를 사용해 색인(index)을 버킷(bucket)이나 슬릇(slot)의 배열로 계산한다.

 

연관 배열구조?
연관 배열은 자료구조의 하나로, 키 하나와 값 하나가 연관되어 있으며 키를 통해 연관되는 값을 얻을 수 있다.

연관 배열은 일반적으로 다음의 명령을 지원한다.

• 키와 값이 주어졌을 때, 연관 배열에 그 두 값을 저장하는 명령
• 키가 주어졌을 때, 연관되는 값을 얻는 명령
• 키와 새로운 값이 주어졌을 때, 원래 키에 연관된 값을 새로운 값으로 교체하는 명령
• 키가 주어졌을 때, 그 키에 연관된 값을 제거하는 명령

 

 

 

 

장단점

장점

1️⃣ 중복을 제거할 수 있다.
2️⃣ 데이터 캐싱, 보안에 주로 사용된다.
3️⃣ 배열의 인덱스로 접근하기에 삽입, 삭제 등 연산이 빠르다.

 

단점

1️⃣ 공간 복잡도가 커진다.
2️⃣ 충돌이 발생할 수 있다. (충돌이 발생한 경우 시간복잡도는 O(n)에 가까워진다.)
3️⃣ 순서가 있는 배열에는 어울리지 않음

 

충돌(Collision)

충돌(Collision)은 서로 다른 문자열이 해시 함수를 통하여 해싱한 해시값이 중복인 경우이다.

충돌이 많아질 수록 탐색의 시간 복잡도가 O(1)에서 점점 O(n)에 가까워진다.

 

충돌을 해결해주는 방법은 크게 2가지 있다.

 

Separating Chaining 분리 연결법과 Open Addressing  개방 주소법은 따로 자료구조 CS로 다뤄보자.

 

 

 

 

 

참고

배현호님의 블로그 글 (출처 : https://velog.io/@hanif/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%95%B4%EC%8B%9C)