Hash Table

Hash Table이란?

• hashing이란 기술을 사용해 key를 통해 value를 얻을 수 있는 자료 구조
• key는 hashable해야한다
  (== immutable한 data type이여야한다)

Hash Function이란?

• H(x) = key 'x'를 고정된 숫자 범위의 값으로 mapping 해주는 함수
• H(x) == H(y) 일경우 x와y가 다른 key일 수 있지만
  H(x) != H(y)인 경우 x 와 y는 항상 같은 key면 안된다.
• 이러한 성질을 이용해 object x,y를 비교 시 일단 hash 값을 비교 후 같은 hash 값을 가질 경우에 x,y를 명시적으로 비교한다.
• H(x) = y 이면 H(x)는 항상 y값이여야 한다. (determistic)
• hash collision(H(x) == H(y))이 최소한으로 발생하는 uniform hash function을 만들도록 노력해야한다

Hash Table 동작

• hash function을 indexing 방법으로 사용해 배열처럼 사용함
• 모든 동작(insert,delete,lookup)을 O(1)로 사용할 수 있어 매우 빠름
• 이를 얻기 위해선 좋은 uniform hash function을 사용해야 한다.
• hash collision이 발생하면 separate chaining 기법과 open addressing 기법을 사용한다(가장 많이 쓰이는 기법들)

Separate Chaining

• 같은 hash값 == 같은 index 란 뜻
  => LinkedList배열로 만들어 같은 hash 값일 경우 같은 index에 저장해 hash collision을 해결한다.
• 한 linkedlist에 많은 원소가 들어가면 O(1)으로 찾기 불가능 -> 많은 원소가 들어가면 해쉬 테이블 자체 크기를 키운 후 모든 key들을 재분배

Open Addressing

• 같은 hash값 == 같은 index 란 뜻
  => 같은 hash 값일 시 probing function을 사용해 새로운 hash값을 만들어 빈 배열 공간에 저장

• Separate Chaining과 다르게 한 공간에 하나의 value만 들어갈 수 있음

  • 해쉬 테이블 크기가 항상 들어간 원소 개수보다 커야함
  • 관리를 위해 LoadFactor 사용
  • LoadFactor = 아이템 수 / 테이블 크기
    => probing function 사용 시 배열의 size 보다 작은 범위로 cycle이 생기는 경우 존재
    => 그런 경우가 존재하지 않는 probing function 사용하여 해결

• Probing Function

  • linear probing function
    • P(x) = ax + b
    • cycle 문제 해결법: 배열의 크기와 a의 최대공약수가 1일 경우 배열 전체를 cycle 하여 해결할 수 있다.
      => P(x) = 1x 인 경우 언제나 최대공약수 1 이므로 자주 사용된다.
  • quadratic probing function
  • double hashing function