해시 테이블

해시 테이블

데이터를 ‘key’ 와 ‘value’로 저장하는 방식의 자료구조 이며
key 값을 ‘hash 함수’에 넣어 나온 ‘해시값’을 이용해
value를 특정한 위치를 저장한다

Key : 값(value)의 위치를 나타내는 데이터
Value : 실제 저장하는 데이터

이후 ‘값’을 찾을 땐,
다시 ‘key’를 ‘hash 함수’에 넣은
해시값으로 해당 위치의 value를 가져오는 방식

• 해시함수?
  

  ‘임의의 크기를 가진 데이터’를 ‘고정 크기’의
  값에 대응하게 하는 함수
  (함수 이므로 ‘입력값’이 같으면 ‘출력값’이 같다)
  

• 해시충돌?
  

  ‘함수’는 입력값이 달라도 출력값은 같을 수 있기에
  발생하는 현상이며, 이 현상을 방지할수록
  좋은 해시 함수로 평가된다
  (굳이 ‘key’를 따로 저장안하고
  해시값(int)만 들고 있으면 되므로)

C#, Python에선 ‘딕셔너리(Dictionary)’로 표현

해시 테이블의 시간 복잡도

검색, 삽입, 삭제 (평균) : 모두 O(1)!!
(다만 최악의 경우 O(n))

• 전부 O(1)이 되려면 어떻게 해야 하지??
  =>자료가 위치한 곳을 ‘알고 있다’면 가능

해시 테이블의 용도

빠르게 ‘데이터’를 읽어올 필요가 있는 경우 유용

‘해시 충돌’이 발생하지 않는 조건이라면,
사용하지 않을 이유가 없다

미리 기존에 hash Table로 만들어둔 경우라면
데이터 파일을 O(1)으로 읽어올 수 있음!!
(개발 도중 해시 충돌이 없다는 것이 확인이 되었으므로)

(ex : 게임에서 특정 아이템의 강화 확률 원본)

해시 충돌 시, ‘해시 테이블’의 충돌 해결방식

1. 분리 연결법(Separate Chaning)
   
   겹치는 요소를 관리할 자료구조를 활용,
   추가적인 메모리를 사용해, 값이 겹치는 경우
   해당하는 자료구조에 값을 넣어 관리한다
   
   

   테이블 자체에 대한 확장이 필요없으며,
   구현이 손쉽다는 장점이 있으나,
   충돌이 많아질수록 ‘선형’의 자료구조를
   탐색하는 것과 동일한 시간복잡도를 가지게 된다

2. 개방 주소법(Open Addressing)
   
   비어있는 ‘해시테이블’ 공간을 활용하는 방법
   겹친 공간이 아닌 ‘특정할 수 있는 다른’ 곳에
   데이터를 저장하는 방식이며,
   일정한 간격만큼 이동하는 Linear probing,
   순서 폭을 제곱으로 이동하는 Quadratic probing
   등이 존재한다

   다만, 해시 테이블 에서 ‘Data’를 삭제하는 경우
   데이터를 찾다 ‘쓰레기값’을 주워올 수 있기에
   Hash Table의 재정렬이 필요하다

• 다만 결국 이러한 ‘처리 방식’을 사용해도
  해쉬의 충돌이 발생할 수록,
  해쉬 테이블의 성능이 저하되는 점을 인식해야 한다.

이미지 출처

[출처] : https://mangkyu.tistory.com/102