[자료구조](19)[해시 테이블]

 

해시 테이블

Map을 구현하는 방법 중 하나
구성 요소

• 해시 함수
• bucket: 자료가 저장되는 배열

 

데이터 관리

 

insert

key를 해시 함수에 넣고 -> mod 연산을 한 뒤 -> 그 값을 인덱스로 사용해 자료, 해시값을 저장
예) 크기가 8인 버킷에 (value = 'abc', key = 9)인 데이터를 저장하고 싶다면
    1. 해시함수에 9를 넣어 hash = 14라는 값이 나왔다고 하자.
    2. 14 ≡ 6 (mod 8) 이므로 인덱스는 6이다
    3. 해당 인덱스에 key, value, hash를 저장한다

 

collision handling

인덱스가 중복되는 충돌이 발생하는 경우

• 경우 1: 같은 해시 값이 나왔을 때
• 경우 2: 다른 해시 값이지만 mod 연산에서 인덱스가 같을 때
  
  충돌을 처리하는 방법
• chaining: 연결 리스트로 해당 인덱스 값 뒤에 붙이기
  예) 인덱스 5에 이미 abc가 들어있는 상태에서 인덱스가 5인 rerere를 또 집어넣고 싶을 때

       ...
    4 | fdsfs
    5 | abc -> rerere
    6 | 
       ...

  로 처리하면 된다.
• open addressing: 빈 곳에 넣어주기
  빈 곳을 찾는 것도 여러 방법이 있는데
      linear probing: 한칸씩 내려가며 빈 공간 찾기
      quadratic probing: 제곱만큼 건너뛰며 빈 공간 찾기
          -> linear은 특정 인덱스 주위에 자료가 많이 몰리는 clustering이 발생 가능 따라서 quadratic으로 '그나마' 낫게 한다.
      double hashing: 인덱스에 또 해시, mod연산을 해 새로운 인덱스로 만들고 비어있는지 확인
  물론 이 경우엔 해시 연산으로 얻은 인덱스 값과 완전 딴판이 되므로 탐색에 더 시간이 들 수 있다.
  예) linear probing으로 open addressing을 할 때

    인덱스 5에 이미 abc가 들어있는 상태에서 인덱스가 5인 rerere를 또 집어넣고 싶을 때
    ```
        ...
    4 | fdsfs
    5 | abc
    6 | rerere
       ...
    ```
    가 된다.

 

rehashing

bucket에 데이터가 70% 이상 찬다면 인덱스끼리 충돌이 날 위험이 크므로
기존보다 더 큰 bucket을 잡고 그 버킷으로 기존의 버킷에 있는 데이터를 옮겨준다.
이때 다시 인덱스 계산을 해야 한다.
    다시 해시함수부터 돌리면 비용이 많이 드니
    미리 저장해놨던 hash를 불러와 mod new_bucket 으로 인덱스를 빠르게 계산한다.
예) (value = 'abc', key = 9, hash = 14)인 데이터를 크기가 19인 버킷에 rehashing하고 싶다면
    hash ≡ 14 (mod 19)이므로
    인덱스 14에 (value = 'abc', key = 9, hash = 14)를 저장하면 된다.

 

remove

key를 연산을 통해 인덱스로 바꾸고
거기에 있는 값이 지울 값과 같은지 비교 후
    (충돌로 인해 그 자리에 있는 값이 꼭 지울 값이란 보장이 없음)
지운다.

 

시간복잡도

최선	평균	최악
O(1)	O(1)	O(n)

최선, 평균 O(1)의 시간복잡도를 지님
-> (N에 상관 없이) 충돌이 없는 대부분의 경우 key를 연산만 하면 바로 인덱스를 찾을 수 있기 때문!
최악일땐 O(n)의 시간복잡도를 지님
-> 한 인덱스에 충돌이 너무 발생해 충돌 처리에서
    chaining일땐 연결 리스트마냥 될 수도 있고
    open addressing에서도 아래로 계속 해당 값을 찾으러 내려가며 탐색해야 하니
O(n)의 시간복잡도를 갖게 된다.
(물론, key로 찾을 때 이렇다는 거지 value 기준으로 찾게 되면 모두 O(n)이다.)

 

get

key를 연산을 통해 인덱스로 바꾸고
거기에 있는 값이 찾는 값과 같은지 비교 후
    (충돌로 인해 그 자리에 있는 값이 꼭 찾는 값이란 보장이 없음)
있으면 반환,
없으면 끝까지 찾아봐야 함...
    chaining일땐 연결 리스트의 끝까지 찾아보고
    open addressing에선 비어있는 공간이 나올 때까지 찾기

 

시간복잡도 <- remove와 동일

최선	평균	최악
O(1)	O(1)	O(n)

최선, 평균 O(1)의 시간복잡도를 지님
-> (N에 상관 없이) 충돌이 없는 대부분의 경우 key를 연산만 하면 바로 인덱스를 찾을 수 있기 때문!
최악일땐 O(n)의 시간복잡도를 지님
-> 한 인덱스에 충돌이 너무 발생해 충돌 처리에서
    chaining일땐 연결 리스트마냥 될 수도 있고
    open addressing에서도 아래로 계속 해당 값을 찾으러 내려가며 탐색해야 하니
O(n)의 시간복잡도를 갖게 된다.
(물론, key로 찾을 때 이렇다는 거지 value 기준으로 찾게 되면 모두 O(n)이다.)