HashSet에서 대체 비교 사용

Question

일종의 HatTrie에서 사용할 HashSet [Array [Byte]]을 만들 때이 문제를 우연히 발견했습니다.

분명히 표준은 배열에 대한 신원 확인() 메소드입니다. 어떻게 요소가 집합에 포함되어 있는지 확인하기 위해 .deepEquals()를 사용하는 대체 Comparator로 HashSet을 제공 할 수 있습니까? 그들 중 많은이 있기 때문에 내가 실행 가능하게 다른 객체에 배열 [바이트]를 포장 할 수

describe ("A HashSet of Byte Array") {  

    it("must contain arrays that are equivalent to one that has been added") { 
     val set = new HashSet[Array[Byte]]() 
     set += "ab".getBytes("UTF-8") 
     set must contain ("ab".getBytes("UTF-8"))   
    } 
} 

:

기본적으로,이 테스트를 통과합니다. 이 목적을 위해 새로운 HashSet 구현을 작성하지 않으면 할 수있는 일이 있습니까?

Answer 1

배열과 같은 변경 가능한 데이터 구조는 해시 코드가 사용되는 곳에서 사용하기에는 반대입니다. 데이터 구조가 변경되어 데이터의 해시 코드가 변경되어 데이터에 부정확하게 액세스 할 수 있기 때문입니다.

예를 들어, 해시 코드를 기반으로 요소를 저장하는 바이너리 트리가 있다고 가정 해 보겠습니다. 해시가 짝수이면 오른쪽에 홀수가 있으면 왼쪽에 데이터를 저장합니다. 그런 다음 해시를 두 개로 나누고 해시가 0이 될 때까지 프로세스를 반복합니다. 이때 노드에 데이터를 저장합니다.

이제이 구조체를 HashSet의 기반으로 사용하고 배열을 저장합니다. 배열은 해시 코드가 균등하기 때문에 트리의 왼쪽으로갑니다. 정확한 위치를 무시하자.

나중에 배열을 변경 한 다음 세트에서 찾아 봅니다. 이제 해시 코드가 이상합니다. 그리고 나무의 오른쪽을 살펴 봅니다. 그래서 나무에 저장되어 있더라도 찾을 수 없습니다 - 다른쪽에 있습니다.

따라서 해시 기반 컬렉션이있는 배열을 사용하지 마십시오. 물론 당신의 질문에 대답하지 않습니다.

질문에 대해서는 HashSet을 하위 클래스화한 다음 equals 메서드를 재정의해야합니다. HashSet이 봉인 된 클래스의 최종 클래스인지 아니면 하위 클래스인지 모르기 때문에 실행 가능한지 여부는 알 수 없습니다.

또 다른 옵션은 deepEquals를 기반으로 equals 또는 "=="으로 명명되지 않은 대체 비교 메서드를 만든 다음 Pimp My Class 메서드를 사용하여 HashSet에 추가하는 것입니다.

내 말은 서브 클래스 HashSet의를했지만 내가 질문에 충분한주의를 지불하지 않았다

편집. 나는 당신이 단지 contains를 사용하는 대신에 전체 HashSet을 비교하고 있다고 생각했다. 당신은 이것을 할 수 있습니다 :

class MyHashSet[A] extends scala.collection.mutable.HashSet[A] { 
    override def contains(elem: A): Boolean = elem match { 
    case arr : Array[_] => this.elements exists (arr deepEquals _) 
    case _ => super.contains(elem) 
    } 
} 

첫 번째 경우를 따르지 않기 때문에 실제로는 작동하지 않습니다. REPL에 대한 간단한 테스트가 제대로 작동해야한다는 것을 나타내는 것처럼 나는 여기서 정말로 잃어버린다. 나는 그것이 권투와 관련이 있을지도 모른다고 생각하지만, 나는 무엇이 진짜인지 명확하지 않다. :-)