문자열에 대한 상수 해시?

Question

SO에 대한 또 다른 질문은 일부 언어에서 문자열을 해시하여 테이블에서 빠른 조회를 제공하는 기능을 가져왔습니다.이에 대한 두 가지 예는 .NET의 Dictionary<>와 Python의 {} 저장소 구조입니다.다른 언어도 확실히 그러한 메커니즘을 지원합니다.C++에는 맵이 있고 LISP에는 다른 대부분의 현대 언어와 마찬가지로 이에 상응하는 맵이 있습니다.

문자열에 대한 해시 알고리즘은 일정한 시간에 수행될 수 있다는 질문에 대한 답변에서 25년의 프로그래밍 경험을 가진 한 SO 멤버와 함께 모든 것이 일정한 시간에 해시될 수 있다고 주장했습니다.내 개인적인 주장은 특정 응용 프로그램이 문자열 길이에 경계를 설정하지 않는 한 이것이 사실이 아니라는 것입니다.이는 일부 상수 K가 문자열의 최대 길이를 결정한다는 것을 의미합니다.

나는 연산을 위해 해싱 함수를 사용하는 Rabin-Karp 알고리즘에 익숙하지만 이 알고리즘은 사용할 특정 해시 함수를 지시하지 않으며 저자가 제안한 것은 O(m)입니다. 여기서 m은 길이입니다. 해시된 문자열.

