Algorithm - Hash

Hash
Key와 Value가 쌍을 이루는 자료구조

 

Direct Address Table

해쉬에 대하여 알아보기 전에 먼저 알고 가야하는 자료구조이다.

키 값을 배열의 인덱스로 환산하여 데이터에 접근하는 자료구조인데

Direct Address Table은 key가 테이블 slot T[key]에 저장되기 때문에 테이블의 크기는 전체 키(U)개수가 된다.

중복키가 없고, 테이블의 크기가 작을 경우 사용 가능한 자료구조이다.

 

Direct Address Table는 연산속도가 매우 빠르지만 문제점이 단점이 존재한다

• 전체 키(U)를 예측해야 테이블 사이즈를 정할 수 있으며
• 전체 키(U)가 크다면 테이블에 저장하는 것은 비효율적이다
• 전체 키(U) 대비 사용하는 키(key)가 훨씬 적을 경우 공간 복잡도에서 비효율적이다

 

 

Hash의 구조

Python의 Dictionary 자료형과 같다.

키와 밸류로 구조화 되어 있는 자료구조인데 일반적으로 Key값을 Hash Function을 통해 HashCode를 내뱉고 저장공간의 사이즈로

나눠 Index를 정한 후 Value값을 저장한다.

 

왜 Hash를 쓰는가?

자바의 경우 ArrayList는 내부 인덱스를 이용해 한번에 검색이 이루어져 빠른 검색 속도를 보장하지만 데이터의 추가/삭제시 많은 데이터가 움직여야 하기에 많은 시간이 소요된다

LinkedList의 경우 추가/삭제시에 인근 노드들의 참조만 수정해주면 되기에 빠른 속도를 보장하지만 데이터를 검색할 경우 해당 노드를 찾기 위해 처음부터 순차적인 탐색을 필요로 한다. 최악의 경우 데이터가 많고 찾으려는 값이 뒤에 있을 수록 느려져 효율이 떨어지는 구조다.

 

이러한 두 자료구조의 한계를 극복할 수 있는 방법이 Hash인데, 내부적으로 배열을 사용해 데이터를 저장하기에 빠른 검색 속도를 찾는다 

즉 인덱스로 접근을 한다. 데이터 추가/삭제시에는 데이터와 연관된 고유한 숫자를 만들어낸 뒤 이를 인덱스로 사용하기에 데이터 이동이 필요 없는 구조이다.

 

Hash Function

해쉬 함수는 key를 고정된 길이의 해쉬로 변경해주는 역할을 하며 이러한 과정을 hashing이라고 한다. key를 해시함수라는 함수에 input으로 넣어 output으로 나오는 것이 해쉬이며 이 해쉬가 저장위치가 된다.

즉 HashFunction은 key를 통해 해쉬를 만드는 함수이다.

 

Hash Table

• Hash Table
  • 해쉬 함수를 사용해 키를 해시값으로 매핑
  • 이 해시값을 주소 또는 색인 삼아 데이터(value)를 키와 함께 저장하는 자료구조
  • 데이터가 저장되는 곳을 버킷, 슬롯이라 한다.
• Key
  • 고유한 값
  • hash function의 input이 된다
  • key값을 그대로 저장소의 색인으로 사용할 경우 key의 길이만큼 정보를 저장하는 공간도 마련해야 하기 때문에 고정된 길이의 해시로 변경한다
  • key길이가 각각 다를 수 있기 때문이다
• Value
  • 저장소에 최종적으로 저장되는 값으로 hash와 매칭되어 저장되어진다

 

해쉬테이블은 key-value가 1:1 매핑되어 있기 때문에 삽입, 삭제, 검색의 과정에서 모두 평균적으로 O(1)의 시간복잡도를 가진다

 

Hash의 단점

• 해시간의 충돌이 발생할 수 있다
• 순서/관계가 있는 배열에는 어울리지 않음
• 공간 복잡도 부분에서 떨어진다
  • 왜냐하면 배열이기에 저장공간을 미리 만들어줘야하며, 남는 공간이 생길 수 있다
• hash function의 의존도가 높다 이는 곧 해쉬함수가 복잡하다면 hash를 구현하는 과정에서 어려움을 겪을 수 있다.

 

Hash 충돌

만일 "강아지","고양이" 두가지의 key가 존재한다고 하자

이 두개를 hash function을 통해서 해시 값을 얻었는데 hash 값이 똑같이 3으로 나왔다.

이와 같은 현상을 hash collision이라 하는데 해시를 만드는 과정에서 서로 다른 Key가 같은 해쉬로 변경된다면 같은 공간에 2개의 value가 저장되므로 key-value가 1:1 매핑되는 해시테이블의 특성을 위반한다.

 

이를 해결하는 방법으로는 2가지가 있다.

 

해결방법 1. Hash Chaining

 

 

해시 충돌이 발생했을 때 이를 동일한 저장소에 저장을 하지만 나중에 저장되는 값을 연결리스트 형태로 저장하는 방법

미리 충돌을 대비하여 많은 공간을 확보할 필요가 없다.

충돌이 일어날 때마다 새로운 공간을 만들어 연결해주면 되기 때문이다

단 같은 해쉬에 자료들이 많이 연결되면 검색할 때 효율성이 떨어진다. 

Chaining을 통해 hash table 생성시 기능들의 시간복잡도는 O(n)까지 늘어날 수 있음

 

해결방법 2.Open Addressing

 

Open Addressing(개방 주소법)을 이용해 충돌이 일어나면 비어있는 hash에 데이터를 저장하는 방법

