Использование альтернативного сравнения в HashSet

Question

Я наткнулся на эту проблему при создании HashSet [Array [Byte]] для использования в виде HatTrie.

По-видимому, стандартный метод equals() для массивов проверяет подлинность. Как я могу предоставить HashSet альтернативный Comparator, который использует .deepEquals() для проверки того, содержится ли элемент в наборе?

В принципе, я хочу, чтобы это испытание пройти:

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"))   
    } 
} 

Я не могу посильнее завернуть Array [Byte] на другой объект, поскольку есть много из них. За исключением написания новой реализации HashSet для этой цели есть ли что-нибудь, что я могу сделать?

Answer 1

Мутируемые структуры данных, такие как массивы, противопоказаны для использования в тех местах, где используется хеш-код. Это связано с тем, что структура данных может меняться, тем самым изменяя хэш-код данных, тем самым делая доступ к данным неточным.

Например, предположим, что у меня есть двоичное дерево для хранения элементов на основе их хеш-кода. Если хэш четный, я сохраняю данные с левой стороны, если нечетно с правой стороны. Затем я разделяю хэш на два и повторяю процесс до тех пор, пока хеш не будет равен 0, после чего я буду хранить данные в узле.

Теперь я использую эту структуру в качестве базы для HashSet, а затем храните массив на ней. Массив имеет четный хэш-код, поэтому он идет в левую часть дерева. Давайте проигнорируем его точное положение.

Позже я меняю массив, а затем просматриваю его на множестве. Теперь хеш-код нечетный, и я смотрю на правую сторону дерева и, следовательно, не могу его найти, даже если он хранится в дереве - только на другой стороне.

Итак, не используйте массивы с коллекциями на основе хэшей. Конечно, это не ответит на ваш вопрос.

Что касается вашего вопроса, вам придется подклассировать HashSet, а затем переопределить метод equals. Я не знаю, является ли HashSet окончательным или потомком из запечатанного класса, поэтому я не знаю, является ли это жизнеспособным.

Другим вариантом будет создание альтернативного метода сравнения - без имени равно или "==", основанного исключительно на deepEquals, а затем с помощью метода Pimp My Class, чтобы добавить его в HashSet.

Редактировать

я средний подкласс HashSet, но я не обратил должного внимания на этот вопрос. Я думал, что вы сравниваете весь HashSet, а не просто используете contains. Вы можете сделать это:

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, похоже, указывают, что он должен работать. Я думаю, что это может иметь какое-то отношение к боксу, но я не совсем понимаю, что - или у меня было бы это работать. :-)