[자료구조] 자바 Map 총정리

Map이 잘 기억이 나지 않아 정리를 하려한다.

map은 key와 value로 쌍을 이룬다.

key 값은 중복 될 수 없지만 value는 중복이 가능하다.

주민등록번호는 중복되는 사람이 없지만 이름은 같은 사람을 떠올리면 쉽게 이해 할 수 있다.

Map 메소드 중 가장 많이 쓰이는 메소드는 put(), get(), remove()이다.

가장 많이 쓰이는 클래스는 HashMap, TreeMap, LinkedHashMap이다.

HashMap과 HashTable의 차이점은 아래와 같다.

기능	HashMap	HashTable
키, 값에 null 저장 가능 여부	O	X
여러 쓰레드 안전 여부	X	O

그래서 HashMap을 Thread safe하게 이용하려면

Map m = Collections.synchronizedMap(new HashMap(~));

이런 식으로 사용해야 한다고 한다. 

public static void main(String[] args) {
        //객체선언 Map<Object,Object> 형태로 객체를 선언한다
        Map<Integer, String> testMap = new HashMap<Integer, String>();
        
        //put을 사용해 데이터를 넣음
        testMap.put(1,"루피");
        testMap.put(2,"에이스");
        testMap.put(3,"사보");

        
        for(int i=1; i<=testMap.size(); i++){
            //get을 사용해 데이터를 꺼낸다.
            System.out.println(testMap.get(i));
        }

        //containsKey로 특정 키가 존재하는지 확인 할 수 있다.
        //true, false로 리턴해준다
        if(testMap.containsKey(1)) {
			System.out.println(testMap.containsKey(1));
	}
    }

HashMap 의 생성자에는 capacity와 load factor 가 있다.

- capacity == bucket의 크기

- 한 HashMap 객체에 저장된 데이터의 수 == capacity * load_factor

map을 별도의 설정을 하지 않으면 capacity == 16, load_factor == 0.75의 값을 가지고 bucket이라는 ArrayList가 만들어진다.

        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(16, 14);
        map.put(17, 3);
        map.put(34, 8);
        map.put(1, 9);
        map.put(36, 20);
        map.put(49, 25);
        map.put(18, 37);
        System.out.println("map = " + map);

예를들어 map에 위의 데이터가 들어있다고 가정했을 때

처음 16,14 데이터가 들어가면 map은

int index = key.hashCode() % capacity;

연산을 하게되는데 key는 Integer인 16이고, Integer 클래스의 hashCode()는 해당 int 값을 그대로 반환한다.

그렇게 index 값은 16 % 16 0으로 0번째 인덱스에 14의 값이 들어간다.

다음 17,3 데이터도 17%16으로 1번째 공간에 저장이 된다.

그런데 1,9 데이터도 1%16으로 1번째 공간에 저장이 되어야하는데 1번째 공간에는 이미 17,3의 값이 있다.

이럴 때는 17,3 데이터 앞에 1,9의 데이터를 저장하고 1,9 노드의 next값이 17,3 노드를 참조하도록 설정한다.

즉, LinkedList 형태로 노드가 저장된다.

이런 방식으로 데이터가 저장되는걸 Separate Chaining 이라고 한다.

데이터를 다 넣었다고 가정하고 get() 메소드를 사용할 때

get(17)을 실행하면 hashCode를 계산해 1번째 인덱스를 살펴보는데 2개 이상의 노드가 있으니,

첫번째 노드부터 시작해서 key값이 같은지 equals()로 비교한다. 

데이터가 적은 경우에는 문제가 되지않지만 데이터가 수백만개가 존재한다면 equals 연산이 엄청나게 실행되어야하고,

이는 성능 저하를 우려한다.

이를 방지하기 위해 HashMap은 자신의 capacity에 데이터 수가 차면 자동으로 bucket의 크기를 늘린다.

bucket의 크기를 늘리는 시점은

- load_factor == 저장된 데이터 수 / capacity 

가 되는 시점이다.

load factor가 작으면 그만큼 capacity가 커지므로 메모리는 많이 차지하지만, 검색 속도가 빨라진다.

load factor가 커지면 그만큼 capacity가 덜 커지므로 메모리는 적게 차지하지만, 검색 속도는 느려진다.

그래서 API에서 이상적인 값을 0.75라고 말하고 있다.

마지막으로 HashMap에 저장될 데이터 수가 짐작 가능하다면 capacity를 그 값에 맞게 설정해주는 것이 좋다.

그렇지 않으면 capacity가 자동으로 bucket을 늘리긴 하지만 늘리고 기존의 데이터 index값을 다시 계산하고 배치한다.

이 과정을 rehasing이라고 하는데 부하가 매우 크기때문에 초기 capacity 값을 설정해 주는 것이 매우 중요하다.

메소드 정리

• keySet() : key값만 모아 Set으로 리턴
• values() : value값만 모아 Collection으로 리턴
• Map.Entry 타입의 경우 getKey() 와 getValue()로 key와 value값을 리턴
• containsKey()와 containsValue()를 이용해 해당 값이 객체 안에 있는지 확인. 있으면 true, 없으면 false 리턴
• remove() : 삭제
• size() : map의 크기

TreeMap

HashMap은 데이터의 정렬을 할 수 없다.

하지만 TreeMap은 데이터의 key를 기준으로 정렬을 할 수 있다.

기준은 숫자 > 알파벳 대문자 > 소문자 > 한글 이다.

firstKey(), lastKey(), higherKey(), lowerKey() 메소드가 있다.

LinkedHashMap

HashMap의 경우 put을 통해 데이터나 객체를 넣을 때 key의 순서가 지켜지지 않는다는 단점이 있다.

testMap.put(1,"루피");

        testMap.put(2,"에이스");

        testMap.put(3,"사보");

이와 같이 넣었어도 실제 맵에서는 순서가 뒤죽박죽이다.

이를 해결하기 위해 LinkedHashMap이 나왔다.

put을 통해 입력된 순서대로 Key가 보장되므로 문제를 해결할 수 있고 사용방법은 HashMap과 동일하다.