hash map # hash function # 충돌 hash collision

hash map이란?

  - hash table 이라고도 한다.

  - key, value 형태로 저장하는 자료구조

  - 하나의 key는 하나의 value에 맵핑

  - key는 uniqueness를 보장

 

특징

  - 삽입, 삭제, 갱신, 탐색이 '상수 시간'에 처리(된다는 장점이 있다. 데이터의 크기에 상관 없이) 

    Big O 표기법으로 표현시 O(1)   ( 데이터의 사이즈에 따라 결정된다면 O(n) )

 

  - 내부 구현

   배열(Array)로 구현

     배열은 index를 통해서 삭제, 구현, 탐색이 상수 시간대로 처리가 가능 

     배열로 구현한다는 것은 index를 이용한다는 것

   hash map은 key를 통해서 index에 접근. 어떻게? -> hash function

     hash function: key를 배열 크기 내의 index로 바꿔주는 함수

     -> hash function으로 key의 hash를 구함

     -> 구해진 hash를 배열 사이즈로 modular(%) 한 값을 index로 사용

 array[ hf(key) % M ] = value

           hf: hash function,

           M: hash_map size

      -> hash map 안에서 사용되는 hash function이 반환하는 데이터( hf(key) )의 타입 은 항상 정수타입이어야 한다.

 

- hash function을 어떻게 잘 짰느냐가 hash map에서 중요

  -> 충돌 가능성에 영향을 주기 때문

 

 

* hash 충돌

서로 다른 key들이 같은 hash를 가질 때 발생

  key1 != key2 -> hf(key1) == hf(key2)

 

hash map에서 또 다른 의미의 hash 충돌

  hf(key1) != hf(key2) -> hf(key1) % M == hf(key2) % M

 

왜 hash 충돌이 발생할까?

  - perfect hash function 구현의 어려움

    (perfect hash function: key1 != key2 -> hf(key1) != hf(key2) 을 보장하는 hash function)

  - key(input)의 사이즈에 비해 hash map(output)의 사이즈가 작기 때문

    -> input의 사이즈에 비해 output의 사이즈가 작기 때문

    - key 사이즈 만큼 hash map 사이즈를 잡는 것은 메모리를 너무 비효율적으로 사용하게 될 가능성이 크기 때문에

      보통 hash map 사이즈는 key 사이즈 보다 작게 설계