Почему бы не разрешить внешнему интерфейсу предоставлять hashCode / equals для HashMap?

https://stackoverflow.com/questions/214136

03-07-2019
|

Вопрос

С помощью TreeMap легко создать пользовательский Comparator , переопределяя семантику, предоставляемую объектами Comparable , добавленными на карту. HashMap , однако, не может управляться таким образом; функции, предоставляющие значения хеш-функции и проверки на равенство, не могут быть загружены с одной стороны.

Я подозреваю, что было бы легко и полезно спроектировать интерфейс и преобразовать его в HashMap (или в новый класс)? Примерно так, только с лучшими именами:

  interface Hasharator<T> {
    int alternativeHashCode(T t);
    boolean alternativeEquals(T t1, T t2);
  }

  class HasharatorMap<K, V> {
    HasharatorMap(Hasharator<? super K> hasharator) { ... }
  }

  class HasharatorSet<T> {
    HasharatorSet(Hasharator<? super T> hasharator) { ... }
  }

Map без учета регистра получает тривиальное решение:

 new HasharatorMap(String.CASE_INSENSITIVE_EQUALITY);

Это было бы выполнимо, или вы видите какие-то фундаментальные проблемы с этим подходом?

Используется ли этот подход в любых существующих (не JRE) библиотеках? (Пробовал гугл, не повезло.)

РЕДАКТИРОВАТЬ: Хороший обходной путь, представленный hazzen, но я боюсь, что это обходной путь, который я пытаюсь избежать ...;)

РЕДАКТИРОВАТЬ: изменено название, чтобы больше не упоминать " Comparator " ;; Я подозреваю, что это немного сбивало с толку.

РЕДАКТИРОВАТЬ: принятый ответ по отношению к производительности; хотел бы более конкретный ответ!

РЕДАКТИРОВАТЬ: есть реализация; см. принятый ответ ниже.

РЕДАКТИРОВАТЬ: перефразировав первое предложение, чтобы более четко указать, что это боковая загрузка, которую я ищу (а не упорядочение; упорядочение не принадлежит HashMap).

Решение 4

Trove4j имеет функцию, которая мне нужна, и они называют ее стратегиями хеширования.

Их карта имеет реализацию с различными ограничениями и, следовательно, разными предпосылками, так что это не означает, что реализация для Java "quot; native" quot; HashMap будет возможно.

Другие советы

Немного поздно для вас, но для будущих посетителей, возможно, стоит знать, что у commons-collection есть AbstractHashedMap (в 3.2.2 и с обобщениями в 4.0 ) , Вы можете переопределить эти защищенные методы для достижения желаемого поведения:

protected int hash(Object key) { ... }
protected boolean isEqualKey(Object key1, Object key2) { ... }
protected boolean isEqualValue(Object value1, Object value2) { ... }
protected HashEntry createEntry(
    HashEntry next, int hashCode, Object key, Object value) { ... }

Примером реализации такой альтернативы HashedMap являются собственные IdentityMap коллекций общин (только до 3.2.2 , поскольку в Java есть свой собственный начиная с 1.4).

Это не так эффективно, как предоставление внешнего " Hasharator " к экземпляру Map . Вы должны реализовать новый класс карты для каждой стратегии хеширования (состав против наследования ...). Но это все равно приятно знать.

.NET имеет это через IEqualityComparer (для типа, который может сравнивать два объекта) и IEquatable (для типа, который может сравнивать себя с другим экземпляром).

На самом деле, я считаю, что было ошибкой определять равенство и хэш-коды в java.lang.Object или System.Object. Равенство, в частности, трудно определить таким образом, который имеет смысл с наследованием. Я продолжаю думать об этом в блоге ...

Но да, в принципе, идея здорова.

HashingStrategy - это концепция, которую вы ищете. Это интерфейс стратегии, который позволяет вам определять пользовательские реализации equals и hashcode.

