[DataStructure&Algorithm] HashMap

자료구조 및 알고리즘

---

개 요 - HashMap이란?

자바에서의 HashMap이란 Python의 Dictionary, JavaScript의 Json과 비슷한 형태로, Key와 Value가 한 쌍을 이뤄 저장되는 자료구조의 한 종류로 Map Interface를 상속받아 정의되어 있다.

Map Interface

 

HashMap에서 데이터를 저장할 때는, Key로 들어오는 데이터를 hash함수를 통해 해싱하고 해당 인덱스에 Value로 들어온 값을 저장하게된다.

 

데이터를 조회할때는 Key 값만을 넣어서 조회하는데, 이때도 들어온 Key 값을 해싱해서 해당 구조에서 데이터를 조회하기때문에 보다 빠르게 데이터를 조회할 수 있다.

---

특징

• Key,Value 구조로 이루어져있다.
• Key값은 중복이 안되며, Value 값은 같아도 Key값이 다르다면 중복이 가능하다.
• 해싱 특성상 조회나 삭제, 수정 속도가 빠르다.
• Map의 K,V는 모두 Primitive Type의 Wrapper Type만 대입이 가능하다
  • 어째서 그런 것인지는 잘 모르겠다.
• HashMap의 기본적인 capacity는 16, load factor는 0.75이다. arguments를 넣어줌으로써 변경가능하다.
• capacity는 원소의 최대 개수, load factor는 load factor * 100 % 이상일 때, 용량을 2배로 자동으로 늘린다.

 

---

선언 및 초기화

import java.util.HashMap;
class Main{
    public static void main(String[] args) {
        // 가장 기본적인 HashMap 생성
        HashMap<Integer,Integer> hashMap1 = new HashMap<>();

        // 초기 용량(capacity), load factor를 지정한 HashMap 생성
        // load factor? -> HashMap의 용량이 얼마나 차야 새로운 요소를 추가할 것인가를 결정하는 요소
        // load factor가 0.8이면, HashMap의 용량이 80% 이상 차면 용량을 두배로 늘린다.
        HashMap<Integer,Integer> hashMap2 = new HashMap<>(20,0.8f);

        // 초기 용량(capacity)을 지정한 HashMap 생성
        HashMap<Integer,Integer> hashMap3 = new HashMap<>(10);

        // 다른 Map을 복사한 HashMap 생성
        HashMap<Integer,Integer> hashMap4 = new HashMap<>(hashMap1);

    }
}

 

---

메서드

import java.util.HashMap;
class Main{
    public static void main(String[] args) {
        // 가장 기본적인 HashMap 생성
        HashMap<Integer,Integer> hashMap = new HashMap<>();
        
        // HashMap들의 메서드
        // put(key,value) : key와 value를 매핑
        hashMap.put(1,1);
        hashMap.put(2,2);
        hashMap.put(3,3);
        hashMap.put(4,4);
        hashMap.put(5,5);
        
        // get(key) : key에 해당하는 value를 반환
        System.out.println(hashMap.get(1)); // 1
        System.out.println(hashMap.get(2)); // 2
        System.out.println(hashMap.get(3)); // 3
        System.out.println(hashMap.get(4)); // 4
        System.out.println(hashMap.get(5)); // 5
        
        // remove(key) : key에 해당하는 value를 제거
        hashMap.remove(1);
        System.out.println(hashMap.get(1)); // null
        
        // size() : HashMap의 크기를 반환
        System.out.println(hashMap.size()); // 4
        
        // clear() : HashMap의 모든 요소를 제거
        hashMap.clear();
        System.out.println(hashMap.size()); // 0
        
        // isEmpty() : HashMap이 비어있는지 확인
        System.out.println(hashMap.isEmpty()); // true
        
        // containsKey(key) : key가 HashMap에 존재하는지 확인
        System.out.println(hashMap.containsKey(1)); // false
        
        // containsValue(value) : value가 HashMap에 존재하는지 확인
        System.out.println(hashMap.containsValue(2)); // false
        
        // keySet() : HashMap의 key들을 Set으로 반환
        System.out.println(hashMap.keySet()); // []
        
        // values() : HashMap의 value들을 Collection으로 반환
        System.out.println(hashMap.values()); // []
        
        // entrySet() : HashMap의 key와 value를 Map.Entry로 반환
        System.out.println(hashMap.entrySet()); // []
    }
}

---

응용

• Integer와 같은 Wrapper 뿐만 아니라 사용자 객체를 넣음으로써, 객체의 관리를 보다 용이하게 할 수 있다.
• 특정 객체의 호출 횟수를 업데이트하면서 알고리즘에 활용할 수 있다.
• 특정 지점을 지나갔는지(visited)와 같은 정보를 저장하여 true,false로 활용할 수 있다.