LinkedHashMap 구조

LinkedHashMap 구조

// HttpHeader 객체
HttpHeaders headers = new HttpHeaders();

// HttpBody 객체
MultiValueMap<String, String> params = new LinkedMultiValueMap<>();

// Http body param 과 Http header 를 가진 엔티티
HttpEntity<MultiValueMap<String,String>> naverTokenRequest = new HttpEntity<>(params, headers);

네이버 API 연동을 위한 HTTP 요청을 생성하던중 LinkedMultivalueMap 객체를 사용하게 되었다.

LinkedMultivalueMap 은 내부적으로 LinkedHashMap 을 사용하고, 하나의 키에 여러 값을 저장할수 있는 객체이다.

LinkedHashMap 은 어떤 구조로 자료를 저장하는지 궁금해서 정리했다.

 

LinkedHashMap 은 key, value 외에도 next, after, before 값을 가진다.

after , before 값은 엔티티 간의 순서를 보장하기위해 이전의 노드 주소와 다음 노드 주소를 가르킨다.

이를통해 순서를 보장할 수 있게된다. LinkedList 같은 원리인 것이다.

참고로 자바는 Linked~ 자료구조는 모두 이전노드와 다음노드 주소를 동시에 가지는 양방향으로 구현한다.

 

흥미로운건 next 값이다. 해시값을 사용할때는 '해시 충돌' 문제가 발생할 수 있다.

해시충돌은 서로 다른 엔티티가 동일한 해시값을 가지는 현상을 말한다.

next 값은 해시충돌을 해결하기 위해 존재한다.

 

LinkedHashMap 은 동일한 해시값을 가지는 엔티티를 버킷테이블(ArrayList) 의 동일한 배열값에 배치한다.

그 이후 체이닝을 통해 엔티티를 배치한다. next 값은 체이닝을 통해 연결된 다음 엔티티를 가르킨다.

해시충돌로 인한 문제를 방지한다.

- before : 이 노드 앞에 삽입된 노드를 가리킴
- after : 이 노드 뒤에 삽입된 노드를 가리킴
- key : 제공된 키
- value : 제공된 값
- next : 배열 테이블의 동일한 버킷에 있는 다음 노드를 가리킴

 

<LinkedHashMap>

- HashMap의 빠른 검색속도 O(1) + 순서보장

- 순서보장을 위해 더 많은 메모리가 필요하다.

- HashMap과 동일하게 동기화처리가 되어있지않다. 멀티쓰레드 환경에 적합하지 않다.