자료구조 - 해시테이블 (Java, HashMap)

1. 개념

해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 주소로 하여 데이터를 key와 함께 저장하는 자료구조

key를 활용하여 value값 조회 가능

매우 빠른 평균, 삽입, 삭제, 탐색연산이 제공되는 자료구조

 

구성

- key 

• hash function의 input
• 고유한 값
• 키 값 그대로 저장할 경우 다양한 키의 길이만큼 구성해야하므로 일정한 길이의 해시로 변경함

- hash function

• key를 고정된 길이의 해시로 변경해주는 함수로 해시 함수를 거치는 과정을 "hashing"이라고 함
• 서로 다른 key가 같은 hash 값을 같게 되는 경우를 해시 충돌이라고 하며, 이 충돌이 적을 수록 좋은 해시함수라고 할 수 있음

- value

• 저장소에 저장되는 값

- hash table

• 해시함수를 사용하여 해시값으로 매핑하여, 이 주소에 key와 value가 함께 저장되어 있는 자료구조
• 데이터가 저장되는 곳을 버킷 또는 슬롯이라고 함

 

장점

삽입, 삭제, 탐색 모두 O(1)의 시간복잡도를 가짐 (빠른 연산)

 

단점

해시 충돌 발생 가능성

순서관계가 있는 배열에는 부적합

공간 효율성 떨어짐

• 키의 전체 개수와 동일한 크기의 버킷을 가진 해시테이블(Direct-address table)은 키의 개수와 테이블의 크기가 같아 해시 충돌이 발생하지 않는다. 하지만, 키가 테이블의 크기에 비해 얼마되지 않는 경우 메모리 낭비가 된다.

해시함수의 의존도가 높음

 

 

Universal Hash Function

해시함수 집합 H에서 무작위로 해시함수를 선택해 해시값을 만드는 기법

해시함수 집합에서 무작위로 뽑은 해시함수가 주어졌을 때, 임의의 key 값을 임의의 hash 값에 매핑할 확률을 1/m 로 만드려는 것이 목적(m  : 해시테이블의 크기)

 

이러한 해시함수를 만드는 일은 굉장히 어려워서, 충돌 확률을 c/m보다 작게 만드는 해시함수를 설계하기도 하는데, 이를 c-universal h.f 이라고 부른다. 실제로는 c-universal h.f을 많이 사용함.

 

---

2. Open Addressing (개방 주소법)

해시테이블의 충돌을 피하기 위한 방법

비어 있는 Hash를 찾아 데이터를 저장하는 기법으로 이 방법의 해시테이블은 hash와 value가 1:1관계를 유지함

이 때 비어있는 hash를 찾아가는 방법에 따라 Open Addressing의 방식을 아래와 같이 나눌 수 있음.

선형 탐색 (Linear Probing)

충돌이 발생하면 한칸씩 밑으로 내려가며, 비어있는 테이블을 찾는 것.

연속적으로 key값이 테이블 슬롯에 모여있으면(cluster) 계속 cluster의 끝을 찾느라 삽입에 시간이 많이 소요됨. 

따라서 cluster를 최대한 작게 해야 함.

 

조회를 할 때도 특정 값을 찾기 위해 해시테이블을 확인하고, 찾고자 하는 key가 존재하지 않으면 밀려서 아래 어딘가에 찾고자 하는 값이 있을 수 있으므로 cluster 끝까지 타고 내려가서 특정 값이 있는지 찾음

 

 

제곱 탐색 (Quadratic Probing)

충돌이 일어난 해시의 제곱을 한 해시에 데이터 저장

여러 개의 서로 다른 키들이 동일한 해시값을 갖는 경우, 빈 slot을 찾는 과정이 동일하므로 계속해서 같은 slot을 찾게 됨. 이러한 secondary clustering에 취약

초기 해시값이 같다면, 동일한 폭으로 탐색하므로 효율성 떨어짐

 

이중 해싱 (Double Hashing)

다른 해시함수를 한번 더 적용해 나온 해시에 데이터 저장 (충돌 발생 시 적용할 해시함수 하나 더 준비하여 탐사 이동폭을 얻기 위해 활용)

이중 해싱을 하면 최초 해시값이 달라지므로 탐사 이동폭이 달라짐. 탐사 이동폭이 같더라도 최초 해시값이 달라져 primary, secondary clustering 완화

 

해시함수의 성능에 따라 해시테이블의 성능이 좌우됨

데이터 길이가 늘어나면 그에 해당하는 저장소 마련 필요

 

 

---

 

 

3. Chaining

해시테이블의 충돌을 피하기 위한 방법

충돌이 발생하면 기존 값과 새로운 값을 연결리스트를 이용해 연결

 

장점

한정된 저장소를 효율적으로 활용 (미리 충돌에 대비해 공간을 잡을 필요가 없음)

해시 함수를 선택하는 중요성이 상대적으로 적어짐

c-universal h.f 을 사용하면 충돌 key의 평균 개수(연결리스트의 길이)가 O(1)를 유지해서 연산이 빠름

 

단점

한 해시에 자료들이 많이 연결되면 검색 효율이 낮아짐

외부 저장공간을 활용함

 

 

---

4. Java에서의 구현 : HashMap

Seperate Chaining을 사용한다. 

 

단, 위에서 설명한 Chaining과 달리, Java8부터 Hashmap의 버킷 데이터가 일정 개수 이상일 때 연결리스트 대신 트리(Red-Black Tree)를 사용한다고 한다. (기존에는 연결리스트를 사용하였다.) 

이렇게 Tree를 사용함으로써 get() 메서드의 성능이 향상됐다.

 

하나의 해시 버킷에 8개 이상의 key-value 쌍이 모이면 LinkedList를 Tree로 변경한다. 그리고 다시 6개로 줄어든다면 다시 LinkedList로 변경한다. 트리는 LinkedList보다 메모리 사용량이 많고, 데이터가 적을 때는 LinkedList와의 Worst Case에 대한 수행시간 차이가 크게 의미가 없기 때문이다.

 

동적 확장

해시 테이블은 메모리의 효율성을 위해 기본적으로 전체 키의 크기보다 작게 만든다. 이로 인해 해시 충돌이 발생하고 성능상 손실이 발생하므로, Hashmap은 key-value 쌍 데이터 개수가 일정 개수 이상이 되면 해시 버킷의 수를 두배로 늘려 해시 충돌의 확률을 줄인다.

 

 

 

 

---

 

본 게시글은 한국외국어대학교 컴전학부의 신찬수 교수님의 유튜브 강의를 보고 학습한 내용을 작성한 학습기록입니다.

 

자료구조 과목 소개 - YouTube

 

 

- 참고글

https://velog.io/@adam2/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%ED%95%B4%EC%8B%9C-%ED%85%8C%EC%9D%B4%EB%B8%94