해시(Hash)란?
Hash는 데이터를 다루는 과정에서 빠르게 데이터에 접근하기 위해 사용되는 기술이다. Hash는 어떤 값을 고정된 크기의 값(해시 값)으로 변환된 결과를 말한다. 이 과정에서 사용되는 함수를 Hash Function라고 한다.
해시 함수(Hash Function)
해시 함수(Hash function)는 입력받은 데이터를 고정된 크기의 값으로 변환해 주는 함수를 말한다. 자바에서는 Object 클래스에 hashCode() 메서드를 통해 해시 코드를 제공하며 객체의 메모리 주소를 기반으로 한 정수 값을 반환한다.
해시 충돌(Hash Collision)
해시 함수를 보면 고정된 크기의 값으로 변환해 준다는 내용이 있다. 만약 입력값이 크든 작든 고정된 값을 변환해 주기 때문에 같은 해시 값을 가지는 경우가 발생한다. 이것을 해시 충돌이라고 한다. 이를 해결하는 방법으로는 대표적으로 체이닝(Chaining), 오픈 어드레싱(Open Addressing) 방법이 있다. 이론적으로는 무한한 수의 입력값을 한정된 수의 해시값으로 변환해야 하기 때문에 해시 충돌이 발생하지 않는 경우는 거의 불가능하다. 해시 충돌에 관해 여러 사람들이 비둘기집 원리를 많이 예를 들었다.
* 비둘기집 원리는 n+1개의 물건을 n개의 상자에 넣을 때 적어도 어느 한 상자에는 두 개 이상의 물건이 들어 있다는 원리를 말한다.
출처 : 위키백과
체이닝(Chaining)
충돌이 발생했을 때, 같은 해시 버킷(bucket)에 여러 개의 요소를 연결 리스트(linked list) 또는 트리(tree)와 같은 자료 구조를 사용하여 저장하는 방법. Java에서는 HashMap에서 체이닝 Java 8부터 데이터의 개수가 많아지면 링크드 리스트 대신 트리를 사용한다.
- 장점
- 연결 리스트의 노드를 추가하거나 제거하면 되기 때문에 삭제와 추가가 간단하다.
- 해시 테이블의 크기에 비해 많은 데이터를 저장할 수 있다.
- 단점
- 연결 리스트의 추가적인 포인터 공간이 필요하기 때문에 메모리 사용량이 늘어날 수 있다.
오픈 어드레싱(Open Addressing)
체이닝 방식과 달리 별도의 자료 구조를 사용하지 않고 해시 테이블 내의 빈 슬롯을 찾아 충돌이 발생한 요소를 저장하는 방법이다. 모든 요소가 해시 테이블 내부에 저장되며 대표적인 방식으로 선형 탐사법, 제곱 탐사법, 이중 해싱 등이 있다.
- 선형 조사(Linear Probing): 충돌 위치로부터 선형적으로 다음 빈 슬롯을 찾아 저장한다. 단순하지만, 클러스터링(Clustering) 문제가 발생할 수 있다.
- 제곱 조사(Quadratic Probing): 제곱수를 이용해서 다음 위치를 찾아 저장한다. 선형 조사보다 클러스터링 문제를 줄일 수 있다.
- 이중 해싱(Double Hashing): 또 다른 해시 함수를 사용하여 충돌이 발생했을 때의 다음 위치를 결정하며 클러스터링 문제를 더욱 효과적으로 줄일 수 있다.
* 클러스터링은 해시 테이블 내에서 데이터가 연속적인 블록 형태로 집중되는 현상
- 장점
- 별도의 공간을 사용하지 않아 메모리를 효율적으로 사용가능
- 연속된 공간에 데이터를 저장하기 때문에 체이닝에 비하여 캐시 효율이 높다.
- 단점
- 클러스터링 문제가 발생할 수 있으며 이 경우 탐색, 삽입, 삭제 성능에 영향 부정적인 영향을 줄 수 있다.
📕 참고자료
'Study > Java & Spring' 카테고리의 다른 글
| 체크 예외 & 언체크(런타임 예외) (1) | 2024.03.26 |
|---|---|
| 필터(Filter), 인터셉터(Interceptor) (0) | 2024.02.20 |
