EminentStar's Dev Wiki

기초지식키들의 전체 집합을 U라고 했을 때, 실제로 저장되는 키들의 집합은 K라고 하고 이 K는 U에 비해 상대적으로 작다. 실제 저장되는 K집합이 U에 비해 상대적으로 작기 때문에 해시테이블 T를 위해서 할당된 대부분의 공간이 낭비될 수 있다. 그래서 이렇게 사전에 저장된 키들의 집합 K가 모든 가능한 키들의 전체 집합 U에 비해 훨씬 작을 때 해시 테이블은 직접 주소 테이블보다 훨씬 작은 공간을 필요로 한다. 이때 해시 테이블의 크기를 m이라고 하고 일반적으로 |U|보다 훨씬 작다. 해싱을 이용한 방법에서는 키 k를 갖는 원소는 위치h(k)에 저장된다. 즉 키로부터 저장될 위치를 계산하기 위해 해시 함수 h를 사용한다. 여기서 h는 키들의 전체 집합 U를 해시 테이블 T[0..m-1]의 각 위치에 대..

해시 함수는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 알고리즘이다.== 해시 함수는 주로 3가지의 목적으로 사용된다.Fast Table LookupMessage digestsEncryption Fast Table LookupFast table lookup은 해시 함수와 해시테이블을 사용해서 구현될 수 있다. 해시 테이블을 사용하는 경우 빠른 삽입, 삭제 및 조회 요소는 우선순위다. 이론적으로, 삽입, 삭제, 조회(lookup) 를 동시에 수행할 수 있다. 자, 어쨌든 해시 테이블은 무엇인가? 부가설명해시 테이블은 배열인데, 해시 함수와 커플링 된 함수다. 해시 함수는 데이터를 인풋으로 가지는데 우리는 이것을 키라고 부른다. 그리고 해시 함수의 아웃풋은 해시값이라고 부른다. 해시값은 인풋 키..