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

С 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) libs? (Пробовал Google, не повезло.)

EDIT: Хорошее обходное решение, представленное hazzen, но я боюсь, что это обходной путь, который я пытаюсь избежать...;)

EDIT: Изменено название, чтобы больше не упоминать "Компаратор"; Я подозреваю, что это было немного запутанно.

EDIT: принятый ответ относительно производительности; хотел бы получить более конкретный ответ!

EDIT: существует реализация; см. принятый ответ ниже.

EDIT: перефразировав первое предложение, чтобы более четко указать, что это боковая загрузка, которую я после (и не заказываю, порядок не принадлежит HashMap).

Ответ 1

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

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

Ответ 2

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

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

Но да, в основном идея звучит.

Ответ 3

Немного поздно для вас, но для будущих посетителей, возможно, стоит знать, что коллекторы коллекций имеют AbstractHashedMap (в 3.2.1 и с дженериками в 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.1 как Java имеет свой собственный с версии 1.4).

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

Ответ 4

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)));

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

Как мы выполняем поиск? Помните, что наборы имеют contains(), но не get(). UnifiedSetWithHashingStrategy реализует Pool в дополнение к 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.

Ответ 5

Примечание. Как отмечено во всех других ответах, 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;
}

Ответ 6

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

Ответ 7

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

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

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

Ответ 8

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

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

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

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

Ответ 9

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

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