HashTable

해시충돌

• 여러 개의 key가 같은 hash를 가질 때
  • 비둘기 집의 원리
  • key1 - hash1, key2 - hash1
• 최악의 경우 검색 O(n)

해시충돌 해결 방법

Chaining

충돌이 발생하면 각 데이터를 해당 주소에 있는 링크드 리스트에 삽입하여 문제를 해결하는 방법

• JDK에서 채택
• Linked List(데이터 6개 이하) 또는 Red-Black Tree(데이터 8개 이상) 사용
• 추가적인 메모리 필요하다.

개방주소법

해시 충돌 시 새로운 주소를 찾는 방법

• 선형 탐사
  
  hash 충돌 시, n칸씩 뒤에 넣기
  cluster 발생 (데이터 뭉쳐있는 현상) 가능

• 제곱 탐사
  

• 이중 해싱
  
  해시 함수를 2개 사용
  1개는 key값 찾는데 사용, 나머지 1개는 해시 충돌시 사용

HashTable과 HashMap

• HashTable
  • 동기화
    • 멀티 스레드 환경에서 안전하다. but 상대적으로 느리다.
  • key에 null값 허용
• HashMap
  • 동기화x
    • 멀티 스레드 환경에서 주의 필요 - ConcurrentHashMap
  • key에 null 허용X

Map의 종류

• HashMap

  • Key를 저장할 때 hash(key)로 저장한다.
  • 저장 순서를 알 수 없다.

• LinkedHashMap

  • Key를 저장할 때 hash(key)로 저장한다.
  • 저장 순서를 알 수 있다.
    • HashMap에 before, after

    static class Entry<K,V> extends HashMap.Node<K,V> {
      Entry<K,V> before, after;
      Entry(int hash, K key, V value, Node<K,V> next) {
          super(hash, key, value, next);
      }
  }

  • add가 HashMap과 마찬가지로 O(1)이지만 before,after를 추가적으로 관리하는 비용이 들어간다.
  • LinkedList로 저장되었다는 글이 많던데 코드 다시 확인해보기!

• TreeMap

  • 정렬하는 Map
  • Key를 저장할 때 hash(key)로 hashcode를 이용하지 않는다.
  • 접근: O(logN) Red Black Tree라서