세트의 증분 해싱

Question

점진적으로 요소 집합을 해시하는 좋은 방법은 무엇입니까? 요소가 임의의 순서로 추가 및 제거 될 수 있고 같은 세트가 동일한 해시를 갖도록이 작업이 수행되어야합니다. 그 의도는 세트 모음에서 세트 또는 그 약간의 수정을 신속하게 찾을 수있게하려는 것입니다. 합성 운영자 여기

에 벡터 공간의 접근 방식에

이 작동하지 않습니다 무언가이다. b 비트 정수는 GF (2)에 대한 벡터 공간 V로 생각할 수 있습니다. 여기서 XOR 연산자 (예 : 10 + 11 = 01)이고 0 또는 1에 의한 곱셈은 구성 요소 논리 AND (예 : 1 * 10 = 10, 0 * 10 = 00). 요소를 b 비트 정수 E = {e_1, ..., e_b}로 무작위 (그러나 고정) 매핑 한 다음 요소의 해시를 합산하여 집합의 해시를 계산할 수 있습니다. 그렇게 할 때, E가 벡터 공간 V의 기초를 형성하도록해야한다. 그렇지 않으면 해시가 b 비트 정수의 모든 값을 사용할 수 없습니다.

이 기법의 문제점은 E- 기반의 사용 하위 집합에 베이시스 벡터 e_i에 대해 0이 아닌 첫 번째 구성 요소가 없다면 결과 해시가 홀수가 될 수 없다는 것입니다. 비슷한 문제는 사용중인 기본 벡터의 하위 집합에 따라 달라집니다. 요약하면 XOR은 집합의 해시를 찾는 데 사용해서는 안됩니다. 정상적인 합계 +를 사용하는 것이 더 나은 것은 아닙니다.

Answer 1

한 가지 해결책은 각 노드가 해당 노드를 루트로하는 하위 트리의 결합 된 해시 (항상 왼쪽 자식 해시와 올바른 하위 해시가있는 현재 노드 해시 결합)를 포함하도록 빨간색 - 검정 트리를 늘리는 것입니다. 이렇게하면 일정 시간 (루트 노드의 해시)에있는 모든 요소의 해시를 찾을 수 있지만 그렇지 않은 경우에는 빨강 - 검정 트리의 속성에 영향을 미치지 않습니다. 업데이트 규칙이 데이터 구조의 사용자에 의해 지정된 노드의 계층 적 정보를 자동으로 업데이트 할 수있게하는 일반적인 빨강 - 검정 트리 구현을 만들 수 있습니다. 빨강 - 검정 나무는 균형을 조정할 때 회전 할 수 있기 때문에 해시 조합 함수가 연관성이 있어야 함을 의미합니다. Tillich와 Zémor의 "Hashing with SL2"논문에서 연관 해시 조합 기능 (행렬 곱셈)이있는 해시 함수를 찾을 수 있습니다. 나는 이것이 받아 들일만한 성능을 가지고 있는지 확실하지 않다.