LinkedHashMap 내부 구조? 모르죠?

요즘 빈등록이 어떻게 이루어지는지 내부 동작 구조를 알아보고있는 와중에

LinkedHashMap을 이용해 matchingBeans라는 빈이름 등록 변수를 만드는 것을 확인하였다. linkedhashMap에 대해 단순히 순서를 보장한 hashmap이라는 것만 알고 있을 뿐, 그 구조는 어떻게 이루어지고 무엇때문에 순서가 발생하는지를 몰라서 이번 기회 알아보려고 한다.

📌공식문서에 표현한 linkedhashMap은?

오라클 문서에서 linkedhashmap은

• Map을 상속받았고, hashMap을 확장한 구조
• doubleLinkedList 형태
  라 지칭하고 있다.

doubleLinkedList?
내가 알고 있는 linkedList는 값과 다음번 노드의 주소를 포함하고 있는 형태이다. 그런데 doubleLinkedList는 무엇이지?

단순 연결 리스트(linked list)와는 다르게 노드가 이전 노드(previous)와 다음 노드(next)로 구성되어 있는 형태이다. 즉, LinkedList를 이중으로 사용하여 요소의 순서를 유지하는 것이다.

🔔 자바의 LinkedList는 doubleLinkedList이다?
자바의 LinkedList는 doubleLinkedList로 구현되었다고 명시되어 있다. LinkedList의 단방향성 특징으로 다음 노드에 대한 정보만 있기 때문에 이전 노드를 접근하기에는 어려움이 있기 때문에 doubleLinkedList형태로 만든것이라 생각한다.

📌내부 구조

HashMap과는 별도로 LinkedHashMap에서는 accessOrder 이라는 값을 가지고 있다.

accessOrder는 Entry에 access하는 mode를 나타낸다.
true일 경우 입력된 순서 중에 access빈도 낮은 것들부터 접근하고, false일 경우 입력된 순서로 Entry에 접근한다.

그래서 진짜 내부구조는 어떻게 생겼는데??

linkedList는 키와 값 뿐만아니라 next, after, before를 가지고 있다.

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

📌HashMap과의 차이

• HashMap을 확장한 구조이기 때문에 HashMap의 장점 + 순서보장을 할 수 있는 구조가 linkedHashMap라고 할 수 있다.
• 순서 지정 기능으로 인해 HashMap보다 더 많은 메모리가 필요하다.
• 시간복잡도는 HashMap과 동일하게 get,put,remove,containsKey 메소드를 호출할 때 O(1)을 가진다.
• HashMap과 마찬가지로 동기화 처리가 되어있지 않기 때문에 multi-thread환경에서 사용은 적절하지 않다는 특징을 가지고 있다.

참고)

• https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html
• https://stackoverflow.com/questions/31698572/understanding-acessorder-linkedhashmap-implementation-in-java
• https://www.javamadesoeasy.com/2015/02/linkedhashmap-custom-implementation.html
• https://www.java67.com/2012/08/difference-between-hashmap-and-LinkedHashMap-Java.html