해시 함수는 임의의 길이를 갖는 메시지를 입력받아 고정된 길이의 해시값을 출력하는 함수예요.
저장된 자료의 양에 상관없이 원소 하나를 저장하고 검색하는 것을 상수 시간에 가능하게 하기 위해 해시 테이블이 나왔어요.
Hash 함수
임의의 길이의 데이터를 고정된 길이릐 데이터로 매핑하는 함수예요.
h(x) = x mod 13위와 같은 계산값을
좋은 해시 함수의 조건
계산이 간단해야 함.
입력 원소가 해시 테이블 전체에 고루 저장되어야 함. (해시 충돌을 막아야 한다는 말이에요)
위에서 정의한 함수에서 7과 20의 값을 입력하면 같이 7이라는 출력값이 나와요. 이때 해시 충돌이라 얘기해요
해시 충돌 해결
체이닝
같은 주소로 해싱되는 원소들을 모두 하나의 연결 리스트에 매달아서 관리, 원소를 검색할 때는 해당 연결 리스트의 원소들을 차례로 지나가면서 탐색해요
충돌을 해결할순 있어도, 모든 원소를 다시 비교하게돼 좋지 않아요.
개방 주소 방법
어떻게든 주어진 테이블 공간에서 해결해요.
따라서 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장이 없어요.
선형 조사, 이차원 조사, 더블 해싱등이 있어요.
선형 조사
가장 간단한 충돌 해결 밥법이에요.
충돌이 일어난 자리에서 i에 관한 일차 함수의 보폭으로 점프해요. (비어있는 부분을 찾아서 한칸씩 이동)
테이블의 경계를 넘어갈 경우에는 맨 앞으로 돌아가요.
채워져 있는 구간이 커지면 커질 수록 연산하는 횟수가 늘어난다는 단점이 있어요.
이차원 조사
한칸씩 이동하는 대신 보폭을 이차 함수로 넓혀가면서 봐요
i번째 해시 함수를 h(x) 에서 i^2만큼 떨어진 자리로 잡는다는 얘기에요.
특정 영역에 원소가 몰려도 그 영역을 빨리 벗어날 수 있어요.
더블 해싱
두개의 함수를 사용해요
하나의 함수는 초최의 해시값을 얻을 때, 다른 하나의 함수는 해시 충돌이 일어났을 때 이동할 폭을 얻을 때 사용해요.
두 원소의 첫 번째 해시값이 같더라도 두 번째 해시값까지 같을 확률은 매우 적으므로, 서로 다른 보폭으로 이동하게 되요.
특징
첫 번째, hash 함수는 동일한 입력값(input)에 대한 동일한 출력값(output)을 가지고 있어요
- 입력값이 바뀌지 않으면 출력값도 바뀌지 않는다는 얘기에요.
두 번째, 입력값이 살짝만 변경돼도, 출력값이 전혀 달라져요
- 눈사태 효과라고 불러요.
세 번째, hash 함수는 항상 같은 방향, 일방향으로만 움직여요.
- 출력된 결과 값을 토대로 입력값을 유추할 수 없다는 얘기에요.
전반적인 흐름
hash 함수를 토대로 패스워드 시스템을 만들게 되면, 1.유저가 패스워드를 입력함, 2.hash함수가 hasing함, 3.hash함수의 출력값을 데이터베이스에 저장의 과정을 거쳐요.
이렇게 데이터베이스에 저장되면, admin이나 이를 볼 수 있는 권한이 있는 사람이 패스워드를 봐도 암호화가 되어있기에 이를 전혀 알수 없어요.
문제점
단순히 hash 함수를 쓰면, "레인보우 테이블"이라는 해쉬값을 입력값이랑 연결해놓은 테이블을 통해 입력 값을 찾을 수 있어요. 이는 동일한 입력값에 대해 동일한 출력값을 보장하는 hash 함수의 특징 때문이에요.
Hash 함수의 한계 해결
이러한 문제점 때문에 "Salt"라는 것이 생겼어요. "Salt"는 작은 랜덤 텍스트를 얘기해요. hash함수가 hashing할 때 Salt를 붙여 해싱해요. 이를 통해 완전 랜덤한 입력, 출력값을 얻을 수 있어요.
Hash의 응용
무결성 검사에 사용될 수 있어요
- 데이터의 변조 여부를 해시값을 비교하며 검증 가능
클라우드 스토리지에서 동일한 파일 식별 및 수정된 파일을 검출할 때 사용돼요
데이터베이스에 비밀번호를 저장할 때 사용해요
블록체인, Git에 사용돼요.
댓글