자료구조) 해시테이블(HashTable)

Daehwan Jung·2022년 10월 25일
0

자료구조

목록 보기
1/1

해시테이블(HashTable)

해시테이블(HashtTable)이란?

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

(Key,Value)가 ("John Smith","521-1234")인 데이터를 크기가 16인 해시 테이블에 저장하면

index : hash_function("John Smith")%16 연산을 통해 계산
array[index] : "521-1234"
를 저장하게 된다.

해시함수

해시 함수에서 가장 중요한 것은 고유한 인덱스 값을 설정하는 것

1.Division Method: 나눗셈을 이용하는 방법으로 입력값을 테이블의 크기로 나누어 계산하는 방법(주소 = 입력값 % 테이블의 크기)
2.Digit Folding: 각 Key의 문자열을 ASCII 코드로 바꾸고 값을 합한 데이터를 테이블 내의 주소로 사용하는 방법

충돌하는 경우

  1. hashfunction(A) = 17 , hashfunction(B) = 1 일때 16으로 나누면 둘다 나머지가 1 이기때문에 index 값이 충돌!
  2. hashfunction("자바"), hashfunction("바자") 일때 문자열을 ASCII 코드로 바꾸고 값을 합한 결과가 같기 때문에 index 값이 충돌!

충돌하는 경우 해결 법

분리 연결법(Separate Chaining)


Separate Chaining이란 동일한 버킷의 데이터에 대해 자료구조를 활용해 추가 메모리를 사용하여 다음 데이터의 주소를 저장하는 것이다. 위의 그림과 같이 동일한 버킷으로 접근을 한다면 데이터들을 연결을 해서 관리해주고 있다.

개방 주소법(Open Addressing)


Open Addressing이란 추가적인 메모리를 사용하는 Chaining 방식과 다르게 비어있는 해시 테이블의 공간을 활용하는 방법이다. Open Addressing을 구현하기 위한 대표적인 방법으로는 3가지 방식이 존재한다.

  • Linear Probing: 현재의 버킷 index로부터 고정폭 만큼씩 이동하여 차례대로 검색해 비어 있는 버킷에 데이터를 저장한다.

  • Quadratic Probing: 해시의 저장순서 폭을 제곱으로 저장하는 방식이다. 예를 들어 처음 충돌이 발생한 경우에는 1만큼 이동하고 그 다음 계속 충돌이 발생하면 2^2, 3^2 칸씩 옮기는 방식이다.

  • Double Hashing Probing: 해시된 값을 한번 더 해싱하여 해시의 규칙성을 없애버리는 방식이다. 해시된 값을 한번 더 해싱하여 새로운 주소를 할당하기 때문에 다른 방법들보다 많은 연산을 하게 된다.

0개의 댓글