11-04 개방 주소법(Open Addressing)

 

아래의 상기 내용은

"이것이 자료구조+알고리즘이다. With C언어"의 도서 내용과 인터넷의 내용을 실습 및 정리한 글입니다.

 

 

1.개방 주소법(Open Addressing)

 1)정의

 -해시테이블에 충돌이 일어나도 해시함수로 만들어진 주소 이외에 다른 주소를 사용하여

 충돌을 해결하는 알고리즘

 

2.선형탐사(Linear Probing)

 1)정의

 -개방 주소법 중 하나로 해시함수로 얻어낸 주소에 이미 다른 데이터가 입력 경우

 현재 주소에서 일정 거리의 주소로 이동하는 방식.

 

 

 

 

3.제곱탐사(Quadratic Probing)

 1)정의

 -개방 주소법 중 하나로 해시함수로 얻어낸 주소에 이미 다른 데이터가 입력 경우

 현재 주소에서 탐사 횟수에  제곱된 거리의 주소로 이동하는 방식.

 

4.이중 해싱(Double Hashing)

 1)정의

 -해시 함수를 여러 종류를 두어 클러스터 현상을 해결하는 방법

 -해시 함수로 주소의 이동폭을 제한하거나, 특정상황에서 다른 해시함수를 사용하여 테이블 내

 규칙성을 떨어트리는 것을 목적으로 사용한다.  

 

5.재해싱(ReHasing)

 1)개요 및 정의

 -해시 테이블이 충돌 문제를 해결하는 알고리즘을 사용하더라도 해시 테이블의 여유공간이

 없어 생기는 성능 저하를 막아낼 수 없다.

-재해싱은 해시 테이블의 크기를 늘려 늘어난 해시 테이블의 크기에 맞춰 모든 데이터를 다시

 해싱하는 것.

-해시 테이블은 공간 사용률이 70%~80%에 이르면 성능저하가 나타나기 시작하므로 미리 재해싱을

 시작해야 성능저하를 막을 수 있다.

 

 

6.개방 주소법 해시테이블 구현

6.개방 주소법 해시테이블 구현

 1)데이터 노드 구현

 2)원형 함수 선언

 3)함수 구현

-해시테이블 생성 및 삭제 연산

 

-데이터 키,값 설정 연산

-데이터 값 반환 연산

-해시함수 및 이중해시

-재해싱 함수

-테스트