public interface HashingStrategy<E>
{
    int computeHashCode(E object);
    boolean equals(E object1, E object2);
}

Вы не можете использовать HashingStrategy со встроенным HashSet или HashMap . Коллекции GS включает в себя java.util.Set с именем UnifiedSetWithHashingStrategy и java .util.Map называется UnifiedMapWithHashingStrategy .

Давайте посмотрим на пример.

public class Data
{
    private final int id;

    public Data(int id)
    {
        this.id = id;
    }

    public int getId()
    {
        return id;
    }

    // No equals or hashcode
}

Вот как вы можете настроить UnifiedSetWithHashingStrategy и использовать его.

java.util.Set<Data> set =
  new UnifiedSetWithHashingStrategy<>(HashingStrategies.fromFunction(Data::getId));
Assert.assertTrue(set.add(new Data(1)));

// contains returns true even without hashcode and equals
Assert.assertTrue(set.contains(new Data(1)));

// Second call to add() doesn't do anything and returns false
Assert.assertFalse(set.add(new Data(1)));

Почему бы просто не использовать карту ? UnifiedSetWithHashingStrategy использует половину памяти UnifiedMap и одну четверть памяти HashMap . А иногда у вас нет удобного ключа и вам нужно создать синтетический ключ, например, кортеж. Это может тратить больше памяти.

Как мы выполняем поиск? Помните, что в наборах есть contains () , но нет get () . UnifiedSetWithHashingStrategy реализует Пул в дополнение к Set , поэтому он также реализует форму get () .

Вот простой подход к обработке строк без учета регистра.

UnifiedSetWithHashingStrategy<String> set = 
  new UnifiedSetWithHashingStrategy<>(HashingStrategies.fromFunction(String::toLowerCase));
set.add("ABC");
Assert.assertTrue(set.contains("ABC"));
Assert.assertTrue(set.contains("abc"));
Assert.assertFalse(set.contains("def"));
Assert.assertEquals("ABC", set.get("aBc"));

Это демонстрирует API, но не подходит для производства. Проблема в том, что HashingStrategy постоянно делегирует String.toLowerCase () , который создает кучу строк мусора. Вот как вы можете создать эффективную стратегию хеширования для строк без учета регистра.

public static final HashingStrategy<String> CASE_INSENSITIVE =
  new HashingStrategy<String>()
  {
    @Override
    public int computeHashCode(String string)
    {
      int hashCode = 0;
      for (int i = 0; i < string.length(); i++)
      {
        hashCode = 31 * hashCode + Character.toLowerCase(string.charAt(i));
      }
      return hashCode;
    }

    @Override
    public boolean equals(String string1, String string2)
    {
      return string1.equalsIgnoreCase(string2);
    }
  };

Примечание. Я разработчик коллекций GS.

Примечание. Как отмечалось во всех других ответах, в HashMaps нет явного порядка. Они признают только «равенство». Получение порядка из структуры данных, основанной на хэше, не имеет смысла, поскольку каждый объект превращается в хеш - по сути, случайное число.

Вы всегда можете написать хеш-функцию для класса (и часто это необходимо), если вы делаете это осторожно. Это трудно сделать правильно, потому что структуры данных на основе хеш-функции полагаются на случайное, равномерное распределение хеш-значений. В Effective Java имеется большой объем текста, посвященного правильной реализации хеш-метода с хорошим поведением.

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

Простая реализация:

public class LowerStringWrapper {
    public LowerStringWrapper(String s) {
        this.s = s;
        this.lowerString = s.toLowerString();
    }

    // getter methods omitted

    // Rely on the hashing of String, as we know it to be good.
    public int hashCode() { return lowerString.hashCode(); }

