[자료구조] HashTable (HashMap, unordered_map(set))

김희성의 개발자 면접 cs 강의/ 스터디

 

 

 

HashTable (HashMap , unordered_map(set))

• java는 HashMap
• map: [key,value] 저장  / set : key만 저장   
• Map과 Set은 key가 중복되는 데이터는 저장 불가

• 비선형 자료구조
• 일정 크기의 배열(버킷) 생성 후 key값을 hash함수를 통해 배열의 index로 변환하여, 해당 index에 해당 key값과 value값 저장
• 시간 복잡도 
  • i번째 데이터에 접근(Access) : NONE / *O(N)  (순서라는게 없음)
  • X라는 데이터(Key)가 있는지 탐색 : O(1)
  • X라는 데이터(Key)에 접근(Access) : O(1)
  • X라는 데이터(Key)의 삽입/삭제 : O(1)
• Dictionary는 HashMap 으로 되어있다. (배열에 String이 들어갈 수 있음)
• List , linkedList , Array, Queue, Deque, Stack 은 시간복잡도가 다 O(N)이었다.

import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        HashMap<String, String> map = new HashMap<>();
        map.put("mmm", "0401");
        map.put("aaa", "0128");
        map.put("bbb", "0921");
        map.put("ccc", "1010");

        if (map.containsKey("mmm")) {  //O(1)
            System.out.printf(map.get("mmm")); // O(1)

        }
    }
}

 

 

• map.containsValue() 의 시간복잡도는 O(N)  - > value값은 hash를 하지않기 때문에 하나하나 찾아봐야한다.

import java.util.HashMap;

public class Main {

    private static final int MAX= 200_000;


    public static void main(String[] args) {
        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i =0; i<MAX; i++){ //O(N)
            map.put(i,i);  //O(1)
        }

        long start= System.currentTimeMillis();

        for(int i=0; i<MAX; i++){  //O(N^2)
            if(map.containsKey(MAX+1)){ //O(N)
                System.out.println("correct.");
            }
        }
        long end= System.currentTimeMillis();

        System.out.println((end - start)/1000.0 + "");

    }
}