CS

[Java] Java Map의 내부 구현 파악

jungmin.park 2023. 12. 18. 11:13
Java Map의 내부 구현은 어떻게 이루어져 있을지 추측해보실 수 있을까요?

 

 

Java에서 Map 인터페이스 도구가 있으며 대표적으로 Map, HashMap, TreeMap, LinkedHashMap이 있다.

 

 

Map<Key, Value>

 

Map은 key-value 구조로 구성되어 데이터를 저장할 수 있다.

key를 가지고 저장된 value를 찾을 수 있다.

key를 이용하여 데이터 검색에 최적화되어있으나, 동일한 key에 다른 데이터 value가 저장되어 있을 경우 기존에 저장된 데이터는 덮어씌워져 사라진다.

따라서 중복된 key는 존재할 수 없다.

 

 

HashMap<Key, Value>

 

 

HashMap은 Hash Table 을 이용하여 만들어졌다.

HashMap의 핵심은 배열이며, 배열의 각 슬롯은 연결리스트 또는 트리로 이루어져있다.

Hash Table은 key를 이용하여 빠르게 데이터를 찾기 위한 자료구조를 가지고 있다.

  • 특정 key는 해시 함수를 통하여 해시 값을 계산하고 buckets에 접근할 수 있는 index로 변환한다.
  • index를 통하여 bucket에 접근한다.
  • bucket에 맞는 index에 key와 value를 저장한다.

key가 해시 함수를 통해서 key에 대한 index가 만들어지고 bucket에 접근하기 때문에 저장되는 데이터가 많을수록, bucket의 크기가 작을수록 index 충돌이 발생할 가능성이 높다.

 

충돌처리

  • 여러 키가 동일한 배열의 위치에 저장되어야 할 때 이를 충돌이라고 한다.
  • 이런 충돌을 해결하기 위해 그 위치에 연결리스트를 사용한다.
  • 이 연결 리스트에는 동일한 위치에 저장되어야 하는 모든 키-값 쌍이 저장된다.

배열 크기 조절

  • 만약 HashMap이 너무 많은 데이터를 저장하게 되면 배열의 크기를 늘려야 한다.
  • 이 과정을 재해싱이라고 부르며 기존의 데이터를 새로운 크기의 배열로 옮기게 된다.

 

put()

put() 메소드를 통해 key, value 값이 저장되면 내부적으로 아래와 같은 모습으로 저장

 

  1.  key 객체의 hashCode() 값을 이용하여 내부적으로 새로운 hash 값을 구한다.
  2. 새로운 hash 값을 이용하여 table 배열에서 몇번째 index에 저장할지 index를 찾는다.
  3. 구해진 index에 entry가 이미 존재하면 linked-list 형태로 연결한다.
  4. 구해진 index에 entry가 없으면 assign한다.

 

doubling

hashMap에서는 entry를 저장할 수 있는 table 배열의 크기가 정해져 있기 때문에 많은 수의 entry가 입력되면 collsion이 자주 발생하게 되고 이는 성능저하를 가져오게 된다. 이를 방지하기 위해 HashMap은 table 배열의 사이즈를 doubling 하게 된다. (배열의 크기는 항상 2의 제곱수를 유지)

 

  1. entry 저장 시 entry 개수가 table.size * loadFactor 를 넘어서면 table을 doubling
  2. table 사이즈가 커졌기 때문에 기존에 저장된 모든 entry에 대해서 rehash를 수행하여 entry 분산
  3. table.size가 maximum_capacity를 넘어서면 doubling 하지 않음.

entry의 개수가 많아지면 doubling이 자주 일어나고 이 때 새로운 table을 위한 memory 공간 확보, 기존의 모든 entry에 대해서 rehash 등으로 인한 오버헤드가 발생 할 수 있다. HashMap 생성시 entry의 개수를 미리 예측할 수 있다면 doubling으로 인한 오버헤드를 줄일 수 있다.

 

IndexFor

내부적으로 새롭게 계산된 hash 값을 이용하여 table에 저장된 index값을 구하게 되는데 이를 위해 indexFor 함수를 호출한다.

 

 

ConcurrentModificationException

hashMap은 thread-safe 한 자료구조가 아니다. 특정 Thread가 자료구조를 읽는 중에도 다른 thread가 map 내부의 자료를 삭제할 수 있다. 이는 multi-thread 환경에서 문제가 많다. 이같은 문제때문에 HashMap에서는 entry들을 iteration 하는 도중 자료구조에 변경이 일어나면 ConcurrentModificationException을 발생시켜 해당 문제를 알려준다.

 

이를 위해 HashMap 내부에 modCount라는 변수를 두고 HashMap의 모든 업데이트와 발생시 modCount를 증가시켜준다. 그리고 entry의 interation을 시작하기 전에 modCount 값을 다른 임시 변수에 복사해 두고 매번 next 호출때마다 두 변수 값을 비교하여 차이가 발생하면 ConcurrentModificationException을 발생한다.

 

 

get()

인자로 받은 key에 매핑되는 value 값을 찾는 방식은 put의 방식과 유사하다.

 

  1.  key 객체의 hashCode() 값을 이용하여 내부적으로 새로운 hash 값을 구한다.
  2. 새로운 hash 값을 이용하여 table 배열에서 몇번째 index에 저장되어 있는지 찾는다.
  3. 구해진 index에 entry의 key와 동일한 객체인지 equals을 이용하여 비교하여 동일한 entry의 value를 리턴한다.
  4. equals 결과가 false이면 entry의 next링크를 계속 따라가며 동일한 key를 가진 entry를 찾는다.

 

 

java의 Map은 인터페이스로 인터페이스를 구현한 자료형 중에 Map, HashMap, TreeMap, LinkedHashMap있습니다.
대표적으로 HashMap은 key, value의 형태로 저장을 하게 될때 key는 해시함수를 통해 해시 값을 계산하고 buckets에 접근할 수 있는 index로 변환합니다. 만약 구해진 index에 entry가 없으면 assign하고 index에 entry가 있다면 링크드리스트로 연결합니다. 만약 hashmap에 너무 많은 데이터를 저장하게 되면 index 충돌이 발생할 가능성이 높기 때문에 이를 방지하기 위해 hashmap은 table 배열의 사이즈를 doubling하여 재해싱하여 entry를 분산하게 됩니다. entry의 개수가 많아지면 doubling이 자주 일어나고 이 때 새로운 table을 위한 memory 공간 확보, 기존의 모든 entry에 대해서 rehash 등으로 인한 오버헤드가 발생 할 수 있다. key를 통해 value를 찾을때 key객체는 hasCode() 값을 이용해 테이블에 몇번째 index에 저장되어있는지 찾습니다. entry의 key와 동일한 객체인지 equals을 이용하여 동일한 entry을 찾아 value을 리턴하게 됩니다.

 

 

 

 

 

 

 

 

참조

https://jindevelopetravel0919.tistory.com/44

https://velog.io/@songyuheon/Java-Map%EC%9D%98-%EB%82%B4%EB%B6%80-%EA%B5%AC%ED%98%84

https://mkbansal.wordpress.com/2010/06/24/hashmap-how-it-works/

https://minchangdev.wordpress.com/2014/01/12/16/