Chaining 방법에서는 하나의 해쉬에 여러개의 value가 저장되었지만 Open Addressing에서는 무조건적으로 1개의 해쉬와 1개의 value만이 매칭 된다

 

비어 있는 해쉬를 탐색하는 방법

• 선형 탐색
  • 해쉬값에서 고정폭으로 건너뛰면서 비어있는 해쉬가 나오면 저장하게 된다
• 제곱 탐색
  • 고정폭이 아닌 1->4->9->16->... 칸씩 건너뛰면서 빈칸을 찾는다.
  • 해쉬값이 같은 해쉬들이 들어오면 많은 공간을 확보 해야한다.

 

Chaining방식과 Open-addressing 방식의 장단점

체이닝 방식은 해시충돌이 발생할 경우 연결리스트로 데이터들을 연결하기 때문에 버킷이 꽉 차더라도 데이터의 주소값이 바뀌지 않는다

개방 주소법은 다른 버킷에 데이터를 삽입하기 때문에 데이터의 주소값이 바뀐다

또한 삭제의 경우 충돌에 의해 저장된 데이터가 검색되지 않을 수 있으며 더미 노드의 개수가 일정 수치 이상이 되었을 경우 주기적으로 새로운 배열을 만들어 재해시를 해줘야 성능을 유지할 수 있다 

선형 탐색의 경우 최악의 경우일 때 해시테이블 전체를 검색해야하는 상황이 발생할 수 있다.

 

즉 체이닝은 연결리스트를 사용하여 복잡한 계산식을 개방주소법에 비해 적게 사용하지만 해시테이블이 채워질수록 성능저하가 선형적으로 발생한다

개방주소법은 포인터가 필요 없고 지정한 메모리 외 추가적인 공간도 필요없다.

삽입/삭제시 오버헤드가 적으며 저장할 데이터가 적을 때 체이닝 방식보다 상대적으로 유리하다.

 

Simple Uniform hash function

해쉬함수의 매핑을 개선을 하면 된다.

특정 값에 치우치지 않고 해쉬값을 고르게 만들어내는 해쉬가 좋은 해쉬함수라고 할 수 있다.

 

• division method
  • 가장 기본적인 해쉬 함수이며 숫자로 된 키를 해쉬테이블 크기 m으로 나눈 나머지를 해쉬값으로 변환한다.
  • 간단하며 연산속도가 빠르다
  • 너무 작은 m을 고르면 key 분포의 균일성이 깨진다
  • 해쉬의 중복을 방지하기 위해 테이블의 크기 m은 소수로 지정해서 사용한다
  • 하지만 이 방식 또한 공간복잡도를 고려하였을 때 남는 공간이 발생한다
• multiplication method
  • 숫자 키 k, A는 0<A<1 사이의 실수일 때 h(k)=(ka mod 1)*m으로 계산한다
  • 2진수 연산에 최적화된 컴퓨터 구조를 고려한 해쉬함수

• universal hasing
  • 여러개의 해쉬함수를 만들고 이 해쉬함수의 집합 H에서 무작위로 해쉬함수를 선택해 해쉬값을 만드는 기법
  • 서로 다른 해쉬함수가 서로 다른 해쉬값을 만들어 내기 때문에 같은 공간에 매핑할 확률은 자연스레 줄어들 것이다.

 

Hash 실사용 예시

• 암호 알고리즘 
  • 키와 해시값 사이에 직접적인 연관이 없기에 해쉬값만으로는 키를 복원하기 어려움
  • 보통 사용자의 아이디와 비밀번호는 통상적으로 DB에 보관된다. 로그인을 시도하면 테이블 내에 저장되어 있는 비밀번호와 일치하는지 비교하는데 이때 비밀번호를 평문이 아닌 해쉬함수를 이용한 정보를 되돌리기 어려운. 추적하기 어려운 형태로 암호화 하여 저장한다.
  • 사용자가 입력한 비밀번호를 실시간으로 해쉬하여 그 결과값을 테이블 내 저장된 암호화된 비밀번호와 비교함.
• 디지털 데이터
  • 디지털 데이터는 위변조가 쉬우므로 무결성을 확인하고 위변조를 방지하기 위한 수단이 필요하다.
  • 이 때 해쉬함수는 가장 기초적인 무결성 보장의 수단으로 사용한다.
  • 트랜잭션의 송신전후, 메세지의 해시함수 결과값을 비교해 트랜잭션을 통해 메세지나 파일에 대한 변경이 있었는지를 확인한다.
• 전자 서명
  • 전자서명 알고리즘은 메세지에 대한 암호학적 해시함수를 적용하도록 설계한다.
  • 전자서명 수행 전 해쉬함수를 적용함으로써 원본 메세지보다 상대적으로 작고 안전하는 메세지 값을 생성하여 서명을 수행하도록 한다. 이 과정을 통해 전자서명 생성과 검증에 드는 계산 시간을 단축할 수 있으며 신뢰성 또한 확보 가능하다.
• 패스워드 검증
  • 패스워드 추측 공격을 방어하기 위해 사용자가 입력한 패스워드에 해쉬함수를 여러번 수행하여 악성 사용자가 보통의 장비로 1초에 50억개의 해시값을 비교할 수 있지만 이 과정을 통해 1초에 5번정도만 비교할 수 있게 된다.
  • Password-Based Key Derivation Function 해쉬함수를 가장 많이 사용하고 권장한다
• 파일과 데이터의 식별자
  • Git 과 같은 소스 코드 관리시스템이 파일을 안전하게 관리하며 식별할 목적으로 사용된다.
  • 파일이나 디렉토리 트리구조, 생성 계정 정보 등을 기반으로 각각 해시값을 생성해 식별의 기능을 제공