Java Map의 내부 구현은 어떻게 이루어져 있을지 추측해보실 수 있을까요?
Java 에는 Map 이라는 인터페이스가 있으며 Map이란 기본적으로 key와 value 쌍으로 데이터를 저장하는 방식입니다. 인터페이스는 구현체가 필요하며 대표적으로 HashMap, LinkedHashMap, TreeMap으로 구현합니다.
HashMap은 일반적으로 가장 많이 사용되고 있습니다.
HashMap은 해시 함수를 사용하여 키를 해시 코드로 변환하고, 이를 기반으로 배열에 데이터를 저장합니다. 충돌이 발생하면 동일한 버킷에 연결 리스트 형태로 데이터를 추가합니다.
배열과 연결 리스트의 조합을 사용하며, 각 배열의 요소에는 버킷(연결 리스트의 헤드)이 저장됩니다. 각 버킷은 동일한 해시 코드를 가진 키-값 쌍을 저장합니다.
문자열인 Key가 해시함수를 통해 index와 연결됩니다. 따라서 key, value 형태로 저장 할 수 있습니다. 조회, 수정 등에서도 Key를 통해서 효율적으로 Value에 접근 할 수 있습니다. 매핑 전 원래 데이터의 값을 key, 매핑 후 데이터의 값을 hash value, 매핑하는 과정을 hashing이라고 합니다.
해시 함수를 사용하여 빠른 검색, 삽입, 삭제 성능을 제공합니다. 시간 복잡도는 삽입, 삭제, 검색은 O(1), 순회는 O(N)시간복잡도를 가집니다.
여기서 HashMap은 해시 함수에 따라 key와 value가 맵핑되기 때문에 순서가 보장되지 않게 됩니다.
추가질문
다른 Map 구현체도 추가 설명을 해주실수있나요?
순서를 보장받기 위해서는 LinkedHashMap을 사용합니다. HashMap과 기본적인 구조에서는 유사하지만, LinkedHashMap은 추가로 마치 기차처럼 각 연결 리스트의 엔트리가 이전과 다음 엔트리를 참조하여 입력한 순서를 보존하는 특징이 있습니다. 이를 통해 입력 순서를 보장받을 수 있습니다. 엔트리를 참조하는 부분을 업데이트하는 것 일반적으로는 HashMap보다는 일부 성능 저하가 있을 수 있습니다. 삽입, 삭제, 검색은 O(1), 순회는 O(N)시간복잡도를 가집니다.
TreeMap은 이진 검색 트리(Binary Search Tree)를 기반으로 한 맵 구현체입니다. TreeMap도 마찬가지로 key, value 쌍을 저장하며, Key를 기준으로 정렬된 상태를 유지하는 특징이 있습니다. 정렬된 순서를 유지해야 하거나 범위 검색이 필요한 경우에 사용됩니다. 예로 나라 이름key와 나라코드숫자를 value로 저장하면 나라이름의 알파벳순서대로 정렬되어 저장됩니다. 또한 노드를 기준으로 크고 작음을 계속 탐색하기 때문에 범위 검색에서 효율을 보여 줄 수 있습니다.
이진 검색 트리를 사용하여 검색, 삽입, 삭제가 빠르지만 HashMap보다는 느립니다. 시간 복잡도는 O(log N)입니다.