티스토리 뷰

해시 함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 알고리즘이다.

==

 

해시 함수는 주로 3가지의 목적으로 사용된다.

Fast Table Lookup

Message digests

Encryption

 

Fast Table Lookup

Fast table lookup은 해시 함수와 해시테이블을 사용해서 구현될 수 있다.

해시 테이블을 사용하는 경우 빠른 삽입, 삭제 및 조회 요소는 우선순위다. 이론적으로, 삽입, 삭제, 조회(lookup) 를 동시에 수행할 수 있다. 자, 어쨌든 해시 테이블은 무엇인가?

 

부가설명

해시 테이블은 배열인데, 해시 함수와 커플링 된 함수다. 해시 함수는 데이터를 인풋으로 가지는데 우리는 이것을 키라고 부른다. 그리고 해시 함수의 아웃풋은 해시값이라고 부른다. 해시값은 인풋 키를 해시 테이블의 특정 인덱스로 매핑시킨다. 게다가 우리는 해시 함수를 해시테이블의 어디에 주어진 키를 저장할 것인가를 결정하기 위해 사용한다. 그 후, 나중에 주어진 키가 해시 테이블의 어디에 위치하는지 찾기 위해 똑같은 해시 함수를 사용한다. 이러한 이유로, 해시 함수가 identical key에 대해 일정하게 작동하며 똑같은 아웃풋을 내는 것은 치명적이다.

해시 테이블은 모든 데이터 타입에 대해 사용할 수 있다.

 

collision이란 두 개의 키가 같은 인덱스로 해싱되는 경우다. 해시 테이블이 데이터 세트보다 크고, 좋은 해시함수를 쓰더라도, 충돌을 막을 방법을 생각해야 한다.

Collision을 막는 방법에는 두 개의 방법이 있다.

linear probing

separate chaining

 

linear probing에선 만약 키가 이전에 저장된 키로 해싱된다면 이는 테이블의 다음 이용 가능한 슬롯에 저장된다. 여기선, 한번 collision이 발생하면 또다시 collision이 발생할 가능성이 커진다. 이를 clustering이라 부르고, linear probing의 심각한 단점이다. 게다가 최악에는 삽입과 삭제 조회 시간이 O(n)이 될 수 있다.

 

separate chaining에서는 해시 테이블이 사실상 연결리스트의 포인터 배열이다. collision이 발생했을 때, 키는 동시에 적절한 연결리스트의 head에 삽입된다. O(n/k), k는 해시 테이블의 사이즈?

 

여태 본 것처럼, collision을 해결하는 것은 상당히 느리다. 그래서, 우선 collision 발생을 최소화하는 해시 함수를 골라야 한다.

 

좋은 해시 함수

키로 제공되는 모든 정보를 이용한다. (그냥 한 모든 해시값의 개수를 최대화하기 위해)

Uniformed Distributed:: 해시값은 해시테이블 상에서 고르게 퍼져있어야 한다. 이것은 collision을 발생시키는 연결리스트의 길이를 감소시킨다.

유사한 키라도 매우 다른 해시값을 발생

매우 빠른 작업을 사용하는 해시함수

 

 

해시 테이블에서는 요소의 키에 대한 해시를 계산하고, 그리고 해시값을 테이블에서 인덱스로써 사용함으로써 요소를 찾는다. 이 방법은 테이블의 각각 요소를 시퀀셜하게 맞는지 확인하는 것과 같은 방법들보다 빠르다.

 

Message digests

 

Message digest는 두 개의 데이터를 비교할 수 있게 하고, 그것들이 같은지 빠르게 결정할 수 있도록 해준다. 두 데이터를 bit by bit로 비교하는 것 대신에, 만약 각각의 데이터의 해시값이 사용 가능하다면, 해시값들을 비교할 수 있다. 만약 해시값이 다르다면, 기존의 두 데이터는 완전히 다른 것이다. 만약 해시값이 같다면 기존의 두 데이터는 거의 같다고 봐야 한다. (해시 함수가 좋다는 가정하에)

 

