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

Question

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

Я подозреваю, что было бы легко и полезно разработать интерфейс и модифицировать его в 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) { ... } 
    } 

case insensitive Map проблема приобретает тривиальное решение:

new HasharatorMap(String.CASE_INSENSITIVE_EQUALITY); 

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

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

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

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

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

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

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

Answer 1

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

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

Answer 2

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

Вы всегда можете написать хеш-функцию для класса (и часто нужно время), если вы делаете это тщательно. Это сложно сделать правильно, потому что структуры данных на основе хешей полагаются на случайное равномерное распределение хеш-значений. В Эффективной 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; 
} 

Answer 3

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

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

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

Answer 4

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

Answer 5

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

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

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

Answer 6

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

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

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

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

Answer 7

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

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

Answer 8

Немного поздно для вас, но для будущих посетителей, возможно, стоит знать, что в коллекциях commons есть 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 имеет its own начиная с 1.4).

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

Answer 9

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

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

Вы не можете использовать HashingStrategy со встроенным в HashSet или HashMap. GS Collections включает 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. И иногда у вас нет удобного ключа и вы должны создать синтетический, как кортеж. Это может потерять больше памяти.

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

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

Это показывает 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.