Внутренняя реализация java.util.HashMap и HashSet

Ответ 1

Ответ на вопрос 2 прост - да, вы можете использовать любой объект, который вам нравится. Карты, имеющие ключи типа String, широко используются, поскольку они являются типичными структурами данных для служб именования. Но в целом вы можете сопоставить любые два типа типа Map<Car,Vendor> или Map<Student,Course>.

Для метода hashcode() он как и раньше ответил - всякий раз, когда вы переопределяете equals(), вам нужно переопределить hashcode() для выполнения контракта. С другой стороны, если вы довольны стандартной реализацией equals(), вы не должны касаться hashcode() (потому что это может разорвать контракт и привести к идентичным хэш-кодам для неравных объектов).

Практическое sidenote: eclipse (и, возможно, другие IDE) также может автоматически генерировать пару решений equals() и hashcode() для вашего класса, только на основе членов класса.

Edit

За ваш дополнительный вопрос: да, точно. Посмотрите исходный код для HashMap.get(Object key); он вызывает key.hashcode для вычисления позиции (bin) во внутренней хэш-таблице и возвращает значение в этой позиции (если оно есть).

Но будьте осторожны с методами handhade hashcode/equals - если вы используете объект в качестве ключа, убедитесь, что hashcode не изменился впоследствии, иначе вы больше не найдете отображаемые значения. Другими словами, поля, которые вы используете для вычисления equals и hashcode, должны быть окончательными (или "неизменными" после создания объекта).

Предположим, что мы имеем контакт с String name и String phonenumber, и мы используем оба поля для вычисления equals() и hashcode(). Теперь мы создаем "John Doe" со своим номером мобильного телефона и сопоставляем его с его любимым магазином пончиков. hashcode() используется для вычисления индекса (bin) в хеш-таблице и того, где хранится магазин пончиков.

Теперь мы узнаем, что у него есть новый номер телефона, и мы меняем поле номера телефона объекта John Doe. Это приводит к появлению нового хэш-кода. И этот хэш-код разрешает новый индекс хэш-таблицы, который обычно не является местом, где хранился любимый магазин пончиков John Does.

Проблема ясна: в этом случае мы хотели отобразить "Джон Доу" в магазин пончиков, а не "Джон Доу с конкретным номером телефона". Поэтому мы должны быть осторожны с автогенерированными equals/hashcode, чтобы убедиться, что они действительно нужны, потому что они могут использовать нежелательные поля, вводя проблемы с HashMaps и HashSets.

Изменить 2

Если вы добавляете объект в HashSet, Object является ключом для внутренней хэш-таблицы, значение устанавливается, но не используется (только статический экземпляр объекта). Здесь реализация из openjdk 6 (b17):

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
private transient HashMap<E,Object> map;

public boolean add(E e) {
  return map.put(e, PRESENT)==null;
}

Ответ 2

Какова важность @Override public int hashcode() в HashMap/HashSet?

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

Где этот хэш-код используется внутри?

Никогда. Этот код существует, поэтому вы можете использовать карту в качестве ключа на другой карте.

Можно ли сопоставить значения с someObject (вместо String), например myMap<someObject, Object>?

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

Что нужно для выполнения всех контрактов для этого?

Класс должен реализовывать hashCode() и equals().

[EDIT]

Мы говорим, что хэш-код ключа (check!) - это фактическая вещь, против которой значение отображается в хеш-таблице?

Да.

Ответ 3

Да. Вы можете использовать любой объект в качестве ключа в HashMap. Чтобы сделать это, выполните следующие шаги.

• Переопределить равные.

• Переопределить hashCode.

Контракты для обоих методов очень четко указаны в документации java.lang.Object. http://java.sun.com/javase/6/docs/api/java/lang/Object.html

И да, метод hashCode() используется внутри HashMap, и поэтому возвращение к правильному значению важно для производительности.

Вот метод hashCode() из HashMap

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

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

Ответ 4

Хеширующие контейнеры, такие как HashMap и HashSet, обеспечивают быстрый доступ к элементам, хранящимся в них, разбивая их содержимое на "ведра".

Например, список номеров: 1, 2, 3, 4, 5, 6, 7, 8, сохраненный в List, будет выглядеть (концептуально) в памяти примерно так: [1, 2, 3, 4, 5, 6, 7, 8].

Сохранение того же набора чисел в Set будет выглядеть примерно так: [1, 2] [3, 4] [5, 6] [7, 8]. В этом примере список был разделен на 4 ведра.

