Как сделать эффективный hashCode?

Question

У меня есть три метода hashCode, как показано ниже, и я определил их приоритет на основе их эффективности. Мне интересно, есть ли другой способ сделать более эффективный метод hashCode.

1) public int hashCode() { //terrible 
    return 5; 
    } 
2) public int hashCode() { //a bit less terrible 
    return name.length; 
    } 
3) public int hashCode() { //better 
    final int prime = 31; 
    int result = 1; 
    result = prime * result + ((name == null) ? 0 : name.hashCode()); 
    return result; 
    } 

Answer 1

Я приоритеты их на основе их эффективности

Ваш список отсортирован по возрастанию эффективности — если по «эффективности» вы имеете в виду производительность приложения, в отличие от латентности метод hashCode изолирован от всего остального. Хэш-код с плохой дисперсией приведет к линейному или почти линейному поиску через связанный список внутри HashMap, полностью аннулирующий преимущества хеш-таблицы.

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

Answer 2

Нет надежного способа гарантировать, что ваша функция hashcode является оптимальной, поскольку она измеряется двумя разными показателями.

• Эффективность - Как быстро вычислить.
• Столкновения - Какова вероятность столкновения.

Ваш

1. обеспечивает максимальную эффективность за счет столкновений.
2. Находит место где-то посередине - но все равно не хорошо.
3. Наименее эффективный, но лучший способ избежать столкновений - по-прежнему не всегда лучше.

Вы должны найти баланс самостоятельно.

Иногда это очевидно, когда существует очень эффективный метод, который никогда не сталкивается (например, enum).

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

Иногда общая функциональность вашего кода способствует вашему выбору. Скажем, вы хотите разместить File объектов в HashMap. Имеется ряд опций:

1. Используйте хэш-код имени файла.
2. Используйте хэш-код пути к файлу.
3. Используйте crc содержимого файла.
4. Используйте хэш код SHA1 дайджест содержимого файла.

Почему столкновение плохо

Одним из основных применений hashcode является при вставке объектов в HashMap. Алгоритм запрашивает хэш-код из объекта и использует это для определения того, в каком ведре помещается объект. Если хеш сталкивается с другим объектом, в этом ведре будет еще один объект, и в этом случае ведро будет расти, что затрачивает время , Если все хеши уникальны, то карта будет одним элементом для каждого ведра и, следовательно, максимально эффективной.

См. Превосходную статью WikiPedia на странице Hash Table для более глубокого обсуждения того, как работает HashMap.

Answer 3

Мой ответ идет другим путем - в основном это не ответ, а вопрос: почему вы беспокоитесь о производительности hashCode()?

Вы исчерпывающий профилирование вашего приложения и обнаружили, что есть проблема с производительностью, исходящая от одного метода на некоторых ваших объектах?

Если ответ на этот вопрос «нет» ... тогда - почему вы думаете, что вам нужно беспокоиться об этом одном методе? Почему вы думаете, что дефолт, созданный затмением, вероятно, использовался миллиарды раз в день ... для вас недостаточно?

Для объяснения причин, почему в целом очень плохая идея тратить время на такие вопросы.

Answer 4

Да, есть лучшие альтернативы.

xxHash или MurmurHash3 - универсальные алгоритмы хеширования, которые являются более быстрыми и качественными.

Answer 5

В дополнение к ценным ответы до сих пор, я хотел бы добавить некоторые другие методы, чтобы рассмотреть следующие вопросы:

---

3a):

public int hashCode() { 
    return Objects.hashCode(name); 
} 

Не много плюсов/минусов с точки зрения но немного более кратким.

---

4.) Вы должны либо предоставить дополнительную информацию о классе, о котором вы говорите, либо пересмотреть свой дизайн. Но использование класса в качестве ключа хэш-карты, когда только свойство этого класса является String, то вы можете может также иметь возможность напрямую использовать строку. Так вариант 4:

// Changing this... 
Map<Key, Value> map; 
map.put(key, value); 
Value value = map.get(key); 

// ... to this: 
Map<String, Value> map; 
map.put(key.getName(), value); 
Value value = map.get(key.getName()); 

(И если это не представляется возможным, так как «имя» из Key может измениться после того, как она была создана, вы в большей неприятности, так или иначе - смотрите следующий пункт)

---

5.) Возможно, вы можете прекомпретировать хэш-код.На самом деле, это также делается в java.lang.String классе:

public final class String 
    implements java.io.Serializable, Comparable<String>, CharSequence { 
    ... 

    /** Cache the hash code for the string */ 
    private int hash; // Default to 0 

Но, конечно, это имеет смысл только для неизменяемых классов. Вы должны знать, что использование классов mutable в качестве ключей Map является «опасным» и может привести к ошибкам согласования и должно выполняться только в том случае, если вы абсолютно уверены, что экземпляры, которые используются в качестве ключей, t изменение.

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

class Key 
{ 
    private final String name; 
    ... // Other fields... 

    private final int hashCode; 

    Key(String name, ...) 
    { 
     this.name = name; 
     ... // Other fields 

     // Pre-compute and store the hash code: 
     this.hashCode = computeHashCode(); 
    } 


    private int computeHashCode() 
    { 
     int result = 31; 
     result = 31 * result + Objects.hashCode(name); 
     result = 31 * result + ... // Other fields 
     return result; 
    } 
}