[JAVA] Map - HashTable, HashMap, LinkedHashMap

Map의 특징

Map은 Java에서 많이 사용하는 자료구조입니다.

• 기본적으로 Key - Value를 한쌍으로 저장합니다.
• Key를 통해 Value를 찾고, Key의 중복을 허용하지 않습니다.
• Interface인 Map의 구현체로는 HashMap, LinkedHashMap, TreeMap, HashTable이 있습니다.
• Map<K, V> Signautre를 주로 사용합니다.

Map<String, String> hash = new HashMap<>();

hash.put("riitty", "JAVA");
hash.put("sleep", "good");

hash.get("ritty");

---

Hash

Hash 알고리즘을 사용하였는데, 이 때, 같지 않은 객체 A, B의 대하여 A.hashCode() != B.hashCode() 라면 완전한 해시 함수라고 한다.

hashCode의 결과 자료형은 int 형인데 $2^{32}$ 보다 생성 가능한 객체가 많기 때문에, 완전한 해시 함수를 만들기는 불가능하다. 또, O(1)을 보장하기 위해서 $2^{32}$인 배열을 가지고 있어야 하기 때문에 실제 구현체에서는 메모리 절약을 위해 hashCode() % M 을 사용하고 있다.

따라서 같은 서로 다른 객체라도 $1/M$ 의 활률로 같은 해시 버킷을 사용하게 되는데, 이를 해결하는 대표적인 방법으로 Open Addressing, Separate Chaining이 있다. Open Addressing의 장점인 Cache Rate이 높은 점은 HashMap의 크기가 클 수록 사라지는 반면, 데이터를 삭제 할 때 비 효율적이기 때문에 java 진영에서는 Separate Chaining을 사용하고 있다.

---

HashTable

• JDK 1.0부터 있던 Java의 API로 이후 구현에 변화가 거의 없는 편입니다. - Legacy 위해 존재
• hashCode()를 사용해 식별하기 때문에 동일한 값이 발생 할 수 있습니다.(해시 충돌)
• Key, Value 값으로 Null을 허용하지 않습니다.(HashMap 과의 차이점)

HashMap

• 보조 해시 함수를 사용한다.
• linked List, Tree 형태를 같이 사용해, 값이 많을 경우 트리로 전환, 적을 경우 Linked List를 사용한다.
• 하나의 Null Key, 복수의 Null Value를 허용합니다.
• 입력 순서를 보장하지 않습니다.
  랜덤 접근 : $O(1)$
• String의 경우 웹상에서 사용하는 URL 등의 데이터가 앞 부분이 동일하게 구성되는 경우가 많은데, 앞 부분만 짤라서 Hash 하던 기존의 방법이 문제가 되었고, Horner's method를 사용해 따로 Hash 하고 있다.

LinkedHashMap

• HashMap을 상속받은 class 입니다.
• 입력 순서를 보장하고 있습니다.
  랜덤 접근 : $O(logn)$

출처 : https://d2.naver.com/helloworld/831311