[자료구조] 해시(Hash), 그리고 JAVA

해시 (Hash)

---

"입력 값(Input)을 고정된 길이의 데이터로 변환"

해시 자료구조의 특징

1. key에 value를 매핑하는 구조이다.

2. 해시 함수(해시 알고리즘) 을 통해 key의 데이터를 Hash Table에 저장한다.

3. key를 통해 저장된 데이터를 찾기 때문에 탐색 속도가 매우 빠르다.

 

위 특징들을 가진 덕에 '해시 테이블' 구조를 가진다.

 

Hasing의 과정

"해시 함수에서 해시를 출력하고 해시 테이블에 저장하는 과정"

 

 

 

장점과 단점을 알아보자.

 

데이터 저장과 읽기가 매우 빠르다. 자료구조 특성 상 key에 매핑된 value 확인이 매우 쉬워진다.

그러나 저장 공간을 많이 차지하고, 여러 키에 해당하는 주소가 동일한 경우 Collision이 발생한다.

이 Collision을 해결하기 위한 별도의 자료구조를 구현해야 한다.

 

 

기술에 완벽은 없다

"이론상 완벽한 해시 함수는 존재할 수 없다."

 

Collision, 충돌

 주로 해시 알고리즘의 성능이 좋지 않거나 저장되는 데이터의 양이 해시 테이블의 크기보다 큰 경우 발생한다. 이를 해결할 수 있는 방법들을 알아보자.

 

1. Chaining

Collision 발생 시 Linked List 자료구조를 이용하여 해결하는 방법.

각 버킷을 하나 이상의 값을 저장할 수 있는 Linked List로 변경한다!   -->  ( 버킷의 크기를 동적으로 늘린다고 생각하자!)

데이터의 주솟값은 바뀌지 않는다.

 

2. Linear Proving

Collision 발생 시 해당 해시 주소의 다음 주소부터 빈 공간을 찾아 순회하고, 빈 공간을 찾을 시 데이터를 저장하는 방식.

* 직접 주소 개방 기법 중 하나이다.

데이터의 주솟값이 바뀐다.

---

Java에서의 Hash

HashMap :  import java.util.HashMap;

HashMap<String, String> h1 = new HashMap<>(); // 해시맵 생성

h1.put("승규", "꽃미남"); // 데이터 추가

//데이터 삭제
h1.clear(); //모든 데이터 삭제
h1.remove(Object Key); // Key와 일치하는 Value 삭제
h1.remove(Object Key, Object Value); // Key와 Value 동시에 일치하는 데이터 삭제

//데이터 수정
h1.replace("승규", "미남"); //Key와 일치하는 Value 수정
h1.replace("승규", "꽃미남", "미남"); // Key와 Value 동시에 일치하는 Value 수정

//데이터 확인
h1.containsKey(Object Key); // key있으면 true 반환
h1.containsValue(Object Value); // value있으면 true 반환
h1.isEmpty(); // 데이터 유무 확인
h1.get(Object Key); // key와 매핑된 value 값 확인

 

시간 복잡도

삽입 및 조회 : O(1)

해시 충돌이 발생 할 경우 : O(n)

대략 3만개의 데이터를 사용할 경우 0.6초가 소요된다

 

 

 

---

 

JDK 7 까지는 LinkedList를 이용하여 chaining 기법을 이용해 Collision을 해결!

JDK 8 부터는 LinkedList와 Red Black Tree를 혼용하여 chaining 을 활용

 - linked list는 탐색할 때 시간복잡도가 O(n)이지만 red black tree는 O(log n)이 든다. jdk 8부터 성능적 으로 개선 됨.

 

 

 

*** HashTable과의 차이?

1. HashTable의 경우 thread-safe 하기 때문에 멀티스레드 환경에서 성능이 좋다. 멀티스레드 환경이 아니라면 HashMap사용하기

2. HashTable은 컬렉션 프레임워크가 만들어지기 전부터 존재했다. 더 이상 성능 개선이 이루어지지 않는다고 한다