Hashmap, Hashtable이 뭐냐
- Map이라는 자바 내 인터페이스를 구현한 구현체 입니다.
- Map은 key-value 값을 가지는 자료구조이며, key는 유일한 값, value는 중복을 허용하는 구조를 가지고 있습니다.
이걸 왜쓰냐?
빠른 검색을 위해서 사용합니다. 보통 검색을 하기 위해서는 배열의 저장된 값을 선형탐색 하거나, 정렬된 배열에서는 이진 탐색을 이용하여
O(n)~O(logn)만큼의 시간이 소요되는데, Hashmap을 사용하게 되면 삽입, 검색에 O(1)만큼의 시간이 소요되어 효율적입니다.
내부 동작 원리?
- key-value 값을 설정하게 되면 해시 함수를 통해 해시값(int형)에 해당하는 인덱스로 접근하게 됩니다.
- 그곳엔 buckets라는 녀석들이 존재하는데, value 값을 여기에 저장합니다.
- 하지만 key는 무한, value는 한정적이기 때문에 비둘기 집의 원리 때문에 해시 충돌이 일어나게 되어 있습니다.
해시 충돌
위와 같은 이유로 다른 키 값이 같은 해쉬 코드 값을 가지는 것을 의미합니다.
해시 충돌 피하기
체이닝과 개방 주소법이 있습니다.
체이닝
- 버킷에 데이터를 삽입하다가 해시 충돌이 발생하면 연결리스트로 연결시키는 방법입니다.
개방 주소법
해시 충돌이 일어나면 다른 버킷에 데이터를 삽입하는 방식입니다. 3가지 방식으로 삽입할 버킷을 정할 수 있습니다.
선형 탐색(Linear Probing): 해시충돌 시 다음 버켓, 혹은 몇 개를 건너뛰어 데이터를 삽입한다.
제곱 탐색(Quadratic Probing): 해시충돌 시 제곱만큼 건너뛴 버켓에 데이터를 삽입(1,4,9,16..)
이중 해시(Double Hashing): 해시충돌 시 다른 해시함수를 한 번 더 적용한 결과를 이용함.
Hashmap과 Hashtable의 차이점?
Hashtable
- 둘 다 Map 인터페이스를 구현한 구현체임은 같습니다.
- 스레드로부터 안전하며 애플리케이션 간의 여러 스레드 간의 공유가 가능합니다.
- null 값을 허용하지 않습니다.
스레드로부터 안전하다?
멀티 스레드 프로그래밍에서 여러 스레드로부터 동시에 접근해도 안전하다는 뜻입니다.
Hashmap
- 둘 다 Map 인터페이스를 구현한 구현체임은 같습니다.
- 동기화(Synchronization)가 되어 있지 않으며, 추가 코드로 동기화를 해주어야 스레드 간 공유가 가능합니다.
- key, value 모두 null 값을 삽입하는게 가능합니다.
- 그러므로 동기화되지 않거나 단일 스레드 응용 프로그램에 대해 HashMap 을 사용해야 합니다.
