Функция хеширования, используемая в языке Java

Question

Я знаю, что в Java есть прекрасная встроенная поддержка HashMaps или HashTables.

Кто-нибудь знает, что какого рода функции или методы хеширования используются языком Java?

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

Большое спасибо за чтение!

Answer 1

Java позволяет вам переопределить метод hashCode() для ваших Классов, чтобы использовать алгоритм хеширования, который подходит не только для вашего приложения, но и для ваших отдельных типов:

public class Employee {

   private int id;
   // Default implementation might want to use "name" for as part of hashCode
   private String name; 

   @Override
   public int hashCode() {
     // We know that ID is always unique, so don't use name in calculating 
     // the hash code.
     return id;
   }
}

Answer 2

Так же, как примечание, если вы собираетесь переопределить hashCode, вы также должны переопределить equals.

Answer 3

Орехи.

http://www.docjar.com/html/api/java/util/HashMap.java.html

Кроме того, вы всегда можете установить пороговое значение изменения размера и начальное использование памяти настолько большим, насколько вам нужно, что уменьшит время вставки, когда карта почти заполнена. Если ваша карта имеет многопоточность, вы также значительно увеличите производительность, используя ConcurrentHashmap.

Answer 4

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

Вы действительно можете переопределить метод хеш-кода для каждого объекта. Лучший способ реализовать метод хэш-кода - использовать HashcodeBuilder (который является частью инфраструктуры Commons Lang, см. Здесь:

http://commons.apache.org/lang/

Более подробную информацию о хэш-коде см. В этой статье:

http://www.ibm.com/developerworks/java/library/j-jtp05273.html

Надеюсь, это поможет.

Answer 5

Существует «hashCode / equals contract», который вы должны придерживаться, в котором говорится, что объекты, которые равны друг другу в соответствии с методом equals (), должны предоставлять одинаковое значение hashCode (). Однако не требуется, чтобы все объекты с одинаковым hashCode также были равны. Вы должны взглянуть на http://java.sun.com/javase/6/docs/api/java/lang/Object.html#hashCode(), который сообщает вам детали.

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

Я также рекомендую достать копию Effective Java и прочитать главы в hashCode / equals, чтобы полностью ее понять.

Answer 6

В общем, не стоит слишком сильно беспокоиться о хеш-функциях стандартных классов JDK. Даже если вы можете переопределить String (вы не можете), на практике это хеш-функция практически всегда «достаточно хороша». Есть, возможно, несколько исключений, например некоторые классы, такие как BigInteger и коллекции, каждый раз вычисляют свой хэш-код, циклически просматривая каждый элемент, который они содержат, что в некоторых случаях довольно неестественно, но как часто вы используете ключи для этих классов?

Для разработки хеш-кодов для ваших собственных классов вы пытаетесь распределить хэш-коды "случайным образом" по диапазону целых чисел. Для этого вам, как правило, нужно «смешать» биты последовательных полей в вашем объекте (вас может заинтересовать статья на моем веб-сайте, на которой графически показано , как хеш-код String смешивает биты ). Умножение текущего хэша на нечетное число (и, как правило, простое число), а затем добавление в хэш следующего элемента, как правило, работает достаточно хорошо в качестве первой попытки. (Однако с этим методом могут возникнуть проблемы, когда, например, объединяемые числа / хэш-коды имеют тенденцию иметь нули в своих младших битах - обычно нет практической хэш-функции, которая абсолютно гарантированно будет работать во всех случаях.)

Затем вы можете рассмотреть возможность проверки вашего хеш-кода. Создайте серию случайных объектов (или даже используйте некоторые реальные), вычислите их хеш-коды И, снизу, скажем, 16 битов хеш-кодов, а затем посмотрите, сколько коллизий вы получите. Убедитесь, что количество получаемых вами коллизий примерно соответствует количеству коллизий хешей, которое вы ожидаете получить случайно . Например, если вы взяли И из нижних 16 бит хеш-кода (& 0xffff), то после 1000 случайных объектов вы ожидаете около 8 коллизий. После 2000 года вы ожидаете около 30 столкновений.

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

Answer 7

Я знаю, что в Java есть прекрасная встроенная поддержка HashMaps или HashTables.

Полностью отсутствует синтаксис для литералов хеш-карты, я бы не сказал, что ...

В любом случае, как указывали другие, сами классы должны определять, каким должен быть их hashCode () (по умолчанию это хэш адреса памяти). Если вы реализуете свой собственный, убедитесь, что вы следуете контракту метода hashCode () (в частности, он должен соответствовать equals ()), иначе класс не будет работать для ключей в HashMap.

Вы также можете посмотреть исходный код для j ava.util.HashMap и друзей и посмотреть, как они реализованы. Например, HashMap использует массив блоков, и области могут переполняться с помощью связанного списка.

Для дальнейшего чтения вам может понадобиться взглянуть на ConcurrentHashMap, к которому могут безопасно обращаться многие потоки одновременно, и на TreeMap, который предлагает способ построения карты для ключей, которые можно упорядочить (а обязательно хешируется).

Answer 8

Что я предлагаю, если вы знаете, что вам нужны быстрые хэши, это использовать другую реализацию: попробуйте fast util (http://fastutil.dsi.unimi.it/) или trove (http://trove4j.sourceforge.net/). Они, по-видимому, быстрее, но зависит от типа.