자료구조 - Chapter 13

테이블(Table)과 해쉬(Hash)

테이블(Table)

우리가 흔히 사용하는 표가 테이블이다.

하지만 자료구조의 관점에서 테이블에 저장되는 데이터는 키(key)와 값(value)가 하나의 쌍을 이룬다.

따라서 키(key)가 존재하지 않는 값은 저장할 수 없고 모든 키는 중복되지 않는다.

이러한 테이블은 서전 구조 또는 맵(map)이라고 불린다.

 

예제 : 배열 기반의 테이블 구현하기

키를 인덱스 값으로 하여 그 위치에 데이터를 저장한다.

하지만 키의 값의 범위가 크다면 문제가 발생한다.

배열기반의 테이블

ex13-1 SimpleTable.c

0.00MB

배열 기반 테이블 문제점

• 키의 범위(고유 인덱스)가 배열의 인데그 값으로 사용하기에 적당하지 않다.
• 키의 범위를 수용할 수 있는 매우 큰 배열이 필요하다.

예제 : 해쉬 함수를 이용한 테이블 구현하기

해쉬 함수(Hash Function)

넓은 범위의 키를 좁은 범위의 키로 변경하는 역할 수행.

 

간단한 해ㅟ함수 구현하기

ex13-2 Using SimpleHashFunc.c

0.00MB

예제 : 좋은 해쉬 함수를 사용하여 테이블 구현하기

좋은 해쉬 함수 조건

데이터가 전체 영역에 고루 분포되게 만드는 함수. 이렇게 데이터가 고르게 분포하면 충돌 발생 확률이 낮아진다. 

따라서 좋은 해쉬함수는 키의 일부분을 참조하여 해쉬 값을 만들지 않고, 키 전체를 참조하여 해쉬 값을 만든다.

• 자릿수 선택(Digit Selection) 방법
• 자릿수 폴딩(Digit Folding) 방법

해쉬 함수를 이용한 테이블 구현

ex13-3 HashFunction.c

0.00MB

Person.c

0.00MB

Person.h

0.00MB

Slot.h

0.00MB

Table.c

0.00MB

Table.h

0.00MB

 

예제 : 충돌을 방지하는 해쉬함수를 이용하여 테이블 구현하기(이중 해쉬)

• 선형 조사법(Linear Probing) : 충돌이 발생했을 때, 옆자리 비어있는지 살펴보고 그 자리 사용하는 방법
• 이차 조사법(Quadratic Probing) : 충돌 발생 시, 멀리서 빈 공간을 찾아서 그 자리를 사용하는 방법

이중해쉬 (Double Hash)

• 1차 해쉬 함수 : 키를 근거로 저장위치를 결정하기 위한 것
• 2차 해쉬 함수 : 충돌 발생시 몇 칸 뒤를 살필지 결정하기 위한 것

이중 해쉬로 테이블 구현하기

ex13-4 chainHashFunc.c

0.00MB

Person.c

0.00MB

Person.h

0.00MB

Slot2.h

0.00MB

Table2.c

0.00MB

Table2.h

0.00MB