11-46~47 HashMap(1)

HashMap과 Hashtable

• 순서 X, 중복(키X 값O)
• Map 인터페이스를 구현. 데이터를 키와 값의 쌍으로 저장
• HashMap(동기화 X)은 Hashtable(동기화 O)의 new 버전

HashMap

• Map 인터페이스를 구현한 대표적인 컬렉션 클래스
• 순서를 유지하려면, LinkedHashMap 클래스를 사용하면 된다.

TreeMap (TreeSet과 유사)

• 범위 검색과 정렬에 유리한 컬렉션 클래스
• HashMap보다 데이터 추가, 삭제에 시간이 더 걸림

HashMap의 키(key)와 값(value)

• 해싱(hashing)기법으로 데이터를 저장. 데이터가 많아도 검색이 빠르다.

해싱(hasing)

• 해시테이블은 배열(Array)과 Linked List가 조합된 형태
  
  1) 배열(Array) 장점 : index만 알면 데이터 접근(검색)을 빠르게 할 수 있다.
  2) Linked List 장점 : 데이터 변경이 쉽다
  Array와 Linked List의 장점을 결합 -> 데이터가 많아도 검색속도가 빠르다.

• 해시함수를 이용해서 데이터를 저장, 검색
  
  1) 키로 해시함수를 호출해서 해시코드를 얻는다.
  2) 해시코드(해시함수의 반환값)에 대응하는 Linked List를 배열에서 찾는다.
  3) Linked List에서 키와 일치하는 데이터를 찾는다.
  (※ 해시함수는 같은 키에 대해 항상 같은 해시코드를 반환해야 한다. 서로 다른 키일지라도 같은 값의 해시코드를 반환할 수 있다.)