자료구조 : Hash

컴퓨터 사이언스에서 대표적인 자료구조인 Hash는 key-value로 값을 찾는 알고리즘에 있어서 가장 빠른 속도를 보여줍니다. 

 

때문에 많은 언어에서 Hash 자료구조를 구현해서 사용하고 있습니다. 

 

이번 포스팅에서는 Hash는 무엇이고 어떻게 값을 찾는지, 자바에서는 어떻게 활용하고 있는지에 대해서 알아보도록 하겠습니다.

 

Hash

Hash란 무엇일까요? Hash는 특정한 숫자 혹은 문자 혹은 둘의 혼합으로 이루어진 key라고 생각하시면 됩니다. 

 

보통 어떤 값은 Hash Function에 의하여 해쉬로 바뀝니다. 그리고 그 Hash를 key로 하는 저장 공간을 만들고 나중에 해당 값을 찾으려면 그 값의 Hash값을 대응해서 찾습니다. 

 

Hash Function은 key를 고정된 길이의 해쉬로 변경해주는 역할을 합니다. 이 과정을 hashing 이라고 합니다. 

 

간단하게 정리하자면 key를 해시함수라는 함수에 input으로 넣어서 output으로 나오는 것이 Hash(해시)라고 생각하시면 되고, 이 Hash가 저장위치가 된다고 생가갛면 됩니다. 

 

이러한 Hash를 사용했을 때의 장단점을 무엇일까요?

 

장점

해시테이블은 key-value가 1:1로 매칭되어 있기 때문에 삽입, 삭제, 검색의 과정에서 모두 O(1)의 시간복잡도를 가지고 있습니다. 시간복잡도에서 O(1)이면 아주아주 빠른 속도이고 가장 빠른 속도입니다. 

 

단점

단점에는 여러가지가 있는데

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

 

이 단점들 중에서 가장 핵심적인 해시충돌에 대해서 알아보도록 하겠습니다. 

 

해시충돌이란 어떤 key 값을 해시함수에 의해 해시값으로 만드는 과정에서 동일한 해시값이 나오는 경우를 말합니다. 

 

이러한 해시충돌을 해결하기 위해 개방주소법을 이용합니다. 

 

위의 그림에서 John과 Sandra의 해시가 152로 동일해서 충돌이 일어났습니다. 이때 Sandra는 바로 그 다음 비어있던 153 해시에 값을 저장합니다. 그 다음 Ted가 테이블에 저장하려 했으나 본인의 해시에 이미 Sandra로 채워져 있어 Ted도 Sandra처럼 다음 비어있던 154 해시에 저장합니다. 

 

이런식으로 충돌이 발생할 경우 비어잇는 해시를 찾아 저장하는 방법이 개방주소법입니다. 이때 비어있는 해시를 찾는 방법은 두가지가 있습니다. 

 

• 선형탐색 : 위와 같은 예제가 바로 선형탐색입니다. 해시가 충돌나면 그다음 또 충돌나면 그 다음 이렇게 값을 1씩 증가시켜 탐색하는 과정입니다. 
• 제곱 탐색 : 말 그대로 제곱에 해당하는 해시에 저장하는 방식입니다. 선형탐색과 다르게 공간을 많이 확보해 놔야 한다는 단점이 있습니다. 

 

이러한 해시를 자바에서는 어떻게 사용하고 있을까요?

 

HashMap과 HashSet

자바에서는 이러한 Hash자료구조를 이용해 HashMap과 HashSet을 지원하고 있습니다. 둘 다 해시를 사용하기 때문에 삽입, 삭제, 검색의 과정에서 빠른 성능을 보여주며 대표적으로 사용되는 클래스입니다. 

 

하지만 자바에서는 삽입 순서를 보장해야 한다거나, 동시성 문제를 해결해야 한다거나 하는 이유로 확장된 클래스를 사용하기도 합니다. 

 

LinkedHashMap, LinkedHashSet

삽입 순서를 보장해야 하는 경우 LinkedHashMap, LinkedHashSet을 사용하는데 둘 다 삽입에 대한 순서를 보장하지 않는 Hash의 특징을 보완하기 위해 나온 클래스입니다. 

 

