CS/자료구조

[자료구조] 해시(Hash)

ummchicken 2023. 1. 24. 15:39

해시 테이블 (Hash Table)

데이터를 효율적으로 관리하기 위해,
임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 것.

해시 함수를 구현하여 데이터 값을 해시 값으로 매핑한다.

 

 

 

 

 

해시 테이블의 특징

  • 해시 테이블이란, (key, value)의 형태로 데이터를 저장하는 자료구조이다.
  • 빠른 데이터 검색이 필요할 때 유용하다.
  • 해시 함수에 key를 적용해 고유한 index를 생성하여, 그 index에 저장된 값을 꺼내오는 구조이다.
  • 해시 충돌이 일어나지 않는 경우, 해시 테이블의 시간 복잡도는 O(1)
  • Hash map, map, dictionary, 연관배열 등의 이름으로 알려져 있다.

 

 

해시 함수

  • key를 해시로 바꿔는 역할을 한다.
  • 다양한 길이를 가지고 있는 key를, 일정한 길이의 hash로 바꾸어 공간을 효율적으로 관리. (key의 길이 > hash의 길이)
  • 결국 데이터가 많아지면, 다른 데이터가 같은 해시 값으로 충돌나는 현상이 발생함 'collision' 현상
  • 해시 충돌(Hash Collision)을 최소화 하는 해시 함수를 만드는 것이 중요하다.

 

 

해시

  • 해시 함수의 결과 값
  • 저장소(bucket)에서, 값(value)와 매칭되어 저장됨

 

 

해시 충돌

  • 서로 다른 키가 같은 해시 값을 가지는 경우
  • ex) "Sam Smith"와 "Emily Kim" 을 해시 함수에 넣었을 때 같은 결과가 나오는 경우

 

 

해시 충돌 해결

기본적으로 두 가지 방식이 있다.

 

  • Separate Chaining (분리 연결법) : 다른 해시 버킷이 아니라 해당 해시 버킷에 여러 개의 데이터를 연결하는 방식으로, 트리를 이용한 방식과 linked list를 이용한 방식이 있다. (연결 리스트로 노드를 계속 추가해나가는 방식. 제한 없이 계속 연결 가능. But 메모리 문제)
  • Open Addressing (개방 주소법) : 해시 함수로 얻은 주소가 아닌 다른 주소에 데이터를 저장할 수 있도록 허용. (다른 해시 버킷에 해당 자료를 삽입하는 방식)

 

 

Chaining (체이닝)

해시 충돌이 일어났을 때, 이를 동일한 버킷에 저장하는데, 
이를 연결리스트로 저장하는 방법을 말한다.

 

※ 시간 복잡도
- 탐색 / 삭제는 키에 해당하는 리스트 길이에 비례한다.
최악의 경우 O(k), 이때 k는 키 값의 갯수.

- 삽입은 O(1)

 

 

 

Open Addressing

해시 충돌이 일어날 경우, 저장소의 다른 주소도 이용할 수 있게 하는 방법

 

ex) "Sandra Dee"라는 키에 대해 해시 함수를 적용한 결과, 152가 나왔다.
그렇지만 152번은 이미 다른 키에 의해 사용되고 있는 공간임.
따라서 그 다음 비어있는 주소인 153에 저장함.
※ 시간 복잡도
- 탐색, 삽입, 삭제 모두 최상의 경우 O(1), 최악의 경우 O(n)

※ 장점
- 다른 저장공간 없이 해시테이블 내에서 데이터 저장이 가능하다.

※ 단점
- 해시함수의 성능에 따라 해시 테이블 전체의 성능이 좌지우지된다.
- 데이터의 양이 늘어나면, 그에 해당하는 크기의 저장소를 미리 확보해두어야 한다.

 

Open Addressing에서는,

저장소가 어느정도 채워졌을 때 저장소의 크기를 늘리는 것이 중요하다.

  • Open Addressing의 3가지 충돌 해결 기법
    • 선형 탐사 (Linear Probing)
    • 제곱 탐사 (Quadratic Probing)
    • 이중 해싱 (Double Hashing)

 

 

 

해시 충돌의 문제가 있음에도 해시 테이블을 쓰는 이유는 ?

  • 많은 양의 데이터를 빠르게 탐색할 수 있기 때문 → 해시 충돌이 없으면 O(1)의 시간으로 탐색 가능
  • 적은 자원으로 많은 양의 데이터를 효율적으로 관리할 수 있기 때문
  • 하드디스크나, 클라우드에 존재하는 무한한 데이터들을 유한한 개수의 해시값으로 매핑하면,
    작은 메모리로도 프로세스 관리가 가능해짐

 

 

 

HashMap과 HashTable의 차이점에 대해?

동기화 지원 여부의 차이가 있다.
병렬 처리를 하면서 자원의 동기화를 고려해야 하는 상황이라면
해시테이블(HashTable)을 사용해야 하며,

병렬 처리를 하지 않거나 자원의 동기화를 고려하지 않는 상황이라면
해시맵(HashMap)을 사용하면 된다.

 

 

 

Map과 Hash Map(Set과 Hash Set)의 차이

  • Map은 Red-black Tree 알고리즘을 이용해 구현 (바이너리 서치 트리(이진탐색트리)) 
    → 키 값이 정렬되어 있음
  • Hash Map은 Hash Table을 이용해 구현

 

 

 

 

 

출처

 

 

 

저작자표시 비영리 변경금지

'CS > 자료구조' 카테고리의 다른 글

[자료구조] 트리(Tree)와 힙(Heap)  (0) 2023.01.24
[자료구조] 스택(Stack) & 큐(Queue)  (2) 2023.01.09
[자료구조] Array vs ArrayList vs LinkedList  (0) 2023.01.07

'CS/자료구조'의 다른글

  • 현재글[자료구조] 해시(Hash)

관련글

댓글

티스토리툴바