티스토리 뷰

CS (Computer science)

[CS] Hash Table(해시 테이블)

Peppo 2023. 7. 6. 08:49
728x90

오늘은 Hash Table에 대해 공부해보려 합니다.

유튜브를 보는데 '해시를 모르는데 면접에서 붙을리가..' 라는 제목을보고 뜨끔해서 정리해봅니다..!

 

목차

 

- 해시 함수

- 해시 테이블

- 해시 충돌

Hash Function - 해시함수

 

주요 역할

 

원래의 데이터(key)를 hash value로 변경해줍니다.

hash value는 고유한 index값이 됩니다.

key → 해시함수 → hash value

이 과정을 hashing 이라고 합니다.

 

대표적인 해시 함수(4가지)

1. Division Method

나눗셈을 이용하는 방법.
key값을 테이블의 크기로 나누어 계산. 나머지를 index로 사용

index = key / 테이블 크기

ex) key값이 23이고, 테이블 크기가 7이면 index는 2가 됨.

 

2. Digit Folding

key의 문자열을 ASCII 코드로 바꿔 값을 합한 데이터를 테이블 내 주소로 사용하는 방법.

 

3. Multiplication Method

숫자로된 key값(K), 0~1 사이의 실수 A, 2의 제곱수인 M을 사용해 아래와 같은 공식으로 계산.

index = (KA mod 1)m

 

4. Universal Hashing

여러 해시 함수를 만들어 특정한 장소에 넣어두고, 무작위로 해시함수를 선택해 hash value를 만드는 방법.

 

Hash Table - 해시테이블

 

해시 함수를 사용해서 변환한 값을 index로 삼아 key와 value(bucket이라고도 함)를 저장하는 자료구조를 말합니다.

 

예)

Swift, Python - dictionary

Java, JavaScript - Map

 

특징

  • 기본 연산으로 search(검색), insert(삽입), delete(삭제)가 있습니다..
  • 순차적으로 데이터를 저장 하지않습니다. (해시함수의 변환값을 index로 삼기 때문)
  • key를 입력하면 value값을 얻을 수 있습니다. (배열에 비해 속도가 빠름)

예시1)

선형검색(Linear Search)과 비교해보자면,

메뉴 = ["피자", "치킨", "키토김밥", "족발", "파전", "복순도가"]

“복순도가”를 찾고 싶을때 선형검색에서 순차적으로 검색하기 때문에 원하는 값이 뒤에 있을 수록 시간이 오래걸립니다.

시간복잡도: O(n)

 

 

해시테이블을 이용할 경우 key값만 안다면 아래처럼 원하는 값을 한번에 찾을 수 있습니다.

메뉴[”복순도가”]
// ₩12,000
시간복잡도: O(1)

 

동작방식

 

  1. /100 의 몫을 hash value 로 변환하는 해시함수가 있다고 가정.
  2. 각 데이터 마다 해시함수를 거쳐 index 값을 부여 받음.
  3. 위 그림에서 순서대로 index값을 배정
    1. 123 → 1
    2. 234 → 2
    3. 345 → 3
    4. 456 → 4
  4. 해당 index에 값을 저장

Q: 데이터 123, 100, 145가 있으면 index 1이 나올텐데? 어떻게 저장하죠?

A: 우린 이걸 해시충돌 이라 부르기로 했어요

 

Hash collision - 해시충돌

 

데이터가 해시함수를 거쳐 반환된 키값이(hash value) 이미 존재하는 경우.

John Smith, Sandra Dee 의 hash키 값이 2로 동일

 

위 그림처럼 index(hash value) 값이 같이 배정되는 경우를 해시충돌이라고 하며, 여러 해결 방법이 있습니다.

 

체이닝(separate Chaining)

추가적인 메모리를 사용하여 버킷(bucket) 내 연결리스트(Linked List)를 할당해 데이터를 연결하는 방식입니다.

John Smith가 index 152로 배정이 되었는데, Sandra Dee도 같은 index로 배정이 된다면,
먼저 저장한 John Smith의 다음 원소로 Sandra Dee를 저장합니다.

 

 

장점

  • 해시 테이블을 확장할 필요가 없음
  • 간단한 구현
  • 원소를 쉽게 삭제할 수 있음.

단점

  • 중복되는 index에 데이터가 많아지면 캐시 효율성 ↓

 

개방 주소법(Open Addressing)

 

비어있는 해시 테이블 공간을 활용하는 방법.

3가지 방법이 있습니다.

 

1. 선형 탐사(Linear Probing)


: 현재 버킷 index로 부터 고정폭 만큼씩 이동해 차례대로 검색해 비어있는 버킷에 데이터를 저장하는 방법

 

 

 

2. 제곱 탐사(Quadratic Probing)


: 해시의 저장순서 폭을 제곱으로 저장하는 방식
ex) 충돌이 발생할때 마다 2^2, 3^2, 4^2 …(n^2) 칸씩 옮기는 방식

(좌) 선형탐사 / (우) 제곱탐사


3. Double Hashing Probing


: 해시된 값을 한번 더 해싱하여 해시의 규칙성을 없애버리는 방식.

 

  • 다른 방법들보다 많은 연산을 하게되는 단점이 있음.

실제로 Swift에서 빌트인 메서드로 hash(into:)가 있습니다.

 

해시 테이블, 해시함수를 따로 구현할 일은 거의 없습니다.
(시니어 면접에서는 해시테이블을 구현해보라고도 함..)

이미 대부분의 언어에 구현되어 있으며, 동작원리에 간단한 개념만 알고 넘어가면 될것 같습니다.

  •  
728x90

'CS (Computer science)' 카테고리의 다른 글

[CS] 네트워크 - OSI 7계층 (4 ~ 7계층)  (0) 2023.06.18
[CS] 네트워크 - OSI 7계층 (1 ~ 3계층)  (2) 2023.06.04