해시

해시 함수 종류[편집 | 원본 편집]

해시 함수(Hash function) : 데이터를 키로 변환하는 함수. 예를 들어 길고 복잡한 문자열을 짧고 단순한 문자열로 변경
홈 주소(Home address): 해시 함수에 의해 변환된 키값의 주소
해시 테이블(Hash table): 해시 함수가 키값을 생성할때 참조하는 테이블
버킷(Bucket): 하나의 주소를 갖는 파일의 한 구역. 버킷의 크기는 같은 주소에 포함될 수 있는 레코드의 수
슬롯(Slot): 한개의 레코드를 저장 할 수 있는 공간. 한 버킷 안에 여러개의 슬롯이 있다.
충돌(Collision): 다른 레코드가 같은 키를 가지는 충돌 현상. 레코드는 버킷의 다음 슬롯에 들어감
동의어(Synonym): 동일한 홈 주소로 인하여 충돌이 일어난 레코드의 집합. 키값이 같은 레코드의 집합으로, 동의어가 슬롯의 갯수보다 많으면 오버플로우가 일어날 수 있다.
오버플로(Overflow) : 한 홈 주소의 버킷 내에 더 이상의 레코드를 저장할 슬롯이 없는 상태

충돌 저항성: 동일한 출력을 산출하는 서로 다른두 입력을 계산적으로 찾기 어려운 성질
- 강한 충돌 저항성: H(X) = H(Y) 인 서로 다른 임의의 두 입력 X, Y 를 찾는 것은 계산적으로 어려워야 한다.
- 약한 충돌 저항성: X가 주어졌을 때 H(X) = H(Y) 인 X!=Y 것을 찾는 것은 계산적으로 어려워야 한다.
역상 저항성: 해시값 m에 대해 H(X) = m을 만족하는 X값을 찾기 어려운 성질
- 제2역상 저항성: 해시값 m에 대해 h(x)=h(x'), x≠x'를 만족하는 x'를 찾는 것이 어려운 성질

개방 주소법(Open Addressing)
- 선형 방법(Linear Method)이라고도 함
- Collision이 발생했을 때 순차적으로 다음 빈 버킷을 찾아 저장
폐쇄 주소법(Close Addressing)
- Overflow된 레코드들을 별도의 Overflow 영역에 저장하고 Chain(Pointer)으로 홈 버킷에 연결
- Direct Chaining: 해시표 내의 빈 자리(Cylinder Overflow Area)에 Overflow 레코드를 보관
- Indirect Chaining: 해시표와는 별도의 기억공간(Independent Overflow Area)에 Overflow 레코드를 보관
재해싱(Rehashing)
- Collision이 발생하면 새로운 해싱 함수로 새로운 홈 주소를 구하는 방식

레코드 키 값을 어떤 해싱 함수에 의해 주소로 변환시켜 해당 주소 위치에 레코드를 저장하는 방식으로 키 변환 값이 같은 경우 오버플로우 문제가 발생하지만 검색할 때 찾고자 하는 레코드의 키 값을 주소 변환에 의 해 해당 위치를 검색하므로 조사 횟수가 상당히 작은 방식