HashMap & Hashtable

• 순서 X, 중복(키 X, 값 O)

• Map 인터페이스를 구현. 데이터를 키-값 쌍으로 저장

• Hashtable : 구버전 (동기화 O)

HashMap : 신버전 (동기화 X)

• Map 인터페이스를 구현한 대표적 컬렉션 클래스

• 순서를 유지하고 싶으면, LinkedHashMap 사용

• 해싱(Hashing) 기법으로 데이터를 저장하기 때문에, 데이터가 많아도 검색이 빠르다.

• key-value pair : key는 중복 X, value는 중복 O

public class HashMap extends AbstractMap
					implements Map, Cloneable, Serializable {
    transient Entry[] table;	// 배열. Entry = key-value pair
    ...
    static class Entry implements Map.Entry {
    	final Object key;
        Object value;
    }
}

TreeMap : TreeSet과 같은 특성 (이진 탐색 트리)

• 범위 검색과 정렬에 유리한 컬렉션 클래스

• HashMap보다 데이터 추가/삭제에 더 많은 시간이 걸림 (비교 후 저장하기 때문)

해싱(Hasing)

• 에드위드 부스트코스 정리본 참고

• key -> 해쉬 함수 (hash function) -> index 반환(저장위치. 이를 해시코드라고 함)

• 해싱이란? 해쉬함수를 이용해서, 해시 테이블(hash table)에 데이터를 저장하고, 읽어오는 것이다.

• 해시 테이블이란? 배열(Array)과 링크드 리스트(LinkedList)가 조합된 형태이다.

  Hashtable = {LinkedList1, LinkedList2, LinkedList3, LinkedList4 ...};

  배열의 장점인 "접근성" + 링크드리스트 장점인 "변경 유리" = Hashtable

• hashCode()를 사용하는 함수 : Hashtable, HashMap, HashSet

  -> Objects.hash() 를 이용해서 작성.
  

• Hashtable에 저장된 데이터를 가져오는 과정

  1. key로 해시함수를 호출하여, HashCode(배열의 index)를 얻는다.
  2. HashCode에 대응하는 LinkedList를 배열에서 찾는다.
  3. LinkedList에서 key와 일치하는 데이터를 찾는다.

• 해시 함수는, "같은 key"에 대해, "항상 같은 해시코드"를 반환해야 한다.

  서로 다른 key 일지라도, 같은 값의 해시코드를 반환할 수 있다. (같은 LinkedList에 존재한다.)