HashMap이란 무엇인가?

HashMap이란?

• 정의 : HashMap은 키(Key)와 값(Value) 두 쌍으로 데이터를 보관하는 자료구조인 Map 인터페이스의 구현체로 키를 해싱하여 사용하는 자료구조 이다.

---

HashMap의 특징

• 데이터 저장할 때는 키(key)값을 해싱하여 저장위치를 결정하여 값(value)을 저장한다.

• 특정 데이터의 저장 위치를 해시함수를 통해 알 수 있어 데이터의 추가,삭제,검색이 빠르다

• Map 내부의 키(key)의 중복은 불가능 하지만 값(value)의 중복은 가능 하다.

• Thread Safe 하지 않기 때문에 동시에 여러 쓰레드가 접근할 경우에 외부에서 synchronized 처리가 필요하다.

---

HashMap은 왜 사용하는가?

HashMap을 사용하는 이유는

• key - value 쌍으로 데이터를 저장
  ⇒ 선형자료형과 같이 [1,2,3]이 아닌 key - value쌍 형식으로 저장하고 싶을때 사용한다.

• 성능
  ⇒ HashMap은 Hash Function을 이용하여 데이터를 삽입 검색 하기 때문에 시간복잡도 O(1)이라는 이점을 가지고 있어 사용한다.

---

HashMap vs HashTable

• HashMap vs HashTable

  HashMap과 HashTable은 Java의 API 이름이다.

  • HashTable이란 JDK 1.0부터 있던 Java의 API이고, HashMap은 Java 2에서 처음 선보인 Java Collections Framework에 속한 API다.

  • HashTable 또한 Map 인터페이스를 구현하고 있기 때문에 HashMap과 HashTable이 제공하는 기능은 같다.

    ⇒ 다만 HashMap은 보조 해시 함수(Additional Hash Function)를 사용하기 때문에 보조 해시 함수를 사용하지 않는 HashTable에 비하여 해시 충돌(hash collision)이 덜 발생할 수 있어 상대으로 성능상 이점이 있다.

    ⇒ 보조 해시 함수가 아니더라도, HashTable 구현에는 거의 변화가 없는 반면, HashMap은 지속적으로 개선되고 있다.

    ⇒ HashTable의 현재 가치는 JRE 1.0, JRE 1.1 환경을 대상으로 구현한 Java 애플리케이션이 잘 동작할 수 있도록 하위 호환성을 제공하는 것에 있기 때문에, 이 둘 사이에 성능과 기능을 비교하는 것은 큰 의미가 없다고 할 수 있다.

• HashMap과 HashTable 클래스의 차이점

  	HashTable	HashMap
  동기화 고려	O	X
  Null 허용	X	O

  • Thread-safe 여부
    ⇒ Hashtable은 Thread-safe하고, HashMap은 Thread-safe하지 않다는 특징을 가지고 있다 그렇기에 멀티스레드 환경이 아니라면 Hashtable은 HashMap 보다 성능이 떨어진다는 단점을 가지고 있다.

  • Null 값 허용 여부
    ⇒ Hashtable은 key에 null을 허용하지 않지만, HashMap은 key에 null을 허용한다.

  • 성능상 이점
    ⇒ HashMap은 보조해시를 사용하기 때문에 보조 해시 함수를 사용하지 않는 Hashtable에 비하여 해시 충돌(hash collision)이 덜 발생할 수 있어 상대적으로 성능상 이점이 있다.

  최근까지 Hashtable은 구현에 거의 변화가 없지만, HashMap은 현재까지도 지속적으로 개선되고 있다.

---

HashMap의 Collision

충돌(collision)이란 서로 다른 문자열이 해시 함수를 통하여 해싱한 해시값이 중복인 경우를 말한다.

충돌이 많아질수록 탐색의 시간 복잡도가 O(1)에서 -> O(n) 에 가까워지기 때문에 HashMap의 이점을 잃어버리지 않기 위한 해결할 방안이 필요하다.

• 충돌이 적게 나는 해시함수를 사용

• 충돌 발생시 충돌에 대한 해결방안 사용

  • Separating Chaining 동일 해시값이 있을 경우 Liked List 혹은 Red-Black tree를 통해 쇠사슬 모양으로 연결하여 관리하는 방법

    • 장점

      • 항목을 탐색하거나 저장, 삭제하고자 하면, 계산한 해시 주소에 해당하는 연결 리스트에서 독립적으로 수행하기 때문에, 오버 플로우가 발생해도 수행 시간 면에서 효율적이다.
      • 연결 리스트로 구현하기 때문에 메모리 낭비도 없다.

    • 단점

      • 해시 함수의 퀄리티에 따라서 한 주소에 쏠림 현상이 발생할 수 있다.
        
        

  • Open addressing 데이터를 삽입하려는 버킷이 사용중이면 다른 비어 있는 버킷을 찾아 삽입하는 방법

  • 재해싱 종류

    • 선형 탐색(Linear Probing):** 해시충돌 시 다음 버켓, 혹은 몇 개를 건너뛰어 데이터를 삽입한다.
    • 제곱 탐색(Quadratic Probing):** 해시충돌 시 제곱만큼 건너뛴 버켓에 데이터를 삽입(1,4,9,16..)
    • 이중 해시(Double Hashing):** 해시충돌 시 다른 해시함수를 한 번 더 적용한 결과를 이용함.

  • 장점

    • 체이닝처럼 포인터가 필요 없고, 지정한 메모리 외에 추가적인 공간이 필요 없다.
    • 삽입 삭제시 오버헤드가 적다.

  • 단점

    • 최악의 경우 비어있는 버킷을 찾지 못하고 탐색을 시작한 위치까지 되돌아 올 수 있다.
    • 특정 위치에만 데이터가 몰리는 현상이 나타날 수 있다.

---

Java의 HashMap 사용

• HashMap 선언

      //HashMap생성	
      HashMap<String,String> map1 = new HashMap<String,String>();
  
      //new에서 타입 제너릭 생략가능
      HashMap<String,String> map2 = new HashMap<>();
  
      //초기 용량 지정
      HashMap<String,String> map4 = new HashMap<>(10);
  
      // 초기값 지정
      HashMap<String,String> map6 = new HashMap<String,String>(){{
        put("a","b");
    }};

• 주요 메소드

  메소드	설명
  containsKey(Object key)	지정된 key가 포함되어 있는지 여부를 반환한다.
  containsValue(Object value)	지정된 value가 포함되어 있는지 여부를 반환한다.
  entrySet()	저장된 키와 값을 엔트리(키와 값의 결합)의 형태로 Set에 저장하여 반환한다.
  keySet()	저장된 모든 key를 Set에 저장하여 반환한다.
  clear()	저장된 모든 객체(key, value)를 제거한다.
  remove(Object key)	지정된 key에 해당하는 value를 제거한다.
  getOrDefault(Object key, Object defaultValue)	지정된 키의 값을 반환한다. 키가 없을 경우, default Value로 지정된 데이터를 반환한다.
  putAll(Map map)	Map에 저장된 모든 요소를 HashMap에 저장한다.
  replace(Object key, Object value)	지정된 키의 값을 지정된 value로 대체한다.
  replace(Object key, Object oldValue, Object newValue)	지정된 키와 값(oldValue)가 모두 일치하는 경우에만 새로운 값으로 대체하며, 일치 여부를 반환한다.

---

HashMap의 시간복잡도

get           : O(1)
containsKey   : O(1)
put			  : O(1)
remove		  : O(1)
next          : O(h/n) h는 테이블 용량