[Java, 자료구조] Map

Array와 List의 장점을 합친건 없을까?
유연하면서도 빠르게 조회할 수 있는건 없을까?

Map

map은 유연하고, 값을 빠르게 찾아낼 수 있게 한다.
특정 index를 사용하지 않고 key를 사용해 값을 찾아준다.
(=딕셔너리)

hashing → 키를 array 크기에 맞게 적절히 겹치지 않는 index로 변경한다.
"키와 값은 연결되어 있다. 키는 곧 값과 같다."

매핑 테이블

Key	Value
k	v

시간 복잡도: O(1)

Hashtable

java에서는 map을 Hashtable로 제공해준다. (sync)
Dictionary 클래스를 상속받고 있고, Map 인터페이스를 구현하고 있다.
put, get, remove, replace, contains 등의 메소드는 Map에서 제공하는 메소드들이다.

Map<String, Integer> map = new HashTable<>();

HashMap

(async)
Hasttable과 마찬가지로 Dictionary 클래스 상속, Map 인터페이스를 구현하고 있다.
나머지도 비슷하다.

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

정리

그렇다면 언제 무엇을 쓰는 것이 좋을까?

💡 Thread-Safe 가 필요하면 Hashtable을 사용하고 (멀티스레드 환경),
필요하지 않다면 HashMap을 사용하자.
Thread-Safe 하고 많은 동시성이 요구된다면, ConcurrentHashMap을 쓰자.