Algorithm Study (해시)
이전내용 링크
10. 해시(해시 함수)
특정 자료에 빠르게 접근 하기 위한 함수
Key-Value 개념으로 Key 값을 통해 Value에 접근한다.
10-1. Direct Addressing Table
테이블에 Key값 을 인덱스로 저장하는 방법이다.
예로 Value 값이 100이라면 배열의 인덱스가 100인 위치에 Key 값을 저장하고 포인터로 데이터(Value)에 연결한다.
같은 값이 존재하지 않는다고 가정하면(같은 값을 가지는 경우 충돌,Collision 이 발생한다)
데이터의 탐색, 저장, 삭제, 갱신 모두 상수 시간 O(1)에 처리가 가능하다.
하지만 Key값의 크기만큼 배열이 할당 되기 때문에 데이터의 개수가 적고 값이 큰 경우에 메모리 낭비가 발생한다.
10-2. Hash Table
Key값을 테이블에 저장할 때 특정 함수(이를 해시 함수라고 부른다)를 사용하여 저장하는 방법이다.
key 값을 k라 할때 해시 함수 h()를 사용한 값을 h(k)로 표현하며 k의 해시값이라고 부른다.
Direct Addressing Table에 비해 메모리 낭비가 적다.
10-3. 충돌(Collision)
해시 함수를 사용하여 해시값을 출력할 때, 서로 다른 두개의 입력에 대해 동일한 해시 값을 갖는 경우 해시 충돌이 발생했다고 표현 한다.
해시 충돌 확률로 해시 함수를 판단한다.
충돌확률이 높을 수록 데이터를 구분하기 어려워지고 검색 비용이 증가한다.
해시 함수가 무한한 가짓수의 입력을 받아 유한한 가짓수의 출력값을 생성하는 경우 비둘기집 원리*에 의해 해시 충돌은 항상 발생한다. 따라서 해시 충돌은 완전히 방지 할 수 없고 충돌을 허용하되 최소화 하는 여러 기법이 존재한다.
충돌 방지 기법으로는
체이닝(Chaining), 좋은 해시 함수 만들기 등의 방법을 사용한다.
이 외에도 Open Addressing 기법 등이 있으나 알고리즘 공부에서는 Key-Value 쌍의 자료구조 정도로 이해하면 될것 같다.
* 비둘기집 원리 : n+1개의 물건을 n개의 상자에 넣을때 적어도 하나의 상자에는 두개 이상의 물건이 들어있다는 원리
귀류법 증명(귀류법, 어떤 명제가 참임을 증명하려 할 때, 결론의 부정이 모순임을 보여 명제가 타당함을 보이는 방법)
n개의 비둘기집과 n+1마리의 비둘기가 있다고 가정
명제 : 어떤 비둘기 집에는 두마리 이상의 비둘기가 있다.
결론 부정 : 모든 비둘기 집에는 한마리 이하의 비둘기만 존재한다.
모든 비둘기 집에 한마리 이하의 비둘기만 존재하는 경우 최대 n마리의 비둘기만 존재한다. 그런데 비둘기는 n+1마리가 존재하므로 이것은 모순이다. 따라서 명제는 참이다.