해시(Hash)

Ouroboros·2023년 10월 31일

hash 자료구조 해시

자료구조

목록 보기

7/13

✨용어 간단 요약

해시테이블은 hash를 주소로 삼아 데이터를 저장하는 자료구조이다.
해시 함수(Hash Function)은 Key를 Hash값으로 만들어주는 함수이다.
해시(Hash) : 해시 함수에 의해 얻어지는 값
해시(Hash)는 저장위치(주소), 색인, 인덱스 등이라고 할 수 있다.

🕶️해시테이블 구성

1) 해시테이블

해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 주소또는 색인 삼아 데이터(value)를 key와 함께 저장하는 자료구조이다.
데이터가 저장되는 곳을 버킷, 슬롯이라고 한다.

// 해시 함수 예시
Integer hashFunction(String key) {
	
    return (int)(key.charAt(0)) % 100;
}
//키 값을 정수형으로 만든 후 100으로 나눈 나머지 값을 반환하는 함수
//이 나머지 값이 인덱스가 된다.

2) key

해시함수에 Input으로 넣는 고유한 값이다.
key값을 그대로 저장소의 색인으로 사용할 경우 key의 길이만큼의 정보를 저장해야한 공간도 따로 마련해야 한다. 고정된 길이의 해시로 변경한다.
(Input 값의 길이는 달라도 Output 값(해시)의 길이는 고정이다)

3) hash function

key를 고정된 길이의 hash로 변경해주는 역할을 한다.

<대표적인 해시 함수(4가지)>
1. Division Method:
나눗셈을 이용하는 방법으로 입력값을 테이블의 크기로 나누어 계산한다. ( 주소 = 입력값 % 테이블의 크기)
테이블의 크기를 소수로 정하고 2의 제곱수와 먼 값을 사용해야 효과가 좋다.
2. Digit Folding:
각 Key의 문자열을 ASCII 코드로 바꾸고
값을 합한 데이터를 테이블 내의 주소로 사용하는 방법이다.
3. Multiplication Method:
숫자로 된 Key값 K / 0과 1사이의 실수 A / 보통 2의 제곱수인 m을 사용하여 계산을 한다.
h(k)=(kAmod1) × m
4. Univeral Hashing:
다수의 해시함수를 만들어 집합 H에 넣어두고,
무작위로 해시함수를 선택해 해시값을 만드는 기법이다.

4) value

저장소(버킷,슬롯)에 최종적으로 저장되는 값
hash와 매칭되어 저장되어진다.

❣️해시충돌

서로 다른 key를 해시처리 할 때 같은 hash값이 나오는 경우. 해시 충돌 발생확률이 적을 수록 좋다.

💡해시 장,단점

장점

Key와 Value가 1:1로 매핑되어 있기 때문에 삽입, 삭제, 검색의 과정에서 모두 평균적으로O(1)의 시간복잡도를 가지고 있다.

단점

해시 충돌이 발생할 수 있다.
순서/관계가 필요한 배열에는 어울리지 않는다.
공간 효율성이 떨어진다. 데이터가 저장되기 전에 저장공간을 미리 만들어놔야한다. 또한 공간을 만들었지만 공간에 채워지지 않는 경우가 발생한다.
해시함수의 의존도가 높다. 해시함수가 복잡하다면 hash를 만들어 내는데 오래 걸린다.

💥해시 충돌

서로 다른 key가 같은 hash값이 나오는 경우이다.

해시 충돌이 생기는 이유는
1. 함수 알고리즘이 좋지 못할 때
2. 저장하는 데이터의 양이 테이블의 크기보다 클 때

충돌 해결법

[ 분리 연결법(Separate Chaining) ]

분리연결법은 동일한 버킷의 데이터들에 추가 메모리를 사용해서 다음 데이터의 주소값을 저장하는 것이다.
Java8의 Hash테이블은 Self-Balancing Binary Search Tree 자료구조를 사용해 Chaining 방식을 구현하였다.
이러한 연결 방식은 해시 테이블의 확장이 필요없이 간단하게 구현이 가능하며, 손쉽게 삭제할 수 있다는 장점이 있다. 하지만 데이터의 수가 많아지면 동일한 버킷에 데이터가 많아지며 그에 따라 캐시의 효율성이 감소한다는 단점이 있다.

[ 개방 주소법(Open Addressing) ]

개방 주소법은 추가적인 메모리를 사용하는 분리 연결법과는 다르게 비어있는 공간을 활용한다.
개방 주소법에서 삭제를 할 때 삭제 공간은 Dummy Space로 활용된다. 이때 해시테이블을 재정리하는 작업이 필요하다.

<개방 주소법의 3가지 방법>
Linear Probing: 현재의 버킷 index로부터 고정폭 만큼씩 이동하여 차례대로 검색해 비어 있는 버킷에 데이터를 저장한다.
Quadratic Probing: 해시의 저장순서 폭을 제곱으로 저장하는 방식이다. 예를 들어 처음 충돌이 발생한 경우에는 1만큼 이동하고 그 다음 계속 충돌이 발생하면 2^2(4), 3^2(8) 칸씩 옮기는 방식이다.
Double Hashing Probing: 해시된 값을 한번 더 해싱하여 해시의 규칙성을 없애버리는 방식이다. 해시된 값을 한번 더 해싱하여 새로운 주소를 할당하기 때문에 다른 방법들보다 많은 연산을 하게 된다.