해시 세트가 충돌을 일으킬 수있는 방법은 무엇입니까?

Question

해시 집합에 고유 요소의 인스턴스가 하나만 포함 된 경우이 경우 충돌이 어떻게 발생할 수 있습니까?

주어진 요소 중 하나만 존재하기 때문에로드 요소가 문제가 될 수 있습니까?

이것이 숙제 인 반면, 그것은 나를위한 것이 아닙니다. 나는 누군가를 과외하고있어, 나는 그들에게 그것을 설명하는 방법을 알아야한다.

Answer 1

"해시 테이블"("해시 세트"가 다양 함) 뒤에있는 일반적인 개념은 넣으려는 "키"값 (예 : 문자열)을 포함하는 여러 개체가 있다는 것입니다 컨테이너에있는 모든 항목을 검사 할 필요없이 일종의 컨테이너를 사용하고 각 "키"값으로 개별 개체를 쉽게 찾을 수 있습니다.

예를 들어 값을 정렬 된 배열에 넣은 다음 값을 찾기 위해 이진 검색을 수행 할 수 있지만 정렬 된 배열을 유지하는 것은 많은 업데이트가있는 경우 비용이 많이 듭니다.

따라서 키 값은 "해쉬"입니다. 예를 들어 문자의 ASCII 값을 모두 합하여 문자열의 "해시"인 단일 숫자를 만들 수 있습니다. (더 나은 해시 계산 알고리즘이 있지만 정확한 알고리즘은 중요하지 않으며 설명하기 쉬운 것입니다.)

이렇게하면 10 자 문자열의 경우, 어쩌면 600에서 1280까지의 범위에있을 것입니다. 자, 이것을 500으로 나누고 나머지를 취하면 0에서 499 사이의 값을 가지게됩니다. (문자열은 10 일 필요는 없습니다. 문자 - 더 긴 문자열은 더 큰 값을 더할 것이지만 나머지를 나눌 때 0에서 499 사이의 숫자로 끝납니다.)

이제 500 개의 항목 배열을 만들고 위에서 설명한대로 해시를 계산하고 해당 값을 사용하여 배열에 인덱싱합니다. 새 개체를 해당 인덱스에 해당하는 배열 항목에 배치하십시오.

그러나 (특히 순진 해시 알고리즘을 사용하면) 동일한 해시를 사용하여 두 개의 다른 문자열을 가질 수 있습니다. 예를 들어 "ABC"와 "CBA"는 동일한 해시를 가지며 배열의 동일한 슬롯으로 이동하게됩니다.

"충돌"을 처리하기 위해 몇 가지 전략이 있지만 가장 일반적인 방법은 배열 항목에서 연결된 목록을 만들고 해당 목록에 다양한 "해시 동의어"를 넣는 것입니다.

일반적으로 이러한 충돌을 최소화하기 위해 어레이를 충분히 커야하고 (해시 계산 알고리즘이 더 좋습니다.) 해시 체계를 사용하면 충돌을 절대적으로 방지 할 수있는 방법이 없습니다.

동의어 목록의 여러 항목은 동일하지 않으며 서로 다른 키 값을 갖지만 해시 값은 같습니다.

Answer 2

HashSet이 정수이고 해시 함수가 mod 4라고 가정 해 봅시다. 정수 0, 4, 8, 12, 16 등은 모두 삽입하려고하면 콜리 이어됩니다. (mod 4는 끔찍한 해시 함수이지만 개념을 설명합니다)

적절한 기능을 가정 할 때 부하 계수는 충돌 가능성과 관련이 있습니다. 내가 충돌을 처리하는 데 사용하는 전략에 의존하기 때문에 상관 관계가 있고 평등하지 않습니다. 일반적으로 부하율이 높으면 충돌 가능성이 커집니다. 네 슬롯이 있고 해시 함수로 mod 4를 사용한다고 가정하면로드 인자가 0 (빈 테이블) 일 때 충돌이 발생하지 않습니다. 하나의 요소가있을 경우 충돌 가능성은 0.25입니다. 충돌을 해결해야하기 때문에 성능이 저하됩니다.

이제 선형 프로빙을 사용한다고 가정하면 (충돌시, 다음 항목 사용 가능), 테이블에서 3 개의 항목에 도달하면 .75의 충돌 확률을 갖게되고, 가장 좋은 경우에는 다음 항목으로 이동하지만 최악의 경우 3 항목을 거쳐야하므로 충돌은 직접 액세스 대신 평균 2의 선형 검색이 필요하다는 것을 의미합니다 항목.

물론 충돌을 처리하는 더 나은 전략이 있으며 일반적으로 비병리적인 경우에는 .7의로드가 허용되지만 충돌 후에는 성능이 저하됩니다.