Hash(table)효율적으로 데이터 삽입, 탐색을 위한 자료구조.
최솟값이나 최대 값같이 (전체를 검색할때)는 효율이 떨어짐
넓은 공간을 써서 탐색 시간을 줄인다!
최대 O(N) 최소 O(1) (상환시간으로 계산하면)
해쉬 코드함수(hash code function)
key를 넣으면 hash 값을 반환하는 함수
단방향성과 충돌저항성을 동시에 가져야 좋은 해시함수
단방향성 => key으로 hash 값을 찾기 쉽지만, 그 반대는 어렵다
충돌저항성 => 충돌이 자주 발생 안한다.
구조
저장
key 입력 => 해쉬 코드 함수로 hash 값 반환 => 해당 주소의 저장공간에 데이터 저장
탐색
key 입력 => 해쉬 코드 함수로 hash 값 반환 => 해당 주소의 저장공간의 데이터 읽음
충돌
키의 개수는 무한하지만 int의 개수는 유한하기 때문에 두개의 키가 같은 hash를 가르킬수있다.
같은 hash 값을 사용하면 같은 공간을 가르키기 때문에 에러가 일어난다!
충돌 해결법
1. 넓은 범위의 숫자를 생성 n 값을 곱하자(그래도 완벽히 해결불가)
2. Separate chaining 저장공간을 linked list로 만들어서 사용. linked list가 길어지면 검색이 느려지고 추가적 메모리 필요
3. 오픈주소 해싱
해시 테이블의 빈공간을 사용해서 해결
- 선형 조사 Linear Probing
충돌시 다음 공간을 조사 -> 비어있으면 그곳에 저장
장점:추가 메모리 X
단점:한번 충돌 -> 그 주위에 몰려있는 군집화 현상 발생, 삭제가 복잡함. - 제곱 조사(Quadratic Probing)
폭을 제곱으로 늘려가면서 공간이 비어있는지 확인 -> 군집화 해결! - 이중 해싱
해싱 함수를 두개 만들어서 충돌시 두번쨰 함수를 사용!
암호에서
hash 값만 유출되어도 찾기 힘듬
처음부터 끝까지를 입력해서 hash를 뽑아 비교해서 찾을 순 있다.
Avalanche Effect
암호학 용어. 원문(Plaintext)의 한 비트의 변화가 최종 암호문(Ciphertext)에 큰 변화를 주는 효과이다. 모든 암호에서 핵심적으로 요구되는 암호학적 특성이다. 특히 블록 암호나 단방향 해시 함수에서 주로 요구한다.
파이썬에서
파이썬에서는 딕셔너리도 hash이다.
indices 라는 추가적인 배열을 사용하여 들어온 entry의 순서를 기억해서 입력된 순서의 dict를 보장.
참고
