본문 바로가기
STUDY/Data Structure

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

by mhl22 2021. 8. 6.

회사 코드를 볼 때 해시테이블이라는 자료구조를 가끔씩 만났다. 시간이 없다는 핑계로 사용법만을 유추해서 코드를 이해하고 지나가기 바빴는데 오늘은 그 내용을 제대로 정리해보려고 한다.

 

해싱 (Hashing) 이란?

해시 함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 해시 함수에 의해 얻어지는 값은 해시 값, 해시 코드, 해시 체크섬 또는 간단하게 해시라고 한다. 해싱은 임의의 데이터를 해시함수 (Hash Function)을 사용하여 고정된 크기의 값으로 변환하는 작업을 말한다.

 

해싱을 사용하여 데이터를 저장하는 자료구조를 해시 테이블 (Hash Table) 이라고 하며 이는 기존 자료구조인 이진탐색트리나 배열에 비해서 굉장히 빠른 속도록 탐색, 삽입, 삭제를 할 수 있다는 장점이 있다.

 

해시 테이블 (Hash Table) 이란?

해시 테이블은 (Key, Value) 로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조이다. 해시 테이블이 빠른 검색속도를 제공하는 이유는, 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문이다. 해시 테이블은 각각의 key 값에 해시 함수를 적용하여 배열의 고유한 index 를 생성하고, 이 index 를 활용해 값을 저장하거나 검색하게 된다. 실제 값이 저장되는 장소를 버킷 (또는 슬롯) 이라고 한다.

장점

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

단점

  • 해시 충돌이 발생한다.
  • 순서/관계가 있는 배열에는 어울리지 않는다.
  • 공간 효율성이 떨어진다. -> 데이터가 저장되기 전에 미리 저장공간을 확보해야 하기 때문이다.
  • hash function의 의존도가 높다 => 해시함수가 복잡한 경우 연산속도 증가

 

해시 충돌 (Hash Collision)

키의 전체 개수와 동일한 크기의 버킷을 가진 해시테이블을 Direct-address table 이라고 한다. Direct-address table의 장점은 키의 개수와 테이블의 크기가 같기 때문에 해시 충돌 문제가 발생하지 않는다는 것이다. 하지만 실제 사용하는 키는 몇개 되지 않는데 큰 크기의 테이블을 유지하고 있는 것은 메모리 낭비이다. 따라서 보통의 경우 실제 사용하는 키 개수보다 적은 해시테이블을 운용한다고 한다.

 

서로 다른 key 가 해싱 후 같은 hash 값이 나오는 경우가 있고, 이를 해시 충돌이라고 부른다. 

 

해결방법 1) Chaining

버킷에서 충돌이 일어나면 기존 값과 새로운 값을 연결리스트로 연결하는 방법이다. 같은 hash에 자료들이 많이 연결되면 검색시 효율이 낮아진다는 단점이 있다.

 

해결방법 2) Open Addressing

충돌이 일어나면 비어있는 hash 에 데이터를 저장하는 방법이다. hash와 value가 1:1 관계를 유지할 수 있다.

비어있는 hash를 찾아가는 방법은 선형탐색 (Linear Probing), 제곱 탐색 (Quadratic Probing), 이중 해싱 (Double Hashing Probing) 등의 방법이 있다. 

 


참고

https://velog.io/@adam2/자료구조해시-테이블

 

[자료구조]해싱, 해시 테이블 그리고 Java HashMap

해시테이블은 해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 색인 또는 주소 삼아 데이터(value)를 key와 함께 저장하는 자료구조이다.연관배열 구조: key와 value가 1:1로 연관되어있

velog.io

https://mangkyu.tistory.com/102

 

[자료구조] 해시테이블(HashTable)이란?

1. 해시테이블(HashTable)이란? [ HashTable(해시테이블)이란? ] 해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조이다. 해시 테이블이 빠른

mangkyu.tistory.com

 

'STUDY > Data Structure' 카테고리의 다른 글

[자료구조] heap(힙 자료구조) / Python heapq(힙큐)  (0) 2021.08.11