[Java] HashTable / HashMap / 연결리스트의 중간노드 찾기 / LRU 캐시

학습목표

• HashTable
• HashMap
• 연결리스트의 중간노드 찾기
• LRU 캐시

 

HashTable

• Hash table 클래스로 구현되며, maps에 key, value로 매핑 된다.
• key, value 모두 non-null이다.
• 저장과 조회가 되기 위해서는 해당 오브젝트가 해당 키로 hashCode(), equel() 구현되어야 한다.
• 해시 테이블이 생성되며 동적으로 설정되는 변수가 2가지 있다.
  • initial capacity
  • load factor
  • 두가지 변수를 임계값으로 이용해 버킷에 쓰는 원소들이 많아질 경우 링크드리스트 같은 형태를 띄게 되면 해시테이블로의 장점이 사라진다 그럴 때 load factor가 임계치에 다다르면 해시 테이블이 리프레시 되고 버킷 수(capacity)를 늘려 관리해준다.
  • 처음부터 많이 만들어 메모리를 낭비할 필요도 없이 bucket 수를 적게 가지고 시작하더라도 서서히 늘릴 수 있다는 장점을 가지고 있다(dynamic)
• Thead-safe 합니다. Synchronized 처리되어 동시성 처리시 lock이 걸리게 됩니다.
• Enumeration 여부
  • Hashtable은 not fail-fast Enumeration을 제공하지만, HashMap은 Enumeration을 제공하지 않습니다.

 

Hashtable<String, Integer> numbers
 = new Hashtable<String, Integer>();
numbers.put("one", 1);
numbers.put("two", 2);
numbers.put("three", 3);

Integer n = numbers.get("two");
if (n != null) {
 System.out.println("two = " + n);
}

 

• ConcurrentModificationException
  • Map에 들어간 element를 순회하기 전의 modCount와 순회한 뒤에 modCount가 같지 않으면 ConcurrentModificationException 를 발생시킨다.
  • (forEach 뿐만 아니라 Map Operation 곳곳에서 사용된다.)
• ConcurrentModificationException 의 경우는 Thread-safe 하지 않은 Collection을 병렬 쓰레드에서 사용할 경우 자주 마주칠 수 있으니, 사용하는 환경에 따라 Thread-safe 한 Collection을 꼭 골라 쓰도록 하자.

HashMap

• 아래 두가지가 HashTable과 가장 큰 차이이다.
  • key,value null을 허용한다.
  • Thread safe 하지 않다.(unsynchronized)
    • Collections.synchronizedMap . 지도에 대한 우발적인 동기화되지 않은 액세스를 방지하려면 생성 시 수행하는 것이 가장 좋습니다.
• 동시성, 병렬 로직을 사용하지 않는다면 HashMap 사용을 추천한다.
• 많은 양의 HashMap을 저장해야 한다면 자동으로 rehashing 되는 것보다, sufficiently large capacity를 만드는 것이 좀 더 효율적이다.
• 많은 key 값이 동일한 hashCode()를 가진다면 성능이 느려진다. Comparable인 경우 이 클래스는 키 간의 비교 순서를 사용하여 연결을 끊을 수 있습니다.
  • Comparable - 객체 스스로에게 부여하는 한 가지 기본 정렬 규칙을 설정하는 것이 목적이다.
  • Comparator - 기본 정렬 규칙과 다르게 원하는대로 정렬 기준을 지정하고 싶을 때(다른 정렬 기준을 사용하고 싶을 때) 사용한다.

 

출처 - 오라클 자바 공식문서

https://docs.oracle.com/javase/8/docs/api/java/util/Hashtable.html

연결리스트의 중간노드 찾기

 

    public class LinkedList {
    LinkedNode head;
    LinkedNode tail;
        public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();
        linkedList.add(new LinkedNode(1));
        linkedList.add(new LinkedNode(2));
        linkedList.add(new LinkedNode(3));
        linkedList.add(new LinkedNode(4));
        linkedList.add(new LinkedNode(5));

        linkedList.print();
        System.out.println(linkedList.getMidNode().number);

    }
        /**
         * 공간복잡도 : O(N)
         * 시간복잡도 : O(1)
         */
        private LinkedNode getMidNode(){
            LinkedNode fast = this.head;
            LinkedNode slow = this.head;
            while (fast != null && fast.next !=null){
                fast = fast.next.next;
                slow = slow.next;
            }
            return slow;
        }
    }

LRU 캐시

• Cache : 데이터나 값을 미리 복사해 놓는 임시 장소를 가리킨다. 캐시는 접근 시간에 비해 원래 데이터를 접근하는 시간이 오래 걸리는 경우나 값을 다시 계산하는 시간을 절약하고 싶은 경우 사용한다. 캐시에 데이터를 미리 복사해 놓으면 계산이나 접근 시간 없이 더 빠른 속도로 데이터에 접근할 수 있다.
• LRU Cache 기본 개념
  • LRU는 OS의 페이지 교체 알고리즘의 하나로 최근에 가장 오랫동안 사용하지 않은 페이지를 교체하는 기법이다. 캐시에 공간이 부족하면 가장 최근에 사용하지 않은 항목을 제거한다.
• LRU Cache 구현
  • LRU Cache 구현은 Double Linked List를 통해 구현한다. head에 가까운 데이터일수록 최근에 사용한 데이터이고, tail에 가까울수록 가장 오랫동안 사용하지 않는 데이터로 간주하여 새로운 데이터를 삽입할 때 가장 먼저 삭제되도록 한다.
  • 구현코드
    • https://github.com/haemanlee/java/blob/main/coding_study/whiteship/list/LRUCache.java

리소스 3일 경우

출처 : https://doublesprogramming.tistory.com/254