Message digest는 암호 해시함수, 혹은 비암호 해시함수를 사용할 수 있다. 만약 message digest의 목적이 기존의 메시지가 손상됬는지 안됐는지를 확인하는 것이라면 암호 해시함수를 사용해야 할 것이다. 만약 그냥 빠르게 하나의 파일이 다른 파일(다른 이름과 함께)과 같은지를 파악하고 싶다면, 단지 비암호 해시 함수를 사용할 수 있다.

 

Encryption

 

암호화는 데이터의 변형인데, 복호화용 비밀키 없이는 누구도 접근 불가능한 형태로 변형시킨다. 해시 함수는 암호화에서 중요한 역할을 한다. 왜냐하면, 접근 불가능한 암호화된 데이터를 발생시키고, 복호화키 없이 암호화된 데이터로부터 기존의 데이터로 복호화시킬 수 없게 만드는 것이 해시 함수 역할이기 때문이다.

 

여기서 해시 함수는 어떨 때는 mixing functions와 같은 다른 이름으로 주어진다.

 

Properties of Hash Functions

해시 함수로서 유용한 함수가 되기 위해서는, 이는 uniform distribution의 특성을 보여줘야만 한다. 어떤 해시 함수들은 또한 onewayness 속성을 가지기도 한다. 만약 해시 함수가 암호학적으로 사용되거나, 또는 키가 알려지지 않는 곳의 fast table lookup을 위해서 사용된다면 onewayness 속성은 필수사항이다.

 

Uniform Distribution

모든 좋은 해시 함수는 충돌 저항성을 가진다. 이 충돌 저항성에서 기대되는 현상은 유니크한 인풋이 유니크한 아웃풋을 제공한다는 것이다. 그런데 해시함수와 해시테이블에서 만약 인풋 아이템의 개수가 해시 테이블의 슬롯 개수보다 많다면 모든 collision을 피하기 불가능하다. 이때는 중복이 어쩔 수 없이 돼야만 한다. 이때 해시함수는 인풋 아이템 set 중 몇몇은 같은 아웃풋으로써 해시 슬롯에 배치될 것이다.

 

이렇게 collision을 피할 수 없게 되면서 제2차 목표는, 아웃풋을 다 찾아갈 수 있으면서 최대한 중복이 적게끔 구성하는것이 되겠다. 이 유사성 최소화는 중복된 체인들의 개수 분포가 고르게 일어날 때 발생한다. 다시 말하면, 아웃풋 체인들이 상응하는 인풋 아이템들로부터 똑같이 분배될 때를 말한다. 이것이 일어날 때, 우리는 아웃풋 벡터들이 uniformly distributed 됐다고 말한다.

 

One-way Functions

또 하나의 중요한 목표는, "유사한" 인풋 벡터들이 매우 다른 아웃풋 벡터들을 생산한다는 것이다. Table lookup의 경우에는, 테이블 키는 보통 자연어 문자열이거나, 인덱스 넘버거나, 또는 non-randomness를 보여줄 수 있는 또 다른 데이터이다.

Message digest 함수의 경우에, 이의 목표는 가능한 한 같은 해시값에서 두 개의 다른 메시지를 찾는 걸 어렵게 만드는 것이다. 이 특성을 가진 해시 함수는 one-way 해시 함수라고 부른다.

 

모든 해시함수가 one-wayness를 가져야 할 필요는 없지만, 모든 암호적인 애플리케이션은 가져야만 한다. 예를 들어, 키가 전화번호인 테이블의 fast table lookup을 위한 해시값은 간단하게 전화번호의 마지막 4개 숫자가 될 수 있다. 이 해시 함수는 적절하다. 왜냐하면, uniform하게 distributed 될 것이기 때문이다. 하지만 이것을 명확히는 one-way가 아니다. 왜냐하면, 이것은 특정한 해시값을 가지는 전화번호를 만들기 쉽기 때문이다.

 

참고:

해시 테이블: https://www.youtube.com/watch?v=h2d9b_nEzoA

해시 테이블: http://luyin.tistory.com/191

'DataStructure > Algorithms' 카테고리의 다른 글

해시의 충돌 및 충돌 회피 방법  (0) 2016.09.04
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함