해시 편집하기
IT위키
편집을 취소할 수 있습니다. 이 편집을 되돌리려면 아래의 바뀐 내용을 확인한 후 게시해주세요.
| 최신판 | 당신의 편집 | ||
| 1번째 줄: | 1번째 줄: | ||
;Hash | ;Hash | ||
* 하나의 문자열을 원래의 것을 상징하는 더 짧은 길이의 값이나 키로 변환하는 것 | |||
== 해시 함수 종류 == | |||
* 제곱법 : 키값을 제곱한 후에 중간의 몇자리를 선택하고 그 중간 값을 주소로 이용 | |||
==해시 함수 종류== | * 제산법 : 레코드 키 값을 소수로 나누어 나머지 값을 주소로 결정 | ||
* 중첩법(폴딩법) : 길이를 동일하게 여러 부분으로 나누고, 더하거나 XOR 하여 주소 이동 | |||
*제곱법 : 키값을 제곱한 후에 중간의 몇자리를 선택하고 그 중간 값을 주소로 이용 | * 숫자분석법 : 각 숫자의 분포를 이용해서 균등한 분포의 숫자를 선택해서 사용 | ||
*제산법 : 레코드 키 값을 소수로 나누어 나머지 값을 주소로 결정 | * 기수 변환법 : 주어진 키의 값을 다른 진법으로 변환하여 얻은 값을 주소로 사용 | ||
*중첩법(폴딩법) : 길이를 동일하게 여러 부분으로 나누고, 더하거나 XOR 하여 주소 이동 | * 무작위 방법 : 난수를 발생, 탐색을 위한 해시의 경우 충돌이 발생하면 다음 난수를 이용 | ||
*숫자분석법 : 각 숫자의 분포를 이용해서 균등한 분포의 숫자를 선택해서 사용 | |||
*기수 변환법 : 주어진 키의 값을 다른 진법으로 변환하여 얻은 값을 주소로 사용 | |||
*무작위 방법 : 난수를 발생, 탐색을 위한 해시의 경우 충돌이 발생하면 다음 난수를 이용 | |||
*'''해시 함수(Hash function)''' : 데이터를 키로 변환하는 함수. 예를 들어 길고 복잡한 문자열을 짧고 단순한 문자열로 변경 | == 개념 및 용어 == | ||
*'''홈 주소(Home address)''': 해시 함수에 의해 변환된 키값의 주소 | * '''해시 함수(Hash function)''' : 데이터를 키로 변환하는 함수. 예를 들어 길고 복잡한 문자열을 짧고 단순한 문자열로 변경 | ||
*'''해시 테이블(Hash table)''': 해시 함수가 키값을 생성할때 참조하는 테이블 | * '''홈 주소(Home address)''': 해시 함수에 의해 변환된 키값의 주소 | ||
*'''버킷(Bucket)''': 하나의 주소를 갖는 파일의 한 구역 | * '''해시 테이블(Hash table)''': 해시 함수가 키값을 생성할때 참조하는 테이블 | ||
*'''슬롯(Slot)''': 한개의 레코드를 저장 할 수 있는 공간. 한 버킷 안에 여러개의 슬롯이 있다. | * '''버킷(Bucket)''': 하나의 주소를 갖는 파일의 한 구역, 버킷의 크기는 같은 주소에 포함될 수 있는 레코드의 수 | ||
*'''충돌(Collision)''': 다른 레코드가 같은 키를 가지는 충돌 현상. 레코드는 버킷의 다음 슬롯에 들어감 | * '''슬롯(Slot)''': 한개의 레코드를 저장 할 수 있는 공간. 한 버킷 안에 여러개의 슬롯이 있다. | ||
*'''동의어(Synonym)''': 동일한 홈 주소로 인하여 충돌이 일어난 레코드의 집합. 키값이 같은 레코드의 집합으로, 동의어가 슬롯의 갯수보다 많으면 오버플로우가 일어날 수 있다. | * '''충돌(Collision)''': 다른 레코드가 같은 키를 가지는 충돌 현상. 레코드는 버킷의 다음 슬롯에 들어감. 레코드를 삽입할 때 2개의 상이한 레코드가 똑같은 홈 주소로 해싱되는 경우 | ||
*'''오버플로(Overflow)''' : 한 홈 주소의 버킷 내에 더 이상의 레코드를 저장할 슬롯이 없는 상태 | * '''충돌 회피성(충돌 저항성)''': 동일한 출력을 산출하는 서로 다른두 입력을 계산적으로 찾기 어려운 성질 | ||
** '''강한 충돌 회피성''': H(X) = H(Y) 인 서로 다른 임의의 두 입력 X, Y 를 찾는 것은 계산적으로 어려워야 한다. | |||
** '''약한 충돌 회피성''': X가 주어졌을 때 H(X) = H(Y) 인 X!=Y 것을 찾는 것은 계산적으로 어려워야 한다. | |||
* '''동의어(Synonym)''': 동일한 홈 주소로 인하여 충돌이 일어난 레코드의 집합. 키값이 같은 레코드의 집합으로, 동의어가 슬롯의 갯수보다 많으면 오버플로우가 일어날 수 있다. | |||
* '''오버플로(Overflow)''' : 한 홈 주소의 버킷 내에 더 이상의 레코드를 저장할 슬롯이 없는 상태 | |||
== | == 대표적 해시 함수 == | ||
* MD5, SHA, HAS | |||
== 오버플로우 처리 기법 == | |||
* '''개방 주소법(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이 발생하면 새로운 해싱 함수로 새로운 홈 주소를 구하는 방식 | |||
==오버플로우 처리 기법== | |||
*'''개방 주소법(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이 발생하면 새로운 해싱 함수로 새로운 홈 주소를 구하는 방식 | |||
== 해시 탐색 == | |||
;레코드 키 값을 어떤 해싱 함수에 의해 주소로 변환시켜 해당 주소 위치에 레코드를 저장하는 방식으로 키 변환 값이 같은 경우 오버플로우 문제가 발생하지만 검색할 때 찾고자 하는 레코드의 키 값을 주소 변환에 의 해 해당 위치를 검색하므로 조사 횟수가 상당히 작은 방식 | ;레코드 키 값을 어떤 해싱 함수에 의해 주소로 변환시켜 해당 주소 위치에 레코드를 저장하는 방식으로 키 변환 값이 같은 경우 오버플로우 문제가 발생하지만 검색할 때 찾고자 하는 레코드의 키 값을 주소 변환에 의 해 해당 위치를 검색하므로 조사 횟수가 상당히 작은 방식 | ||
* 특정 데이터가 저장된 기억장소의 주소를 관리하기 위한 사상테이블(Mapping Table)을 정의하기 위해 해시를 사용 | |||
* 빠르다는 장점 때문에 운영체제 및 직접 접근파일을 구성하는데 사용된다. | |||
* 사상 테이블의 용량부족으로 인한 Overflow가 발생할 수 있다. | |||
* 동일한 주소를 만들어 내는 두 개 이상의 키 값인 동의어(Synonym)에 의해 충돌(Collision)이 발생 할 수 있다. | |||
== 해시 암호화 == | |||
==해시 암호화== | |||
* | * | ||
