[알고리즘 개념] 해시 알고리즘

 

 

해시 함수

 

어떤 길이의 데이터를 입력해도 정해진 길이의 결과를 주는 함수

여기서 정해진 길이는 256 bits로 input의 길이에 관계없이 output의 길이는 일정하다.

 

 

 

해시 함수의 특징

 

- 데이터의 입력의 길이에 제한이 없다

- 결과는 정해진 256bits의 길이를 가진다

- 결과값이 중복될 가능성이 거의 없다

- 결과값을 가지고 입력값을 유추할 수 없다

 

 

해시 알고리즘

 

크기가 U인 테이블 T를 생성하고 key k를 slot h(k)에 저장하는 방식이다.

이때 key의 중복은 없어야 한다.

 

key k가 slot h(k)로 해쉬 되었다고 하며 h(k)를 key k의 해쉬 값이라고 부르고,

h()가 해쉬 함수이다.

 

slot의 크기는 무한하지 않기 때문에 h(k)의 값이 중복되어 나타날 수 있다.

이 경우 연결 리스트를 사용하여 해결하기도 하지만,

한 table에 긴 리스트가 생기게 되면 해시 테이블의 장점인 시간 복잡도가 저하되어 버린다.

 

따라서 각각의 key가 중복 없이 m개의 slot에 동이할 확률로 해쉬되며 각각의 key는 다른 key값의 해쉬값과 관계없이 해쉬되도록 해야한다.

 

 

division method

 

해쉬 함수로 사용하는 대표적인 방법이 나눗셈 방법이다.

나눗셈 방법은 간단하면서 빠른 연산이 가능한 해시 함수이다. 

하지만, 해시테이블의 크기가 정해진다는 단점이 있다.

 

multiplication method

 

숫자로 된 키가 K이고 A는 0과 1 사이의 실수일 때 곱셈법의 정의이다.

나눗셈 방법보다는 느리지만, 2진수 연산에 최적화한 컴퓨터 구조를 고려한 해쉬 함수라고 할 수 있다.

 

universal hasing

 

다수의 해시함수를 만들고, 이 해시함수의 집합 H에서 무작위로 해시함수를 선택해 해시값을 만드는 기법니다.

 

 

 

해시 테이블의 장점

 

해시 충돌이 발생할 가능성이 있음에도 해시 테이블을 사용하는 이유는 적은 리소스로 많은 데이터를 효율적으로 관리하기 위해서이다. 

해시값을 사용하여 모든 데이터를 살피지 않고 데이터 검색, 삽입, 삭제를 빠른 시간 안에 할 수 있다.

즉, 데이터 검색, 삽입, 삭제하는데 걸리는 시간 복잡도는 O(1)이다.