Linked 한 List를 제공해야 하기 때문에 순수한 HashMap, HashSet 보다는 무겁지만 이렇게 무거워도 기존 Hash의 특징인 시간복잡도가 O(1)이라는 특징은 변하지 않습니다. 따라서 성능적으로 사용하는데에는 문제가 없습니다. 

 

ConcurrentHashMap

우리가 HashMap을 이용한다는 것은 자바 내부적으로 엄청나게 많은 일들이 일어납니다. 간단하게 두 상황을 가정해보도록 하겠습니다.

 

Map<String, String> map = new HashMap<>();

Thread 1
map.put("hi", "hi");

Thread 2
map.get("hi");

이 상황에서 동시성 문제가 발생할 수 있습니다. 바로 Map이 정상적으로 put 하기 전에 get을 요청하는 경우이죠. Map 입장에서는 put으로 객체를 만들지도 않았는데 갑자기 get을 요청해버리니 값이 꼬여버리거나 이상한 값이 리턴되는 상황이 발생합니다. 

 

ConcurrentHashMap에서는 이러한 상황을 방지하기 위해 다양한 노력을 기울이고 있습니다. 

 

ConcurrentHashMap은 조회(get)에는 동기화를 하지않고 삽입과 삭제에 대해서는 동기화를 synchronized를 통해 진행하여 동시성 문제를 막습니다. 

 

또 이런 경우가 있을 수도 있겠죠

Map<String, String> map = new HashMap<>();

Thread 1
map.put("A", "A");

Thread 2
map.put("B", "B");

위와 같은 상황에서 스레드1과 스레드2가 거의 동시에 일어난다면 어떻게 될까요?

 

위에서 설명했듯이 동기화가 되어있기 때문에 문제없을 것 같네요. 하지만 단순히 synchronized로 동기화 했기 때문에 동시성 문제가 발생하지 않는 것이 아닙니다. 

 

단순히 synchronized로 Wrapping해서 동기화 하였다면 성능적인 부분에서 문제가 발생할 수 있습니다. 스레드가 lock 을 획득하고 다음 스레드는 lock을 획득하기까지 해당 메서드에 접근할 수 없기 때문에 기다려야 하는 상황이 발생합니다. 

 

ConcurrentHashMap은 Segment라는 개념을 도입해 각각의 스레드가 해당 스레드에 맞는 Segment를 부여받고 그 Segment에 해당하는 일만 수행하기 때문에 동기화 작업과 별개로 동시성 문제가 발생하지 않습니다. 

 

즉, 스레드1은 1번 Segment를 부여받고 스레드2는 2번 Segment를 부여받기 때문에 스레드가 동시에 실행되어도 부여받은 Segment에 의해 작업이 분리되기 때문에 동시성문제가 해결됩니다. 

 

아무튼 HashMap은 ConcurrentHashMap이라는 강력한 동시성 문제 해결 방안 덕분에 실무에서 안전하게 HashMap을 사용할 수 있게 해줍니다. 

 

더 자세한 내용은 아래의 링크를 타고 들어가시면 알 수 있습니다.

https://coding-review.tistory.com/278

ConcurrentMap, ConcurrentHashMap

 

그럼 HashSet은 어떨까요? 

 

안타깝게도 HashSet도 Thread-safe 하지 않지만 HashMap처럼 따로 동기화 작업을 한 클래스가 없습니다. 

 

따라서 HashSet의 동시성 문제를 해결하기 위해서는 따로 동기화 작업을 거쳐야 합니다. 

 

 

 

이렇게 Hash에 대해서 알아보고 자바에서는 Hash를 어떻게 이용하는지까지 알아봤습니다. 크게 어려운 부분이 없어서 이해하는데 큰 어려움이 있지는 않았던 것 같습니다. 

 

긴 글 읽어주셔서 감사합니다. 저는 다음 포스팅에서 뵙도록 하겠습니다.

 

 

 

출처

https://www.inflearn.com/questions/347336/threadlocal-%EB%8F%99%EC%8B%9C%EC%84%B1-%EC%9D%B4%EC%8A%88-arraylist-hashmap-hashset

ThreadLocal 동시성 이슈 (ArrayList, HashMap, HashSet) - 인프런 | 질문 & 답변

 

https://www.baeldung.com/java-linkedhashset

=> 자바 공식 가이드 사이트

 

https://go-coding.tistory.com/30

[자료구조] Hash의 개념 및 설명