[알고리즘] 해싱테이블, 해싱함수
[알고리즘] 해싱테이블, 해싱함수
해싱
- 해싱은 Hash Table이라는 기억공간을 할당하고
- 해시 함수라는 기억공간을 할당하고
- 해시 함수를 이용하여 레코드 키에 대한 Hash Table내의 Home Address를 계산 한 후 주어진 레코드를 해당 기억장소에 저장하거나 검색 작업을 수행하는 방식
- 해싱은 DAM(직접 접근)파일을 구성할 때 사용되며, 접근 속도는 빠르나 기억공간이 많이 요구된다.
- 다른 방식에 비해 검색 속도가 가장 빠르다.
- 삽입 삭제 작업의 빈도가 많을 때 유리한 방식이다.
- 키-주소 변환 방법이라고도 한다.
해시테이블(HashTable)
해시테이블은 레코드를 한개 이상 보관할 수 있는 Bucket들로 구성된 기억공간으로 보조기억장치에 구성할 수도 있고 주기억장치에 구성할 수도 있다.
- 버킷(Bucket)
- 하나의 주소를 갖는 파일의 한 구역을 의미하며, 버킷의 크기는 같은 주소에 포함될 수 있는 레코드 수를 의미한다.
- 슬롯(Slot)
- 한 개의 레코드를 저장할 수 있는 공간으로 n개의 슬롯이 모여 하나의 버킷을 형성한다.
- Collision(충돌현상)
- 서로 다른 두개이상의 레코드가 같은 주소를 갖는 현상이다.
- Synonym
- 충돌로 인해 같은 Home Address를 갖는 레코드들의 집합이다.
- Overflow
- 계산된 Home Address의 Bucket내에 저장할 기억공간이 없는 상태로, Bucket을 구성하는 Slot이 여러개일때 Collision은 발생해도 Overflow는 발생하지 않을 수 있다.
- Overflow처리 방법
- 개방주소법 : 선형방법. collision 발생시 순차적으로 그 다음 빈 버킷을 찾아 저장함(새로운 공간을 할당)
- 폐쇄주소법 : overflow된 레코드들을 별도의 overflow영역에 저장하고 chain(pointer)으로 홈 버킷에 연결하는 방법(주어진 해시 테이블 안에서)
- 재해싱 : collision 발생 시 새로운 해싱 함수로 새로운 홈주소를 구함
해싱함수(Hasing Function)
제산법
- 제산(Division)법은 레코드키로 해시표의 크기보다 큰 수 중에서 가장 작은소수로 나눈 나머지를 홈 주소로 삼는 방식이다.
제곱법
- 제곱법은 레코드키 값을 제곱한 후 그 중간 부분의 값을 홈 주소로 삼는 방식이다.
폴딩법
- 폴딩(Folding)법은 레코드키값을 여러부분으로 나눈 후 각 부분의 값을 더하거나 XOR(배타적 논리합)한 값을 홈주소로 삼는 방식이다.
- Shift Folding : 각 부분의 값들을 왼쪽 or 오른쪽 끝자리에 맞추어서 계산
- Fold Boundary : 경계 지점을 접었을 때 마주치는 자리 그대로 계산
기수변환법
- 기수변환법은 키 숫자의 진수를 다른 진수로 변환시켜 주소 크기를 초과한 높은 자릿수는 절단하고, 이를 다시 주소 범위에 맞게 조정하는 방식
대수적 코딩법
- 대수적 코딩법은 키 값을 이루고 있는 각 자리의 비트 수를 한 다항식의 계수로 간주하고, 이 다항식을 해시표의 크기에 의해 정의된 다항식으로 나누어 얻은 나머지 다항식의 계수를 홈 주소로 삼는 방식이다.
계수 분석법(숫자 분석법)
- 계수 분석법은 키 값을 이루는 숫자의 분포를 분석하여 비교적 고른 자리를 필요한 만큼 택해서 홈 주소로 삼는 방식이다.
무작위법
- 무작위(Random)법은 난수(Random Number)를 발생시켜 나온 값을 홈 주소로 삼는 방식이다.
Overflow 해결 방법
충돌이 발생했을 때 그 버킷에 저장할 slot이 없으면 Overflow가 되는데, 이것을 해결하기 위해서는 다음과 같은 방법이 필요합니다.체이닝(Chaining)
버킷 내이 연결리스트를 할당하여, 버킷에 데이터를 삽입하닥 해시 충돌이 발생하면 연결리스트로 데이터를 연결하는 방식이다.개방 주소법(Open Addressing)
체이닝의 경우 버킷이 꽉 차더라도 연결리스트로 계속 늘려나기에, 데이터의 주소값은 바꾸지 않는다.하지만 개방 주소법의 경우에는 다르다. 해시 충돌이 일어나면 다른 버켓에 데이터를 삽입하는 방식을 개방 주소법이라고 한다.
개방 주소법은 대표적으로 3가지가 있다.
- 선형 탐색 : 해시 충돌 시 다음 버킷, 혹은 몇 개를 건너뛰어 데이터를 삽입한다.
- 제곱 탐색 : 해시 충돌 시 제곱만큼 건너뛴 버킷에 데이터를 삽입한다.(1,4,8,16..)
- 이중 해시 : 해시 충돌 시 다른 해시함수를 한 번 더 적용한 결과를 이용한다.
폐쇄 주소법(Close Addressing)
Overflow된 레코드들을 별도의 Overflow 영역에 저장하고 Chain(Pointer)으로 홈 버킷에 연겨한다.- Direct Chaining : 해시표 내의 빈자리(Cylinder Overflow Area)에 Overflow레코드를 보관한다.
- Indirect Chaining : 해시표와는 별도의 기억공간(Independent Overflow Area)에 Overflow 레코드를 보관한다
재해싱(Rehashing)
충돌이 발생하면 새로운 해싱 함수로 새로운 홈 주소를 구하는 방식출처
댓글
댓글 쓰기