Hash

류지수·2022년 12월 11일
0

[자료구조] Hash

[ Hash Table 이란? ]

key-value로 이루어진 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조

해시 테이블이 빠른 검색 속도를 제공하는 이유 -> 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문.

해시 테이블은 각각의 Key값이 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 됨.

(여기서 실제값이 저장된느 장소 -> bucket 또는 slot)
key는 hash 함수를 통해 hash로 변경이 되며 (이 과정을 Hashing이라고 함) hash는 value와 매칭되어 저장소에 저장됨.

< 예시 >
Sandra Dee라는 사람의 전화번호를 찾는 과정이라면,
해시함수(Hash Function)의 입력값은 "Sandra Dee"이고 출력값은 "14"이다.
그리고 index가 "14"인 bucket에서 "521-9655"를 찾는다.

< Hash Table Data Structure >

  • key : 고유한 값이며, 해시 함수의 input이 됨. 최종 저상소에 저장되면 다양한 길이 만큼의 저장소를 구성해 두어야 하기 때문에 해시 함수로 값을 바꾸어 저장이 되어야 공간의 효율성을 추구할 수 있음.
  • 해시함수 : key를 hash로 바꿔주는 역할. 다양한 길이를 가지고 있는 key를 일정한 길이를 가지는 hash로 변경하여 저장소를 효율적으로 운영할 수 있도록 도와줌.

    단, 서로 다른 key가 같은 hash가 되는 경우 해시충돌(Hash Colllision)이라고 한다. -> 충돌을 일으키는 확률을 최대한 줄이는 함수를 만드는 것이 중요!!
  • 해시(Hash) : Hash Function의 결과물, 저장소(buckey, slot)에서 값(value)과 매칭되어 저장됨.
  • 값(Value) : 저장소(bucket, slot)에 최종적으로 저장되는 값으로 키와 매칭되어 저장, 삭제, 검색. 접근이 가능해야 함.

< 장단점 >

장점

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

단점

  • 해시 충돌이 발생 (개방 주소법, 체이닝 과 같은 기법으로 해결해줘야함)
  • 순서/관계가 있는 배열에는 어울리지 않음.
  • 공간 효율성이 떨어짐. 데이터가 저장되기 전에 저장공간을 미리 만들어야 함. 공간을 만들었지만 공간에 채워지지 않는 경우 발생
  • Hash fuction의 의존도가 높음. 해시함수가 복잡하다면 Hash를 만들어 내는데 오래 걸림.

Direct-address table

키의 전체 개수와 동일한 크기의 bucket을 가진 해시테이블

  • 장점 : 키의 개수와 테이블의 크기가 같기 때문에 해시 충돌 문제가 발생하지 않음.
  • 단점 : 전체 키의 개수만큼의 테이블 크기를 유지하는 것은 메모리 낭비일 수 있음.

-> 실제 키 개수보다 적은 해시테이블을 사용하기 때문에 해시 충돌이 발생할 수 밖에 없고, 해시 충돌을 해결하기 위해 다양한 방법들이 고안되었음.


해시 충돌

A,B 두가지 key가 hash function을 통해 얻은 Hash 값이 똑같을 때
Key-Value가 1:1로 매핑되어야 함
너무 많은 해시 충돌은 해시 테이블의 성능을 떨어뜨린다.

  • 클러스터링(Clustering) : 연속된 레코드에 데이터가 몰리는 현상
  • 오버플로우(Overflow) : 해시 충돌이 버킷에 할당된 슬롯 수보다 많이 발생하면 더 이상 버킷에 값을 넣을 수 없는 현상

해결방법 1. Chaining

저장소(Bucket)에서 충돌이 일어나면 기존 값과 새로운 값을 연결리스트로 연결하는 방법

장점

  • 미리 충돌을 대비해서 공간을 많이 잡아 놓을 필요가 없다. 충돌이 나면 그때 공간을 만들어서 연결해주면 된다.
  • 연결 리스트만 사용하면 되기 때문에 복잡한 계산식을 사용할 필요가 개방주소법에 비해 적다.

단점

  • 같은 hash에 자료들이 많이 연결되면 검색시 효율이 낮아짐. Open Addressing은 충돌이 일어나면 비어있는 hash에 데이터를 저장하는 방법이기 때문에 hash table은 hash와 value가 1:1 관계를 유지함.

1) 연결리스트를 사용하는 방식 (Linked List)

  • 각각의 bucket들을 연결리스트 (Linked List)로 만들어 Collison이 발생하면 해당 bucket의 list에 추가하는 방식
  • 삭제 또는 삽입이 간단
  • 작은 데이터들을 저장할 때 연결 리스트 자체의 overhead가 부담

2) Tree를 사용하는 방식 (Red-Black Tree)

  • 트리를 사용하는 방식은 메모리 사용량이 많음.

해결방법 2. 개방 주소법 (Open Addressing)

해시 충돌이 일어나면 다른 버킷에 데이터를 저장하는 방식을 개방 주소법이라고 한다.

대표적 개방 주소법

1) 선형탐색

  • 해시 충돌시 다음 버킷에 저장하는 방법

2) 제곱 탐색

  • 해시 충돌시 제곱만큼 건너뛴 버킷에 데이터를 저장하는 방법

3) 이중 해시

  • 해시 충돌시 다른 해시함수를 한 번 더 적용한 결과를 저장

장점

  • 체이닝처럼 포인터가 필요 없고, 지정한 메모리 외에 추가적인 공간이 필요 없다.
  • 삽입, 삭제시 오버헤드가 적다.
  • 저장할 데이터가 적을 때 더 유리하다.

단점

  • 최악의 경우 비어있는 bucket을 찾지 못하고 탐색을 싲가한 위치까지 되돌아 올 수 있다.
  • 특정 위치에만 데이터가 몰리는 현상이 나타날 수 있다.
profile
AI Engineer가 될테야

0개의 댓글