Почему бы не разрешить внешнему интерфейсу предоставлять hashCode/equals для HashMap?
С TreeMap тривиально предоставить заказ Comparatorпереопределяя семантику Comparable объекты добавлены на карту. HashMaps, однако, не может контролироваться таким образом; функции, обеспечивающие значения хеш-функции и проверки на равенство, не могут быть загружены с одной стороны.
Я подозреваю, что было бы легко и полезно спроектировать интерфейс и дооснастить его 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, но я боюсь, что это обходной путь, который я пытаюсь избежать...;)
РЕДАКТИРОВАТЬ: Изменено название, чтобы больше не упоминать "Компаратор"; Я подозреваю, что это немного сбивало с толку.
РЕДАКТИРОВАТЬ: Принятый ответ по отношению к производительности; хотел бы более конкретный ответ!
РЕДАКТИРОВАТЬ: есть реализация; см. принятый ответ ниже.
РЕДАКТИРОВАТЬ: перефразировав первое предложение, чтобы более четко указать, что это боковая загрузка, я после (и не упорядочение; упорядочение не принадлежит в HashMap).
9 ответов
Немного поздно для вас, но для будущих посетителей, возможно, стоит знать, что у коллекций 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 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, А иногда у вас нет удобного ключа и вам нужно создать синтетический ключ, например, кортеж. Это может тратить больше памяти.
Как мы выполняем поиск? Помните, что наборы имеют 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.
Примечание: как отмечено во всех других ответах, 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 в качестве входных данных, поэтому интерфейс обратного вызова, отвечающий за хеширование, должен будет выполнить дополнительную проверку экземпляра. Либо это, либо класс карты должен знать класс его ключей.)
Есть такая особенность в com.google.common.collect.CustomConcurrentHashMapК сожалению, в настоящее время нет общедоступного способа установить Equivalence (их Hasharator). Возможно, они еще не закончили с этим, возможно, они не считают эту функцию достаточно полезной. Спросите в списке рассылки гуавы.
Интересно, почему этого еще не произошло, как было упомянуто в этом выступлении более двух лет назад.
Это интересная идея, но она абсолютно ужасна для производительности. Причина этого весьма фундаментальна для идеи хеш-таблицы: на порядок нельзя положиться. Хеш-таблицы работают очень быстро (с постоянным временем) благодаря тому, как они индексируют элементы в таблице: путем вычисления псевдо-уникального целочисленного хэша для этого элемента и доступа к этому расположению в массиве. Это буквально вычисление места в памяти и непосредственное хранение элемента.
Это контрастирует с сбалансированным бинарным деревом поиска (TreeMap), который должен начинаться с корня и проходить до нужного узла каждый раз, когда требуется поиск. В Википедии есть более глубокий анализ. Подводя итог, эффективность древовидной карты зависит от последовательного упорядочения, таким образом, порядок элементов является предсказуемым и разумным. Однако из-за снижения производительности, вызванного подходом "переход к месту назначения", BST могут обеспечить только производительность O (log (n)). Для больших карт это может сильно повлиять на производительность.
Можно наложить согласованный порядок на хеш-таблицу, но для этого необходимо использовать методы, аналогичные LinkedHashMap и ручное ведение заказа. Альтернативно, две отдельные структуры данных могут поддерживаться внутри: хеш-таблица и дерево. Таблицу можно использовать для поиска, а дерево - для итерации. Проблема, конечно, заключается в том, что она использует более чем вдвое больше необходимой памяти. Кроме того, вставки выполняются так же быстро, как и дерево: O(log(n)). Одновременные уловки могут немного снизить это, но это не является надежной оптимизацией производительности.
Короче говоря, ваша идея звучит очень хорошо, но если вы действительно попытаетесь ее реализовать, вы увидите, что это приведет к огромным ограничениям производительности. Окончательный вердикт звучит так (и был на протяжении десятилетий): если вам нужна производительность, используйте хеш-таблицу; если вам нужен порядок и вы можете жить с пониженной производительностью, используйте сбалансированное двоичное дерево поиска. Боюсь, что на самом деле невозможно эффективно объединить две структуры, не потеряв при этом некоторые гарантии того или другого.