[JAVA/자료구조] Map / HashMap / Hashtable

Map

• Map< K, V >
• key - value 쌍으로 관리하는 메서드를 구현함
• 검색을 위한 자료구조
• key값을 이용하여 값을 지정하고, 값을 꺼내오는 방식 - hash 알고리즘으로 구현됨
• 객체의 유일성 비교를 위해 equals() , hashCode() 메서드를 구현해야 함.

---

CollectionFramework의 HashMap, Hashtable의 사용법이 궁금하신 분은 목차의 "HashMap 선언" 부터 보시면 됩니다!

---

HashMap, Hashtable의 구조

• 키(Key) : 해시 테이블 접근을 위한 입력 값
• 해시 함수(Hash Function) : 키를 해시값으로 매핑하는 연산을 수행
• 해시 값(Hash Value) : 해시 테이블의 인덱스
• HashMap, Hashtable : key - value를 연관시켜 저장하는 데이터 구조

HashTable에 접근하기 위한 key가 주어지면, key가 Hash function을 통과하여 hash값으로 변경된다.

Hash function을 통해 key를 변경하여 Hash값을 얻으면, 그 Hash값을 인덱스로 삼아 HashTable에 접근한다.

---

Hash값 충돌

임의의 key1과 key2가 있을 때, Hash function을 통해 나온 Hash값이 동일한 경우가 있을 수 있다. 이를 해시 충돌 이라고 한다.

이 때, 일정한 규칙에 따라 Hash값을 변경해주어 해결할 수 있다. 그게 개방주소법과 분리연결법이 있다.

---

개방 주소법(Open Address)

• 해시 충돌 발생 시 테이블에서 비어있는 공간을 찾아 데이터를 저장하는 방법이다.
• hash와 value의 1대1 관계가 유지된다.

1. 선형 탐사법(Linear Probing)

• 빈 공간을 순차적으로 탐사하는 방법

충돌 발생 지점부터 이후의 빈공간을 순서대로 탐사한다.

 

일차 군집화 문제가 발생한다.

그림에는 10개의 공간만 표시했지만, 실제로는 매우 넓은 공간 중 일정 위치에 값을 저장한다.

그런데 충돌 발생 지점에서부터 선형적으로 빈공간을 찾는다면,

해당 충돌 지점 주변에 데이터가 몰리는 경우가 발생하게 된다.

2. 제곱 탐사법(Quadratic Probing)

• 빈 공간을 n제곱만큼의 간격을 두고 탐사하는 방법

충돌 발생 지점부터 n제곱을 곱한 위치의 공간을 확인해보고,

비어있으면 데이터를 삽입하고 비어있지 않으면 그 위치에서 다시 n제곱 위치를 탐색하는 과정을 반복한다.

(n = 0,1,2,3...)

 

일차 군집화 문제가 일부 보완되지만, 이차 군집화 문제 발생 가능성이 있다.

3. 이중 해싱(Double Hashing)

• 해싱 함수를 이중으로 사용하는 방법

해시함수 1 : 최초 해시를 구할 때 사용

해시함수 2 : 충돌 발생 시, 탐사 이동 간격을 구할때 사용함

 

선형탐사, 제곱탐사법에 비해 데이터가 골고루 분포된다.

---

분리 연결법(Separate Chaining)

• 해시테이블을 연결 리스트로 구성하는 방법

충돌 발생 시, 테이블 내의 다른 위치를 탐색하는 것이 아니라 연결리스트를 이용하여 해당 테이블에 데이터를 연결한다.

---

HashMap과 Hashtable

HashMap과 Hashtable 모두 Map 인터페이스를 구현한 클래스이다. 거의 비슷하지만 다른점이 있다.

가장 중요한 것은 동시성 문제이다. 

Hashtable은 Thread-safe하고, HashMap은 그렇지 않다.

따라서 멀티스레드 환경에서는 Hashtable을 싱글스레드 환경에서는 HashMap을 사용해야 할것이다.