    // We overrode hashCode, so we MUST also override equals. It is required
    // that if a.equals(b), then a.hashCode() == b.hashCode(), so we must
    // restore that invariant.
    public boolean equals(Object obj) {
        if (obj instanceof LowerStringWrapper) {
            return lowerString.equals(((LowerStringWrapper)obj).lowerString;
        } else {
            return lowerString.equals(obj);
        }
    }

    private String s;
    private String lowerString;
}

Хороший вопрос, спроси Джоша Блоха. Я представил эту концепцию как RFE в Java 7, но он был отброшен, я думаю, что причина была связана с производительностью. Я согласен, однако, должно было быть сделано.

Я подозреваю, что это не было сделано, потому что это предотвратит кэширование hashCode?

Я попытался создать универсальное решение Map, в котором все ключи были бы незаметно завернуты. Оказалось, что оболочка должна содержать обернутый объект, кэшированный hashCode и ссылку на интерфейс обратного вызова, отвечающий за проверки на равенство. Это, очевидно, не так эффективно, как использование класса-обертки, где вам нужно будет только кэшировать исходный ключ и еще один объект (см. Ответ hazzens).

(Я также столкнулся с проблемой, связанной с обобщениями; метод get принимает Object в качестве входных данных, поэтому интерфейс обратного вызова, отвечающий за хеширование, должен будет выполнить дополнительную проверку экземпляра. Либо это, либо класс карты должен будет знать класс его ключей.)

Это интересная идея, но она абсолютно ужасна для производительности. Причина этого весьма фундаментальна для идеи хеш-таблицы : на порядок нельзя положиться , Хеш-таблицы очень быстрые ( постоянное время ) из-за способа индексации элементов в таблице : путем вычисления псевдо-уникального целочисленного хэша для этого элемента и доступа к этому местоположению в массиве. Это буквально вычисление местоположения в памяти и непосредственное хранение элемента.

Это контрастирует с сбалансированным бинарным деревом поиска ( TreeMap ), которое должно начинаться с корня и проходить вниз до нужного узла каждый раз, когда требуется поиск. В Википедии есть более глубокий анализ . Подводя итог, эффективность древовидной карты зависит от последовательного упорядочения, таким образом, порядок элементов является предсказуемым и разумным. Однако из-за снижения производительности, вызванного «перемещением к месту назначения» Подход, BST могут обеспечить производительность только O (log (n)) . Для больших карт это может сильно повлиять на производительность.

Можно наложить согласованный порядок в хеш-таблице, но для этого необходимо использовать методы, аналогичные LinkedHashMap , и вручную поддерживать порядок. В качестве альтернативы, две отдельные структуры данных могут поддерживаться внутри: хеш-таблица и дерево. Таблицу можно использовать для поиска, а дерево - для итерации. Проблема, конечно, заключается в том, что она использует более чем вдвое больше необходимой памяти. Кроме того, вставки выполняются так же быстро, как и дерево: O (log (n)). Одновременные уловки могут немного снизить это, но это не является надежной оптимизацией производительности.

Короче говоря, ваша идея звучит действительно хорошо, но если вы действительно попытаетесь ее реализовать, вы увидите, что это приведет к огромным ограничениям производительности. Окончательный вердикт звучит так (и был на протяжении десятилетий): если вам нужна производительность, используйте хеш-таблицу; если вам нужен порядок и вы можете жить с ухудшенной производительностью, используйте сбалансированное двоичное дерево поиска. Боюсь, что на самом деле невозможно эффективно объединить эти две структуры без потери некоторых гарантий того или другого.

В com.google.common.collect.CustomConcurrentHashMap есть такая функция, к сожалению, в настоящее время нет общедоступного способа установить Эквивалентность (их хэшаратор ). Возможно, они еще не закончили с этим, возможно, они не считают эту функцию достаточно полезной. Спросите в списке рассылки гуавы .



 Интересно, почему этого еще не произошло, как было упомянуто в этом  выступлении  более двух лет назад.



	
		
			Лицензировано под: CC-BY-SA с атрибуция
			Не связан с StackOverflow