1. 개념

• 해시 함수를 사용하여 키를 해시 값으로 매핑하고, 이 해시값을 index 삼아 데이터의 값(value)를 키와 함께 저장하는 자료구조이다.

  • 데이터가 저장되는 곳을 버킷 또는 슬롯 이라고 한다.
    

• HashMap은 키와 값을 저장하는 자료구조로, 빠른 검색 및 삽입 속도를 제공하는 매우 유용한 자료구조이다.

• HashMap은 키-값 쌍으로 이루어진 매핑을 저장하는데 사용된다. 각 키는 유일하며, 값은 중복될 수 있다. HashMap은 Map 인터페이스를 구현하므로, 키와 값의 형식은 일반적으로 제네릭 타입으로 정의 된다.

• HashMap은 내부적으로 해시 테이블을 사용하여 구현된다. 해시 테이블은 배열과 링크드 리스트를 조합하여 구현된다. 배열의 인덱스는 해시 함수를 사용하여 결정되며, 각 인덱스는 연결 리스트로 구성된다. 이것은 해시 충돌을 처리하기 위한 것이다. 해시 충돌이 발생하면, 새로운 항목은 해당 인덱스의 연결 리스트에 추가된다.

2. 메소드

• boolean containsKey(Object key) : HashMap에 저장된 키(key)가 포함되었눈지 알려준다. (포함되어 있으면 true)
• Object get(Object key) : 지정된 키(key의 값(객체)을 반환, 못찾으면 null 반환
• Object getOrDefault(Object key, Object defaultValue) : 지정된 키(key)의 값(객체)을 반환한다. 키를 못찾으면, 기본 값(defaultValue)로 지정된 객체를 반환
• boolean isEmpty() : HashMap이 비어있는지 알려준다.
• Set keySet() : HashMap에 저장된 모든 키가 저장된 Set을 반환
• Object put(Object key, Object value) : 지정된 키와 값을 HashMap에 저장
• Object remove(Object key) : HashMap에 지정된 키로 저장된 값(객체)를 제거
• int size() : 저장된 객체의 개수를 반환한다.

3. 시간 복잡도

• 삽입 (put) : O(1) (평균)
• 탐색 (get) : O(1) (평균)
• 삭제 (remove) : O(1) (평균)
• 크기 (size) : O(1)
  • HashMap은 내부적으로 해시 테이블을 사용하여 키-값 쌍을 저장하므로, 키의 해시 코드를 계산하여 이를 이용해 저장 및 검색 작업을 수행한다. 평균적으로 해시 테이블에서 데이터를 찾는 시간은 O(1)이므로, HashMap의 삽입, 탐색, 삭제 작업은 평균적으로 상수 시간에 수행된다.
  • 하지만, 해시 충돌이 발생하는 경우 평균 시간 복잡도보다 더 오랜 시간이 걸릴 수 있다. 이러한 경우에도 HashMap은 O(N)보다는 효율적이다.
  • 또한, HashMap의 크기를 반환하는 size() 메서드는 해시 테이블에 저장된 원소의 수를 반환하기 때문에 O(1)의 시간 복잡도를 갖는다.

4.Direct-address table

• 키의 전체 개수와 동일한 크기의 버킷을 가진 해시테이블이다.
• Direct-address table의 장점은 키 개수와 해시테이블 크기가 동일하기 때문에 해시충돌 문제가 발생하지 않는다는 것이다. 하지만 전체 키 중 실제 사용되는 키의 개수가 적을 경우 메모리 효율성이 크게 떨어진다. 대표적인것이 배열 인덱스를 키로 사용하는 방법이다.
• 이를 개선하고자 HashMap을 사용한다.