이 페이지와 같은 다른 페이지도 보입니다(http://www.cse.yorku.ca/~oz/hash.html) 일부 해시 알고리즘을 표시하지만 각각은 해당 값에 도달하기 위해 문자열의 전체 길이를 반복하는 것으로 보입니다.

주제에 대해 비교적 제한적으로 읽은 바에 따르면 문자열 유형에 대한 대부분의 연관 배열은 실제로 내부적으로 일종의 트리와 함께 작동하는 해싱 함수를 사용하여 생성되는 것으로 보입니다.이는 키/값 쌍의 값 요소 위치를 가리키는 AVL 트리 또는 빨간색/검은색 트리일 수 있습니다.

이 트리 구조에서도 n이 트리의 요소 수인 세타(log(n)) 순서를 유지하려면 상수 시간 해시 알고리즘이 필요합니다.그렇지 않으면 문자열을 반복하는 추가 페널티가 발생합니다.비록 많은 문자열을 포함하는 인덱스에 대해 theta(m)이 theta(log(n))에 의해 가려지더라도, 우리가 검색하는 텍스트가 매우 클 도메인에 있다면 이를 무시할 수 없습니다.

나는 접미사 트리/배열과 Aho-Corasick이 메모리 비용을 높이기 위해 검색을 theta(m)로 낮출 수 있다는 것을 알고 있지만, 임의 길이의 문자열에 대해 상수 시간 해시 방법이 존재하는지 구체적으로 묻고 있습니다. 다른 SO 구성원이 소유권을 주장했습니다.

감사해요.

Answer 1

일반적으로 완전한 문자열 해시는 문자열의 모든 문자를 사용해야 하므로 n 문자에 대해 O(n)만큼 커져야 한다고 생각합니다.그러나 실용적인 문자열 해시의 경우 쉽게 O(1)이 될 수 있는 대략적인 해시를 사용할 수 있다고 생각합니다.

표준 해시를 계산하기 위해 항상 Min(n, 20) 문자를 사용하는 문자열 해시를 생각해 보세요.분명히 이것은 문자열 크기에 따라 O(1)로 증가합니다.안정적으로 작동할까요?도메인에 따라 다릅니다...

Answer 2

해시 함수는 모든 문자열에 대해 고유한 값을 반환할 필요가 없으며 반환할 수도 없습니다.

처음 10자를 사용하여 난수 생성기를 초기화한 다음 이를 사용하여 문자열에서 100개의 임의 문자를 추출하고 해시할 수 있습니다.이것은 일정한 시간이 될 것입니다.

상수 값 1을 반환할 수도 있습니다.엄밀히 말하면 이것은 매우 유용한 함수는 아니지만 여전히 해시 함수입니다.

Answer 3

심각한 해시 충돌 사례의 위험 없이 문자열에 대한 일반적인 상수 시간 해싱 알고리즘을 쉽게 달성할 수 없습니다.

일정한 시간이 되려면 문자열의 모든 문자에 액세스할 수 없습니다.간단한 예로 처음 6자를 사용한다고 가정해 보겠습니다.그런 다음 누군가가 와서 일련의 URL을 해시하려고 합니다.has 함수는 모든 단일 문자열에 대해 "http://"를 확인합니다.

다른 캐릭터 선택 체계에서도 비슷한 시나리오가 발생할 수 있습니다.이전 문자의 값을 기반으로 의사 무작위로 문자를 선택할 수 있지만 어떤 이유로 문자열에 "잘못된" 패턴이 있고 많은 문자열이 동일한 해시 값으로 끝나는 경우 여전히 큰 실패의 위험이 있습니다.

Answer 4

당신은 할 수 있습니다 희망 다음을 사용하면 선형 해싱 시간보다 점근적으로 짧습니다. 로프 문자열 대신 일부 계산을 건너뛸 수 있는 공유 기능이 있습니다.그러나 분명히 해시 함수는 읽지 않은 입력을 분리할 수 없으므로 "모든 것이 일정한 시간에 해시될 수 있다"는 것을 너무 심각하게 받아들이지는 않을 것입니다.

해시 함수의 품질과 필요한 계산량 사이의 절충안에서는 무엇이든 가능하며, 긴 문자열에 대한 해시 함수는 어쨌든 충돌이 발생해야 합니다.

너 해시 함수가 접두사만 보는 경우 알고리즘에서 발생할 가능성이 있는 문자열이 너무 자주 충돌하는지 확인해야 합니다.

Answer 5

무제한 길이의 문자열에 대한 고정 시간 해시 함수를 상상할 수는 없지만 실제로는 그럴 필요가 없습니다.

해시 함수를 사용하는 기본 아이디어는 해시 값의 분포를 생성하는 것입니다. 많은 문자열이 충돌할 가능성은 거의 없습니다. - 고려 중인 도메인의 경우.이 키를 사용하면 데이터 저장소에 직접 액세스할 수 있습니다.이 두 가지가 결합된 결과는 다음과 같습니다. 일정한 시간 조회 - 평균.

이러한 충돌이 발생하면 조회 알고리즘은 보다 유연한 조회 하위 전략을 사용합니다.

Answer 6

확실히 이것은 해싱이 필요한 항목에 문자열을 전달하기 전에 모든 문자열이 '인턴'되었는지 확인하는 한 가능합니다.인턴은 문자열을 문자열 테이블에 삽입하여 동일한 값을 가진 모든 인턴 문자열이 실제로 동일한 개체가 되도록 하는 프로세스입니다.그런 다음 문자열 자체를 해싱하는 대신 인턴된 문자열에 대한 (고정 길이) 포인터를 간단히 해시할 수 있습니다.

Answer 7

작년에 내가 생각해낸 다음과 같은 수학적 결과에 관심이 있으실 것입니다.

임의의 길이의 모든 문자열 집합과 같은 무한한 수의 키를 {1,2,…,b}의 숫자 집합으로 해싱하는 문제를 생각해 보세요.무작위 해싱은 먼저 H 함수 계열에서 해시 함수 h를 무작위로 선택하여 진행됩니다.

나는 모든 H 함수에 대해 확실히 충돌하는 무한한 수의 키가 항상 있다는 것을 보여줄 것입니다. 즉, 모든 H 함수에 대해 항상 동일한 해시 값을 갖습니다.

해시 함수 h를 선택하세요.집합 A={s:h(s)=y}가 무한한 해시 값 y가 하나 이상 있습니다. 즉, 무한히 많은 문자열이 충돌합니다.다른 해시 함수 h'를 선택하고 세트 A의 키를 해시합니다.집합 A'={s가 A에 있는 해시 값 y'가 하나 이상 있습니다.h'(s)=y'}는 무한합니다. 즉, 두 개의 해시 함수에서 충돌하는 문자열이 무한히 많습니다.이 인수는 여러 번 반복할 수 있습니다.H번 반복하세요.그러면 모든 문자열이 모든 H 해시 함수에서 충돌하는 무한한 문자열 세트가 있습니다.CQFD.

추가 읽기:가변 길이 문자열의 합리적인 해싱은 불가능합니다.http://lemire.me/blog/archives/2009/10/02/sensible-hashing-of-variable-length-strings-is-impossible/