Hashing

Hashing

• 고유 함수에 키 값을 입력받아 고유한 결과값을 주소로 사용하여 value 에 접근 하는것을 말한다.

보통 hashing 은 보안이나 자료 구조를 저장하는데 많이 사용된다

해쉬 알아두기

1. 입력값이 동일하면 출력되는 해시값도 동일하다.
2. 입력값의 길이에 상관없이 변환되는 해시값의 길이는 동일하다.
3. 출력된 해시값으로 입력값을 절대 찾을 수 없음
4. 서로 다른 입력값이 같은 해시값을 반환할 확률은 낮다.

해싱을 하는 방법은 여러가지가 있다.

1. 정적해싱

• 고정크기의 배열사용, 구현이 쉽고 간단하다,
• 단점(데이터의 증가에 따라 검색 성능이 떨어진다)
• 버킷의 크기를 작게 잡을 경우 충동의 우려가 있다.

2. 중간 제곱법

• 키 값을 제곱 한 후 결과 값의 중간 부분에 있는 몇 비트만을 선택

3. 폴딩법

• 키 값을 길이가 동일하게 나누고 난 뒤, 모든 부분을 더하거나, XOR 연산을 이용한다.

4. 경계 폴딩

• 키 값을 여러 부분으로 나누고 난 뒤, 짝수 번째 부분을 뒤집고 난 후 더한다.

5. 숫자 분석법

• 숫자들의 분포도를 보고 고른 분포를 나타내는 자릿 수를 필요한 만큼 선택하여 인덱스로 사용한다.