TIL45. 자료구조-해시

김정현·2021년 5월 8일
0
post-thumbnail

해시테이블 이란?


해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 색인 또는 주소 삼아 데이터(value)key와 함께 저장하는 자료구조이다.

연관배열 구조: key와 value가 1:1로 연관되어있는 자료구조. key를 이용해 value를 알아낼 수 있다.


해시테이블 구성

  • key

    • 고유한 값, hash function의 input이 된다.
    • 키값 그대로 저장소에 저장할 경우 다양한 키의 길이 만큼의 크기를 구성해두어야 하기 때문에 일정한 길이의 해시로 변경한다.
  • hash function

    • key를 고정된 길이hash로 변경해주는 역할을 한다. 이 과정을 hashing이라고 한다.
    • 서로 다른 key가 같은 hash값을 갖게 되는 경우 이를 해시 충돌 이라고 한다. 해시 충돌 발생 확률이 적을 수록 좋다.
    • 해시충돌이 해시값 전체에 걸쳐 균등하게 발생하도록 하는 것도 중요하다. 모든 키가 02라는 동일한 해시값으로 매핑이 될 경우 데이터를 액세스할 때 비효율성이 커지고, 보안이 취약(서로 다른 키인데도 동일한 해시값)해져 굳이 해시를 도입해 데이터를 관리할 이유가 없어진다.
  • value

    • 저장소(bucket, slot)에 최종적으로 저장되는 값으로, hash와 매칭되어 저장.
  • hash table

    • 해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 색인 또는 주소 삼아 데이터(value)를 key와 함께 저장하는 자료구조
    • 데이터가 저장되는 곳을 버킷 또는 슬롯이라고 한다.
    • 해시 테이블의 기본 연산은 삽입, 삭제, 탐색이다.


해쉬테이블 장단점은?

<장점>
해시테이블은 key-value가 1:1로 매핑되어 있기 때문에 삽입, 삭제, 검색의 과정에서 모두 평균적으로 O(1)의 시간복잡도를 가지고 있다.

<단점>

  • 해시 충돌이 발생
  • 순서/관계가 있는 배열에는 어울리지 않는다 => 순서에 상관없이 key만을 가지고 삽입, 검색, 삭제하기 때문
  • 공간 효율성이 떨어짐 => 데이터가 저장되기 전에 미리 저장공간을 확보해야하기 때문. 공간이 부족하거나 아예 채워지지 않은 경우가 발생
  • hash function의 의존도가 높다 => 평균 시간복잡도가 O(1)이지만 해시함수가 매우 복잡하다면 해시테이블의 연산 속도는 증가



해쉬 충돌

  • 서로 다른 값을 가진 key가 해시 테이블의 한 주소에 매핑되는 경우이다.
  • hashing을 해서 삽입하려 했으나 이미 다른 원소가 자리를 차지 하고 있는 상황.

이럴 경우, 해싱의 검출 속도를 떨어뜨리고 버킷 크기를 넘어 저장되어 오버 플로우가 발생한다.


해쉬 충돌 해결 방안

1. 열린 어드레싱 방법 (Open Addressing Method)

  • 선형 조사 : 충돌이 일어난 바로 뒷 자리로 값을 넣어준다.

-계산이 단순하다는 장점.
-검색에 시간이 많이 소요된다.
-테이블 내에 데이터들이 특정 영역에 값이 몰리는 현상이 발생한다.


  • 이차 조사법 : 충돌이 일어나면 2차 방정식을 이용해서 위치를 구해 값을 넣어준다.

-선형 조사법이 n칸 옆을 검사한다면 이차 조사법은 n^2 칸 옆을 검사한다.
-특정 영역에 값이 몰려도 그 영역을 빨리 벗어 날 수 있지만, 여러 개의 원소가 같은 초기 해쉬 값을 갖게 되면 모두 같은 순서로 조사할 수 밖에 없다.


  • 이중 해싱 : 두 개의 함수를 이용하여 하나의 함수는 최초 해시값을 구하고 다른 함수는 해시 충돌이 일어났을 경우 이동할 폭을 구할때 사용한다.


2. 닫힌 어드레싱 방법(Closed Addressing Method)

  • 체이닝 : 해시 테이블 자체는 포인터 배열로 만들고 같은 버켓의 해당하는 데이터들을 체인 형식으로 만들어(링크드 리스트) 연결하는 방식.

    이런 경우, 삽입,삭제가 용이하지만 따로 동적인 공간을 할당해야 하는 문제가 발생한다.

0개의 댓글