[알고리즘 발표. 1620]

https://www.acmicpc.net/problem/1620

Given

1. 포켓몬의 개수 N
2. 문제의 개수 M
3. N 개 만큼의 포켓몬 이름

Then

1. M 개 줄에
   1. 케이스 1
      1. 입력 : 포켓몬 영어 이름
      2. 출력 : 포켓몬 번호
   2. 케이스 2
      1. 입력 : 포켓몬 번호
      2. 출력 : 포켓몬 영어 이름

예제입력

26 5
Bulbasaur
Ivysaur
Venusaur
Charmander
Charmeleon
Charizard
Squirtle
Wartortle
Blastoise
Caterpie
Metapod
Butterfree
Weedle
Kakuna
Beedrill
Pidgey
Pidgeotto
Pidgeot
Rattata
Raticate
Spearow
Fearow
Ekans
Arbok
Pikachu
Raichu
25
Raichu
3
Pidgey
Kakuna

예제 출력

Pikachu
26
Venusaur
16
14

자료구조 선택

해시 맵 구조

1. 해당하는 포켓몬을 선택시 최대한 빠르게 상수시간으로 조회가 가능해야한다.
2. N 은 1≤ N ≤ 100,000 이 조건이다.
   1. 만약 100000개의 포켓몬을 출력하는 경우
   2. 100,000 * 100,000 의 반복이 수행된다.

해법

1. 영어 포켓몬 이름과 숫자 번호를 둘다 상수시간에 저장해야한다.
2. 그냥 영어 포켓몬 이름과 숫자 카운트를 둘다 키값으로 저장해버리면된다.

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        Map<String, String> pokemons = new HashMap<>();
        
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int pokeNum = 1;
        
        while (N-- > 0) {
            String value = br.readLine();
            pokemons.put(String.valueOf(pokeNum), value);
            pokemons.put(value, String.valueOf(pokeNum));
            pokeNum++;
        }
        
        StringBuilder sb = new StringBuilder();
        
        while (M-- > 0) {
            String findValue = br.readLine();
            sb.append(pokemons.get(findValue)).append("\n");
        }
        
        System.out.println(sb);
    }
}

해시맵은 어떤식으로 내부에 자료를 저장하나?

1. 내부 배열 table ( 각 Node 가 하나의 버킷이 된다. )

   • transient Node<K,V>[] table;

   public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V> {
       // 핵심 데이터 구조: Node 배열
       transient Node<K,V>[] table;

   // Node 클래스 정의
   static class Node<K,V> implements Map.Entry<K,V> {
       final int hash;
       final K key;
       V value;
       Node<K,V> next;
   
       Node(int hash, K key, V value, Node<K,V> next) {
           this.hash = hash;
           this.key = key;
           this.value = value;
           this.next = next;
       }
   
       // ... 기타 메서드
   }

   • 하나의 버킷이다.
   • hash 는 키의 해시 값
   • Node<K,V> next; 를 통해
     • 다음 Node 의 참조를 저장한다.
     • 이를 통하여 링크드 리스트를 형성한다.

2. put 연산

   // putVal 메서드 (간략화)
   final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
       Node<K,V>[] tab; Node<K,V> p; int n, i;
       if ((tab = table) == null || (n = tab.length) == 0)
           n = (tab = resize()).length;
       if ((p = tab[i = (n - 1) & hash]) == null)
           tab[i] = newNode(hash, key, value, null);
       else {
           // 충돌 처리 로직...
       }
       // ... 기타 로직
       return null;
   }

   • tab 라는 Node 의 빈 자리에 새 노드를 생성한다.

   static final int hash(Object key) {
       int h;
       return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
   }

   • hash 값은 키값을 기준으로 생성된다.
   • hash 는 결국에는 언젠가는 겹칠 수 있게된다.

   해시 충돌이 나면 버킷을 링크드 리스트 나 트리 구조로 변경한다.

   • 해시 충돌은

     

     • 해시 함수가 존재하는 데, 해당 해시 함수는 언젠간 같은 해시값을 뱉어낼 수 있음.

   Node 의 next 변수가 다음 리스트의 주소를 가지고 있기에, 해당 구조는 링크드 리스트이며,
   만약 
   
   for (int binCount = 0; ; ++binCount) {
       if ((e = p.next) == null) {
           p.next = newNode(hash, key, value, null);
           if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
               treeifyBin(tab, hash);
           break;
       }
       if (e.hash == hash &&
           ((k = e.key) == key || (key != null && key.equals(k))))
           break;
       p = e;
   }

   • 버킷안의 노드를 순회
   • *TREEIFY_THRESHOLD 이상의 노드가 존재하면 ⇒ 자바11 기준 8개*

     • 버킷안의 노드를

       final void treeifyBin(Node<K,V>[] tab, int hash) {
           int n, index; Node<K,V> e;
           if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
               resize();
           else if ((e = tab[index = (n - 1) & hash]) != null) {
               TreeNode<K,V> hd = null, tl = null;
               do {
                   TreeNode<K,V> p = replacementTreeNode(e, null);
                   if (tl == null)
                       hd = p;
                   else {
                       p.prev = tl;
                       tl.next = p;
                   }
                   tl = p;
               } while ((e = e.next) != null);
               if ((tab[index] = hd) != null)
                   hd.treeify(tab);
           }
       }

     • TreeNode 트리구조로 내부 노드를 변경한다.

3. get

   // get 메서드
   public V get(Object key) {
       Node<K,V> e;
       return (e = getNode(hash(key), key)) == null ? null : e.value;
   }

   • 키값의 해시값을 통해 해당 Node 의 밸류를 반환한다.