[자료구조] HashMap 정리하기

 

 

 많은 자료구조 중에서 Map은 정말 많이 사용하는 자료구조 중 하나이다. 나도 강의를 통해서 듣고 혼자서도 활용해본 적도 많지만 이번에 새로운 알고리즘을 공부하면서 문득 한 번은 정리를 해놓는 게 좋을 것 같아서 정리하기로 마음먹었다.

 

---

 

Hash? Map ?

HashMap은 Hash와 Map 이 합쳐져서 만들어진 용어다. Map은 파이썬에서도 한번 공부한 Key와 Value를 가지고 있는 자료구조라는 것은 알겠는데 Hash란 무엇일까? 위키백과의 정의만으로도 의미 파악에 큰 도움이 되었다.

 

해시 함수 (hash function)는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 해시 함수에 의해 얻어지는 값은 해시 값, 해시 코드, 해시 체크섬 또는 간단하게 해시라고 한다. 

(출처 : https://ko.wikipedia.org/wiki/%ED%95%B4%EC%8B%9C_%ED%95%A8%EC%88%98)

 

추가적인 설명을 덧붙이자면 Key를 저장할 때 저장할 주소를 생성하는 연산을 하는 Hashing을 통해서 Key값의 주소를 생성한다. 이렇게 모든 Key에 마다 생성된 주소가 있기 때문에 자료의 검색할 때 O(1)의 빠른 시간 복잡도를 가진다. 즉 데이터를 Key와 Value로 매핑하는 과정이 Hashing이며,  HashMap은 Hash를 사용하는 (Hashing을 사용하는) Map이라고 생각하면 되겠다.

 

Map의 가장 큰 특징이라고 하면 바로 Key값은 절대 중복되지 않는다는 점이다. 하지만 Hashing을 통해서 같은 주소에 다른 Key를 저장한다면? 이것을 해쉬 충돌(Hash Collision)이라고 하는데 이것을 방지하기 위해서 두 가지 방법을 사용한다.

 

Open Hashing - Chaining 기법

• Value를 담는 버킷이라는 공간에 LinkedList를 사용하여 동일한 키에 데이터들을 연결해주는 기법

 

Close Hashing - Linear 기법

• 충돌이 일어나는 Hash 주소 다음에 나오는 첫 번째 빈 공간에 해당 데이터를 저장

 

 

 

HashMap? HashTable?

 

그런데 자바에서 Map을 사용하려고 검색을 해본 사람이라면 HashMap과 HashTable이 둘 다 나오는 것을 본적이 있을것이다. 둘다 Map 인터페이스를 구현한 점은 동일하지만 Thread-safe 부분에서 차이가 있다. 

 

thread safety는 멀티 스레드 프로그래밍에서 일반적으로 어떤 함수나 변수, 혹은 객체가 여러 스레드로부터 동시에 접근이 이루어져도 프로그램의 실행에 문제가 없음을 뜻한다. 보다 엄밀하게는 하나의 함수가 한 스레드로부터 호출되어 실행 중일 때, 다른 스레드가 그 함수를 호출하여 동시에 함께 실행되더라도 각 스레드에서의 함수의 수행 결과가 올바로 나오는 것으로 정의한다.

(출처 : https://ko.wikipedia.org/wiki/%EC%8A%A4%EB%A0%88%EB%93%9C_%EC%95%88%EC%A0%84)

 

 

 

Thread는 프로세스(process) 내에서 실제로 작업을 수행하는 주체를 의미하는데 Thread-safe 하다는 것은 어떤 Thread에서 접근해서 작업을 해도 프로그램의 실행에 문제가 없다는 뜻이다. 이것은 어디에서 접근해서 작업을 해도 동일한 결과가 나와야 한다는 의미로 동기화가 실시간으로 이루어진다고 생각할 수 있다. 이 차이점과 HashMap과 HashTable의 기타 차이점을 정리해보면 다음과 같다.

 

HashMap

• Thread-safe 하지 않음
• null 허용

HashTable

• Thread-safe 
• null 허용하지 않음