• HashMap : not synchronized, Thread-safe X -> single thread
• Hashtable : synchronized, Thread safe -> multi thread 

Java에서는 HashMap과 동일하지만, Thread-safe하게 만든 synchronizedMap, ConcurrentHashMap이 있다.

두 클래스는 synchronized, Thread-safe 한 HashMap이라고 생각하면 된다.

 

HashTable은 JDK 1.0부터 있던 Java의 API이고,

HashMap은 Java 2에서 처음 선보인 Java Collections Framework에 속한 API이다.

HashTable은 구현에 거의 변화가 없는 반면, HashMap은 지속적으로 개선되고 업데이트 되고 있다고 한다.

 

따라서 왠만하면 HashMap을 사용하고, 멀티스레드 환경에서는 ConcurrentHashMap를 사용하는게 좋겠다.

 

---

HashMap 선언

HashMap, Hashtable 모두 Map 인터페이스를 구현한 클래스이기 때문에 아래와 같이 Map형으로 선언할 수 있다.

HashMap<String,Integer> hashMap = new HashtMap<>();
Hashtable<String,Integer> hashtalbe = new Hashtable<>();

Map<String,Integer> map1 = new HashtMap<>();
Map<String,Integer> map2 = new Hashtable<>();

---

Methods

put() : 값 넣기 

• put(K,V) : 데이터 쌍 넣기
• putIfAbsent(K,V) : 이미 있으면 그대로, 없으면 값 넣어줌.

Map<String,Integer> map = new HashMap<>();
map.put("A", 1);//{A=1}
map.put("B", 3);//{A=1, B=3}
map.putIfAbsent("C", 5);//{A=1, B=3, C=5}
map.putIfAbsent("C", 7);//{A=1, B=3, C=5}

---

get() : 값 조회

• get(K) : Key에 해당하는 value 꺼내기
• getOrDefault(K, default) : Key에 해당하는 value를 꺼내거나 , 없으면 default값 꺼내기
• keySet() : K들만 뽑아냄
• values() : V들만 뽑아냄

//{A=1, B=3, C=5}
int a = map.get("A"); //a = 1
int e = map.getOrDefault("E",-1); //e = -1

System.out.println(map.keySet()); //[A, B, C]
System.out.println(map.values()); //[1, 3, 5]

---

remove() : 값 삭제

• remove(K) : K에 해당하는 값 삭제 + 삭제되는 V return
• remove(K, V) : K와 V 모두 존재할때만 삭제 + true,false로 출력도 가능

//{A=2, B=4, C=10}
map.remove("A");// {B=4, C=10}
map.remove("C", 11); //{B=4, C=10}
map.remove("C", 10); //{B=4}

---

replace () : 값 교체

• replace(K,V) : 교체
• replace(K,old V, new V) : old Value가 일치할때만 new Value로 교체

* 이미 존재하는 key에 put()메서드를 이용해서 값을 넣으면 새로 넣은 값으로 변경된다.

//{A=1, B=3, C=5}
map.replace("B", 4); //{A=1, B=4, C=5}
map.replace("C",6); //{A=1, B=4, C=6}
map.replace("C",6,10); //{A=1, B=4, C=10}
map.replace("C",6,12 ); //{A=1, B=4, C=10} => C=6이 아니기때문에 값은 그대로.

map.put("A",2); //{A=2, B=4, C=10}

---

기타 기능

size(), isEmpty(), clear()

• size() : map의 사이즈를 반한
• isEmpty() : map이 비어있는지 여부를 boolean으로 반환
• clear() : map의 데이터를 모두 삭제

---

containsKey(), containsValue() 

값이 존재하는지 확인한다.

 

//{A=1, B=3, C=5}
System.out.println(map.containsKey("A")); //true
System.out.println(map.containsValue("5")); //true
System.out.println(map.containsValue("7")); //false

---

Map.of()

map을 생성함과 동시에 값을 넣는다.

Map<String, Integer> map1 = Map.of("A",1,"B",2,"C",3);
System.out.println(map1); //{C=3, B=2, A=1}