Теперь представьте, что вы хотите найти значение 6 как из List, так и Set. Со списком вам нужно будет начать с начала списка и проверить каждое значение до 6, это займет 6 шагов. С помощью набора вы найдете правильный ковш, проверьте каждый из элементов этого ведра (всего 2 в нашем примере), сделав это трехэтапным процессом. Значение этого подхода значительно увеличивает количество данных, которые у вас есть.

Но подождите, как мы узнали, с какого ведра посмотреть? Именно здесь приходит метод hashCode. Чтобы определить ведро, в котором нужно искать элемент Java-хеширующие контейнеры, вызовите hashCode, затем примените некоторую функцию к результату. Эта функция пытается сбалансировать количество ковшей и количество элементов для быстрого поиска.

Во время поиска, когда найден правильный ковш, каждый элемент в этом ковше сравнивается по одному, как в списке. Поэтому, когда вы переопределяете hashCode, вы также должны переопределить equals. Поэтому, если объект любого типа имеет как метод equals, так и hashCode, он может использоваться как ключ в Map или записи в Set. Существует контракт, который должен соблюдаться для правильного применения этих методов. Канонический текст в этом состоит из большой книги Джоша Блоха. Эффективная Java: Пункт 8: Всегда переопределять hashCode, когда вы переопределяете равно

Ответ 5

• Любой Object в Java должен иметь метод hashCode(); HashMap и HashSet не являются исключениями. Этот хеш-код используется, если вы вставляете хэш-карту/устанавливаете в другую хэш-карту/набор.
• Любой тип класса может использоваться как ключ в HashMap/HashSet. Это требует, чтобы метод hashCode() возвращал равные значения для равных объектов и что метод equals() реализован в соответствии с контрактом (рефлексивным, транзитивным, симметричным). Реализации по умолчанию из Object уже подчиняются этим контрактам, но вы можете переопределить их, если вы хотите равенство ценности вместо ссылочного равенства.

Ответ 6

Существует сложная взаимосвязь между equals(), hashcode() и хэш-таблицами вообще в Java (и .NET тоже, если на то пошло). Процитировать из документации:

public int hashCode()

Возвращает значение хэш-кода для объекта. Этот метод поддерживается в интересах хэш-таблиц, таких как java.util.Hashtable.

     

Общий контракт hashCode:

     

•   
• Всякий раз, когда он вызывается одним и тем же объектом более одного раза во время выполнения приложения Java, метод hashCode должен последовательно возвращать одно и то же целое число, если информация, используемая при равных сравнениях с объектом, не изменяется. Это целое число не должно оставаться согласованным с одним исполнением приложения на другое выполнение одного и того же приложения.  
• Если два объекта равны в соответствии с методом equals (Object), то вызов метода hashCode для каждого из двух объектов должен давать одинаковый целочисленный результат.  
• Не требуется, чтобы, если два объекта не равны по методу equals (java.lang.Object), то вызов метода hashCode для каждого из двух объектов должен производить различные целочисленные результаты. Тем не менее, программист должен знать, что создание отдельных целочисленных результатов для неравных объектов может улучшить производительность хеш-таблиц.  

     

Насколько это практически целесообразно, метод hashCode, определенный классом Object, возвращает разные целые числа для разных объектов. (Обычно это выполняется путем преобразования внутреннего адреса объекта в целое число, но этот способ реализации не требуется языком программирования Java ™.)

Линия

@Overrides public int hashCode()

просто сообщает, что метод hashcode() переопределен. Это обычно означает, что безопасно использовать тип в качестве ключа в HashMap.

И да, вы можете использовать любой объект, который подчиняется контракту для equals() и hashcode() в HashMap как ключ.

Ответ 7

Аарон Дигулла абсолютно прав. Интересная дополнительная заметка о том, что люди, похоже, не понимают, что ключевой объект hashCode() не используется дословно. Фактически, он перефразируется HashMap, т.е. Вызывает hash(someKey.hashCode)), где hash() - внутренний метод хеширования.

Чтобы увидеть это, посмотрите на источник: http://kickjava.com/src/java/util/HashMap.java.htm

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

Ответ 8

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

Ответ 9

Метод HashCode для таких классов коллекций, как HashSet, HashTable, HashMap и т.д. - Хэш-код возвращает целое число для объекта, который поддерживается для хэширования. Он реализуется путем преобразования внутреннего адреса объекта в целое. Метод хэш-кода должен быть переопределен в каждом классе, который переопределяет метод equals. Три общих контакта для метода HashCode

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

• Если он вызывается несколько раз для одного объекта, он должен возвращать постоянное целочисленное значение.

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