Java 자료구조 - 해시맵 (HashMap)

HashMap

• 키(key)와 값(value)을 묶어서 하나의 데이터로 저장한다.
• 해싱(hashing)을 사용해서 많은 양의 데이터를 검색하는데 뛰어난 성능을 보인다.
• key는 중복을 허용하지 않는다. 중복된 키가 있을경우 값은 덮어씌워진다.
• Map<String,Integer> map = new HashMap<>();로 객체 생성하여 사용한다.
  

Hashing

• 해시함수를 이용해서 데이터를 해시테이블(hash table)에 저장 후 검색하는 기법
• 가능하면 Hashtable대신 HashMap을 사용하는게 좋다.

HashMap 기본연산

• put (데이터 추가)
  map.put(key,value)로 데이터 추가

• remove (값 1개 제거)
  map.remove(key)로 키값을 이용해 제거

• clear (모든 값 제거)
  map.clear()로 전체 값 제거

• get (값 가져오기)
  map.get(key)로 key에 해당하는 value값 가져오기

• containsKey
  map.containsKey(key)로 Map에 해당 key가 있는지 조사해서 true나 false 리턴

• size
  map.size()로 Map의 갯수 리턴

HashMap 시간복잡도

O(1) or O(N)
각 key값은 고유한 index를 가져 바로 접근할 수 있으므로 평균 O(1)이지만
데이터 충돌이 발생한 경우 연결된 리스트들까지 검색을 해야하므로 O(N)까지 증가할 수 있다.