해시와 해시 함수.

Presentation on theme: "해시와 해시 함수."— Presentation transcript:

1 해시와 해시 함수

2 해싱이란? 해싱 용도 해시테이블 하나의 문자열을 원래의 것을 상징하는 더 짧은 길이의 값이나 키로 변환하는 것이다.
하나의 문자열을 원래의 것을 상징하는 더 짧은 길이의 값이나 키로 변환하는 것이다. 용도 해시테이블을 이용한 탐색에 쓰인다. 해시테이블 키 값에 직접 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블을 해시테이블

3 해싱의 방법? 값

4 해싱의 결론! 해싱에서는 자료를 저장하는데 배열사용
원하는 항목이 들어 있는 위치를 알고 있다면 매우 빠르게 자료를 삽입하거나 꺼낼 수 있다. 어떤 항목의 키만을 가지고 바로 항목이 들어 있는 배열의 인덱스를 결정하는 기법이다.

5 해싱 함수란? =해시 알고리즘 해싱할때 키를 변환시켜주는 도구 효율적인 변환을 위한좋은 해시함수가 필요 좋은 해시 함수의 조건
충돌이 적어야 한다. 해시 함수 값이 해시 테이블의 주소 영역 내에서 고르게 분포되어야 한다. 계산이 빨라야 한다.

6 좋은예,나쁜예

7 해쉬충돌 해시함수가 서로 다른 두 개의 입력값에 대해 동일한 출력값을 내는 상황을 의미한다 해결책
 해시함수가 서로 다른 두 개의 입력값에 대해 동일한 출력값을 내는 상황을 의미한다 해결책 개방주소법Open Addressing: 선형탐색법Linear Probing 2차 탐색법Quadratic Probing 연쇄 방법Chaining Method

8 해쉬함수의 종류 나눗셈법(Division method)
탐색 키를 해시 테이블의 크기로 나눈 나머지를 해시 주소로 사용하는 방법 폴딩법Folding 키 값을 몇 개의 부분으로 분할 후 합산하여 해쉬주소를 생성하는 방법이다. 그외 유니버셜 해싱(Universal hashing) 중간제곱함수법 비트추출 방법 숫자분석 방법

9 MD5 해시함수의 한 종류 Ron Rivest가 1990년에 발표 사용방법 목적
임의 길이의 입력을 받아 이를 128bit의 해쉬 결과값으로 변환 목적 전자서명에 주로 이용된다.

10 Md5 원리1 padding bit의 추가 키값의 512비트블록들로 나눈 나머지 비트를 512까지 채우는데 모자란 부분을 0으로 채운다. 즉, 키값은 512의 배수의 값이 된다. 연산 4 word buffer A,B,C,D가 연산에 사용된다

11 I(X,Y,Z) = Y xor (X v not(Z))
Word A : Word B : 89 ab cd ef Word C : fe dc ba 98 Word D : F(X,Y,Z) = XY v not(X) Z G(X,Y,Z) = XZ v Y not(Z) H(X,Y,Z) = X xor Y xor Z I(X,Y,Z) = Y xor (X v not(Z)) 64번

12 Md5의 결과 A,B,C,D, 키값의 연산 결과값은 A,B,C,D의 값이다. (A~ D) 길이는 4 word, 즉 128 bit이다. A=B=C=D=4word=32bit 결과값은 ABCD=128bit가 된다.