〔Java〕해시맵(HashMap)과 해시테이블(HashTable)

 

1. 해시(Hash) 함수

• 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수
• 해시테이블과 해시맵은 각각의 Key 값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 해당 index를 활용해 값을 저장하거나 검색하기 때문에 O(1) 의 빠른 검색 속도를 보인다

---

 

2. HashMap/HashTable

맵(Map)이란 키(Key)와 값(Value) 두 쌍으로 데이터를 보관하는 자료구조

• 해시맵과 해시테이블 모두 두 개의 객체를 키와 값의 한 쌍으로 묶어 보관하는 자료구조
• 둘의 차이는 thread safe 한가 아닌가에 있다
• 해시맵은 thread safe 하지 않고 해시테이블은 thread safe 하다

 

Java Platform SE 8

[JAVA] HashTable의 개념 및 사용법 정리

[Collection] 이것만 알면 해시맵(HashMap) 정복 가능 - HashMap의 특징, 사용법 예제

 

thread safe 의 의미?

• Multi-thread 환경에서 공유자원에 대해 동기화(synchronized) 설정을 하지 않으면 여러 쓰레드가 동시에 하나의 공유자원에 접근하여 문제가 발생할 가능성이 있다
• 하지만 thread safe 한 메소드는 synchronized 키워드가 걸려 있어 한 번에 하나의 쓰레드만 해당 메소드를 이용하기 때문에 공유자원에 여러 쓰레드가 동시에 접근하는 문제를 차단하므로 '안전' 하다고 표현하는 것이다
• 해시맵과 다르게 해시테이블만 thread safe 한 이유는 내부에 구현된 코드를 보면 메소드에 전부 synchronized 키워드가 걸려있기 때문이다
• 따라서 멀티쓰레드 환경에서는 해시맵보다 해시테이블을 사용하는 것이 안전하다
• 하지만 싱글쓰레드 환경이라면 해시맵을 사용하는 것이 효율적이다
• 기타 arrayBlockingQueue, arrayBlockingDeque, synchronizedList 처럼 Blocking 또는 synchronized 키워드가 들어있는 자료구조들도 thread safe 하다

 

[Java] 혼동되는 synchronized 동기화 정리

 

[Java] Queue 의 종류와 용법, 자바 병렬 프로그래밍 - 구성 단위

 

---

 

 

3. HashMap/HashTable 의 순회

[Java]HashMap 순회하는 방법

• HashTable.keySet() 을 통해 해시테이블의 key 들만 모은 set 을 얻어내고, for 반복문을 돌리는 방법
• 또는 HashTable.entrySet() 을 통해 key 와 value 한 쌍의 Entry 객체들을 통째로 얻는 방법도 있다

 

---

 

4. HashTable 의 값에 List 담기

[JAVA] 같은 key인 경우, value에 리스트(list)로 담기

• Integer 와 같은 객체 타입을 Value 로 담을 때와 동일한 방식으로 사용하면 됨

 

---

 

5. 해시 충돌(Hash Collision)

• 자바의 hashCode() 메서드가 int 형 정수를 반환한다는 점으로 인해 서로 다른 객체의 해시코드가 같은 경우도 생긴다

☕ 자바 객체의 hashCode는 고유하지 않다 ❌

 

• 자바의 Hashmap 은 Seperate Chaining 방식을 채용하여 해시 충돌 시 해당 버킷값을 첫 부분으로 하는 연결 리스트로 해결

[JAVA] HashMap의 해시충돌(hash collision)과 자바의 대응책