해싱 및 데이터 압축 사용에 대한 설명

Question

해싱을 사용하는 응용 프로그램에 직면하고 있지만 여전히 작동 방식을 알 수는 없습니다. 내 문제는 다음과 같습니다. 해싱은 일부 인덱스를 생성하는 데 사용되며 인덱스를 사용하면 다른 테이블에 액세스하고 인덱스를 사용하는 모든 테이블의 값을 추가 한 후 최종 값을 얻습니다. 이것은 메모리 요구 사항을 줄이기 위해 수행됩니다. 해싱 함수에 대한 입력은 랜덤 상수 숫자와 애플리케이션의 일부 매개 변수 사이에서 XOR을 수행하는 것입니다.

이것은 일반적인 해싱 애플리케이션입니까?. 내가 이해하지 못하는 것은 해싱을 사용하는 방법입니다. 메모리 요구 사항을 줄일 수 있습니까?. 누구든지 이것을 명확히 할 수 있습니까?.

고맙습니다

Answer 1

해싱만으로는 메모리와 관련이 없습니다.

그것이 종종 사용되는 것은 해시 가능입니다. 해시블을 계산하여 작동합니다 해시시 당신이 키우고있는 것 중에서, 이것은 데이터 구조에 대한 색인으로 사용됩니다.

해싱을 사용하면 키 (문자열 등)를 정수 나 비트 세트와 같은보다 컴팩트 한 값으로 줄일 수 있습니다.

그것은 당신이 말하는 메모리 절약 일 수 있습니다. 단순한 정수의 큰 열쇠를 줄입니다.

그러나 해시는 독특하지 않습니다! 좋은 해싱 알고리즘은 충돌을 최소화하지만 고유 한 값으로 감소시키려는 의도는 아니기 때문에 불가능하므로 가능하지 않습니다 (예 : 해시가 32 비트 정수를 출력하면 해시가 2^32 고유 한 값을 가질 수 있습니다).

Answer 2

그건 블룸 필터 당신은 이야기하고 있습니까? 이것은 해시 기능을 사용하여 세트의 멤버십을 테스트하는 공간 효율적인 방법을 얻습니다. 그렇다면 설명 링크를 참조하십시오.

Answer 3

대부분의 우수한 해시 구현은 메모리 비효율적이며, 그렇지 않으면 더 많은 컴퓨팅이 관련 될 것이므로 해싱의 지점이 정확히 누락 될 것입니다.

해시 구현은 삽입, 제거 및 검색과 같은 작업을위한 지속적인 실행 시간을 제공하므로 처리 효율성에 사용됩니다.

어떤 유형이나 크기에 관계없이 모든 데이터가 항상 단일 고정 길이 형태로 표시되는 방식으로 해싱의 품질에 대해 생각할 수 있습니다.

Answer 4

수행중인 해싱이 실제 해시 테이블을 만들지 않고 문자열/메모리 블록 테이블에 인덱스를 만드는 경우 설명 할 수 있습니다. 데이터에서 동일한 문자열 (또는 메모리 시퀀스)을 20 번 사용한 다음 해시/테이블 인덱스만으로 해당 문자열의 20 인스턴스를 모두 교체하면 그러한 방식으로 데이터 압축을 달성 할 수 있습니다. 그러나 각 해시 값에 대해 해당 테이블에 실제 충돌 체인이 포함되어 있다면 방금 설명한 내용은 일어나지 않습니다. 이 경우 해싱의 이유는 압축보다는 저장된 값에 대한 빠른 액세스를 제공함으로써 실행 속도를 높이는 것일 수 있습니다.