해시
정의
해시 함수는 길이가 있는 모든 데이터에 대해 고정 길이의 데이터에 매핑하는 함수를 의미합니다. 이러한 해시 함수를 적용하여 나온 고정 길이의 값을 해시 값으로합시다. 해시 코드, 해시 아일랜드 (섬), 체크 아일랜드라고도합니다.
해시 함수는 일반적으로 덜 복잡한 알고리즘으로 구현되므로 상대적으로 CPU, 메모리 등과 같은 시스템 리소스를 소비하는 특성을 가지고 있습니다. 동일한 입력 값에 대해 동일한 출력이 보장되며,이 출력은 가능한한 균일하게 분포되는 특성을 가지고 있습니다. 또한 특수 목적을 위해 해시 값을 생성하고 동일한 입력에 대해 다른 출력 값을 가질 수 있는 원본의 다른 값을 입력하는 해시 함수가 있습니다.
해시 함수는 일반적으로 입력 값보다 출력 값의 범위가 좁기 때문에 입력의 차이에도 불구하고 동일한 값이 거의 출력되지 않을 때 존재합니다. 세부 원칙은 비둘기 집의 원칙과 생일을 나타냅니다. 이러한 경우를 충돌이라고합니다. 원칙적으로 해시 함수는 이러한 피할 수없는 충돌을 제외하고는 의도적으로 충돌을 계산할 수 없습니다. 간단한 설명은 위키 백과의 충돌 저항 부분을 나타냅니다.
이러한 속성에 의해 지원되고 다양한 목적으로 설계된 해시 함수가 있으며 다음과 같은 다양한 분야에서 매우 유용하게 사용됩니다.
해시를 이용한 데이터 구조
해시 값을 인덱스에 사용하여 빠른 검색, 정렬없이 빠른 삽입을 허용하는 데이터 구조입니다.
해시는 목록을 사용하는 것과 동일한 접근법이지만 색인 개념이 추가됩니다.한 번 충분한 공간을 할당 받고 다음 해시 함수를 사용하여 고유한 색인을 만듭니다. 그리고 이 독특한 색인과 일치하는 위치에 데이터를 저장합니다.
해시 함수가 나무 위키라는 단어에 적용되고 색인이 생성 될 때 목록 2642 색인에 나무 위키를 저장하는 방법의 예입니다. 해시 함수는 항상 동일한 해시 값을 반환하므로 트리 위키에 들어가면 항상 2642와 색인을 찾을 수 있으므로 정렬하지 않고 즉시 찾을 수 있습니다. 그러나 이러한 목적으로 사용되는 해시 함수는 해시 값을 계산하는 비용이 기존 검색 알고리즘보다 훨씬 적어야 한다는 전제 조건을 가지고 있습니다. 그렇지 않으면 이러한 방법을 사용하는 것은 의미가 없습니다.
해시 값이 충돌하는 경우와 동일한 색인이 때때로 생성됩니다. 예를 들어 해시 함수에 나중에 위키위키라는 단어를 입력하고 2642로 색인을 나오면 나무 위키와 같은 색인을 갖게 됩니다. 이 경우 일반적으로 사용되는 두 가지 방법이 있습니다. 하나는 목록의 각 색인을 연결 목록으로 만들고 다음 색인의 빈 위치에 배치하는 오픈 주소 방법이며, 새로운 입력이 획득 될 때마다 분리 연결이 있습니다.
이 충돌을 해결해도 충돌 성능을 막을 수 없기 때문에 수용률이 일정량을 초과하면 처음부터 목록 자체의 크기를 재조정하는 방법을 사용할 수 있습니다. 그런데 이 과정 자체가 굉장히 비싼 과정이기 때문에 실시간으로 빨리 처리할 수는 없습니다. 이렇게 되면 또 다른 큰 목록을 만들어서 점차적으로 적기에 이동하는 확장 방식도 있지만, 이동하는 기존 테이블을 제거하는 방식도 있습니다. 그런데 이 경우에 기억이 훨씬 더 많이 쓰이는 거죠.
또는 해시의 비트 수를 증가시키는 몇 가지 방법; 항목 수가 적을 때 비트 수는 1 비트 증가하며, 짧은 (덜 비트) 해시와 작은 스토리지를 사용하는 빈번한 충돌로 스토리지가 두 배가됩니다. 그리고 점차적으로 확장된 공간으로 항목을 전송함으로써 충돌을 줄일 수 있습니다. 분산 데이터베이스에서 데이터의 일관성을 유지하기 위해 일관된 망설임이라고합니다.
데이터가 기본적으로 정렬되지 않은 상태로 저장되기 때문에 정렬된 순서로 액세스하는 데 비용이 많이 들고 우회할 때도 잘못된 값이 많이 들고 실제 데이터 수를 우회하는 것보다 비용이 많이 들고 임계점을 많이 봐야 한다면 실제 데이터보다 더 많은 메모리를 사용할 것입니다.