[JAVA] LinkedHashMap의 사용

LinkedHashMap

 

< LinkedHashMap이란? >

Map 인터페이스를 구현한 클래스 중 하나로, Map에 입력된 순서를 기억하는 자료구조이다.
HashMap을 확장한 구조로, HashMap의 특성에 순서가 보장된다는 특성이 추가된 자료구조이다.
( 순서가 지정되어 있기 때문에 HashMap 보다 더 많은 메모리가 필요하다.)

 

LinkedHashMap에 저장되는 키와 값은 Map.Entry 클래스를 구현한 Node 클래스에 저장된다.
Node 클래스에는 before, after 멤버가 있는데, LinkedHashMap에 입력된 순서에 따라 연결 리스트 구조를 형성한다.

 

참고 : https://hbase.tistory.com/136

 

< LinkedHashMap의 생성자 >

LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder);

1. 매개변수
   • initialCapacity : Map의 초기 용량
   • loadFactor : 맵의 재해시(rehash)를 수행할 임계값
     • 0.75f : 해시테이블이 75% 채워졌을 때 재해시를 수행한다.
   • accessOrder : 맵의 순서를 접근순서로 지정할 지에 대한 여부.
     • true : 마지막에 접근한 순서대로 유지한다.
     • false : 삽입순서대로 맵의 순서를 유지한다.
2. 재해시 (rehash)?
   • 해시 테이블은 일반적으로 배열로 구현되어있다.
   • 해시 충돌이 발생하면,
     충돌을 해결하기 위해 해당 위치에 있는 데이터를 연결 리스트나 트리 등의 데이터 구조로 저장한다.
   • 재해시란, 해시 충돌이 발생했을 때
     해시 테이블의 크기를 늘리고 모든 데이터를 새로운 해시 테이블로 다시 해싱하는 과정이다.
   • 재해시의 임계값이 작아질 수록 해시테이블이 더 적게 채워져도 재해시가 수행되므로,
     해시충돌이 발생할 가능성이 줄어든다.
   • 하지만 너무 작게 설정할 경우 재해시가 너무 빈번하게 일어나기 때문에 성능에 악영향을 미친다.

 

< 생성자의 accessOrder >

• false로 설정했을 경우

  • import java.util.*;
    public class Main {
        public static void main(String[] args) {
            Map<Integer, String> map = new LinkedHashMap<>(5, 0.75f, false);
    
            map.put(1, "apple");
            map.put(2, "banana");
            map.put(3, "cherry");
    
            map.get(2);
            map.get(1);
            map.get(3);
    
            System.out.println(map);
                // 출력결과 : {1=apple, 2=banana, 3=cherry}
    
            map.put(2, "updated banana");
    
            System.out.println(map);
                // 출력결과 : {1=apple, 2=updated banana, 3=cherry}
         }
    }

• true로 설정했을 경우

  • import java.util.*;
    public class Main {
        public static void main(String[] args) {
            Map<Integer, String> map = new LinkedHashMap<>(5, 0.75f, true);
    
            map.put(1, "apple");
            map.put(2, "banana");
            map.put(3, "cherry");
    
            map.get(2);
            map.get(1);
            map.get(3);
    
            System.out.println(map);
                // 출력결과 : {1=apple, 2=banana, 3=cherry}
    
            map.put(2, "updated banana");
    
            System.out.println(map);
                // 출력결과 : {1=apple, 3=cherry, 2=updated banana}
         }
    }

 

< 주요 메서드 >

 

기본적으로 HashMap과 같이, put, get, remove, clear, containsKey 등이 존재한다.

 

그 중 removeEldestEntry 메소드는 특정 조건에 따라 가장 오래된 엔트리를 제거할 수 있는 메소드로,
페이지 교체 알고리즘 중 FIFO 알고리즘이나 LRU 캐시 알고리즘을 구현할 때
LinkedHashMap을 상속받은 클래스에서 주로 해당 메소드를 오버라이드 해 사용한다.