Продолжение ответов на вопросы.
1. Могут ли у разных объектов в памяти (ref0 != ref1) быть ref0.hashCode() == ref1.hashCode()?
Да, могут. Метод hashCode() не гарантирует уникальность возвращаемого значения.
2. Могут ли у разных объектов в памяти (ref0 != ref1) быть ref0.equals(ref1) == true?
Да, могут. Для этого в классе этих объектов должен быть переопределен метод equals().
Если используется метод Object.equals(), то для двух ссылок x и y метод вернет true тогда и только тогда, когда обе ссылки указывают на один и тот же объект (т.е. x == y возвращает true).
3. Могут ли у разных ссылок на один объект в памяти (ref0 == ref1) быть ref0.equals(ref1) == false?
Нет, не может. Метод equals() должен гарантировать свойство рефлексивности: для любых ненулевых ссылок x метод x.equals(x) должен возвращать true.
4. Есть класс Point{int x, y;}. Почему хэш-код в виде 31 \* x + y предпочтительнее чем x + y?
Множитель создает зависимость значения хэш-кода от очередности обработки полей, а это дает гораздо лучшую хэш-функцию.
5. Если у класса Point{int x, y;} «правильно» реализовать метод equals (return ref0.x == ref1.x && ref0.y == ref1.y), но сделать хэш-код в виде int hashCode() {return x;}, то будут ли корректно такие точки помещаться и извлекаться из HashSet?
HashSet использует HashMap для хранения элементов (в качестве ключа используется сам объект). При добавлении элемента в HashMap вычисляется хэшкод и позиция в массиве, куда будет вставлен новый элемент. У всех экземпляров класса Point одинаковый хэшкод, что приводит в вырождению хэш-таблицы в список. При возникновении коллизии осуществляется проверка на наличие уже такого элемента в текущем списке:
e.hash == hash && ((k = e.key) == key || key.equals(k))Если элемент найден, то его значение перезаписывается. В нашем случае для разных объектов метод equals() будет возвращать false. Соответственно новый элемент будет добавлен в HashSet. Извлечение элемента также будет осуществляться успешно.
Но производительность такого кода будет низкой и преимущества хэш-таблиц использоваться не будут.
6. equals() порождает отношение эквивалентности. Какими из свойств обладает такое отношение: коммутативность, симметричность, рефлексивность, дистрибутивность, ассоциативность, транзитивность?
Метод equals() должен обеспечивать:
x и y метод x.equals(y) должен возвращать true тогда и только тогда, когда y.equals(x) возвращает true);x метод x.equals(x) должен возвращать true.);x, y и z, если x.equals(y) возвращает true и y.equals(z) возвращает true, тогда и x.equals(z) должен возвращать true).Также есть ещё два свойства: постоянство и неравенство null.
7. Можно ли так реализовать equals(Object that) {return this.hashCode() == that.hashCode()}?
Строго говоря нельзя, поскольку метод hashCode() не гарантирует уникальность значения для каждого объекта.
Однако для сравнения экземпляров класса Object такой код допустим, т.к. метод hashCode() в классе Object возвращает уникальные значения для разных объектов (вычисления основаны на использовании адреса объекта в памяти).
8. В equals требуется проверять, что аргумент (equals(Object that)) такого же типа как и сам объект. В чем разница между this.getClass() == that.getClass() и that instanceof MyClass?
Оператор instanceof сравнивает объект и указанный тип. Его можно использовать для проверки является ли данный объект экземпляром некоторого класса, либо экземпляром его дочернего класса, либо экземпляром класса, который реализует указанный интерфейс.
getClass() = ... проверяет два типа на идентичность.
Для корректной реализации контракта метода equals() необходимо использовать точное сравнение с помощью getClass().
9. Можно ли реализовать метод equals класса MyClass вот так: class MyClass {public boolean equals(MyClass that) {return this == that;}}?
Реализовать можно, но данный метод не переопределяет метод equals() класса Object, а перегружает его.
10. Будет ли работать HashMap, если все ключи будут возвращать int hashCode() {return 42;}?
Да, будет. Но тогда хэш-таблица вырождается в связный список и теряет свои преимущества.
1. Зачем добавили HashMap, если уже был Hashtable?
Класс Hashtable был введен в JDK 1.0 и не является частью Java Collection Framework. Методы класса Hashtable синхронизированы, что обеспечивает потокобезопасность, но это приводит к снижению производительности, поэтому и был введен класс HashMap, методы которого не синхронизированы.
Помимо этого класс HashMap обладает некоторыми другими отличиями: например, позволяет хранить один null ключ и множество null значений.
2. Согласно Кнуту и Кормену существует две основных реализации хэш-таблицы: на основе открытой адресацией и на основе метода цепочек. Как реализована HashMap? Почему так сделали (по вашему мнению)? В чем минусы и плюсы каждого подхода?
Класс HashMap реализован с использованием метода цепочек, т.е. каждой ячейке массива соответствует свой связный список и при возникновении коллизии осуществляется добавление нового элемента в этот список.
Для метода цепочек коэффициент заполнения может быть больше 1, с увеличением числа элементов производительность убывает линейно. Такие таблицы удобно использовать, если заранее неизвестно количество хранимых элементов, либо их может быть достаточно много, что приводит к большим значениям коэффициента заполнения.
Среди методов открытой реализации различают:
Основные недостатки структур с методом открытой адресации:
Основное преимущество хэш-таблицы с открытой адресацией - это отсутствие затрат на создание и хранение объектов списка. Также проще организовать сериализацию/десериализацию объекта.
3. Сколько переходов по ссылкам происходит, когда вы делаете HashMap.get(key) по ключу, который есть в таблице?
Возможно, я неправильно понял этот вопрос. За переходы по ссылке в данном ответе я считаю вызовы методов.
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}Рассмотрим первый случай, когда ключ равен null: выполняем метод getForNullKey().
private V getForNullKey() {
if (size == 0) {
return null;
}
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}В цикле foreach проходимся по списку значений для ключа и возвращаем нужное значение. Таким образом, получаем 1 переход.
Второй случай: ключ не равен null. Выполняем метод getEntry(key).
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}Вычисляется хэш-код ключа (метод hash(key)), затем определяется индекс ячейки массива, в которой будем искать значение (метод indexFor(hash, table.length)).
После того, как нашли нужную пару "ключ-значение" возвращаем значение (метод entry.getValue()). Таким образом, получаем 4 перехода.
4. Сколько создается новых объектов, когда вы добавляете новый элемент в HashMap?
Один новый объект статического вложенного класса Entry<K,V>.
5. Как работает HashMap при попытке сохранить в нее два элемента по ключам с одинаковым hashCode, но для которых equals == false?
По значению hashCode вычисляется индекс ячейки массива, в список которой будет происходить добавление элемента. Перед добавлением осуществляется проверка на наличие уже элементов в этой ячейке. Если элементов нет, то происходит добавление. Если возникает коллизия, то итеративно осуществляется обход списка в поисках элемента с таким же ключом и хэш-кодом. Если такой элемент найден, то его значение перезаписывается, а старое - возвращается. Поскольку в условии сказано, что добавляемые ключи - разные, то второй элемент будет добавлен в начало списка.
6. HashMap может выродиться в список даже для ключей с разным hashCode. Как это возможно?
Это возможно в случае, если метод, определяющий номер ячейки массива по hashCode будет возвращать одинаковое значение.
7. Какое худшее время работы метода get(key) для ключа, которого нет в таблице (O(1), O(log(N)), O(N), O(N*log(N)), O(N*N))?
O(N). Худший случай - это поиск ключа в таблице, вырожденной в список, перебор ключей которой занимает линейно пропорциональное время количеству хранимых элементов.
8. Какое худшее время работы метода get(key) для ключа, который есть в таблице (O(1), O(log(N)), O(N), O(N*log(N)), O(N*N))?
O(N). Аналогичные рассуждения, что и для предыдущего вопроса.
9. Объясните смысл параметров в конструкторе HashMap(int initialCapacity, float loadFactor).
int initialCapacity - исходный размер HashMap (количество корзин в хэш-таблице в момент её создания).
float loadFactor - коэффициент заполнения HashMap. Равен отношению числа хранимых элементов в таблице к её размеру. Является мерой заполнения таблицы элементами, при превышении которой происходит автоматической перехеширование.
10. В чем разница между HashMap и IdentityHashMap? Для чего нужна IdentityHashMap? Как может быть полезна для реализации сериализации или клонирования?
IdentityHashMap - это структура данных, реализующая интерфейс Map, но использующая сравнение ссылок вместо метода equals() при сравнении ключей (значений). Другими словами, в IdentityHashMap два ключа k1 и k2 будут рассматриваться равными, если выполняется условие k1 == k2 (в стандартной реализации интерфейса Map (например, HashMap) ключи k1 и k2 считаются равными, если выполняется условие (k1 == null ? k2 == null : k1.equals(k2))).
IdentityHashMap не использует метод hashCode(), вместо которого применяется метод System.identityHashCode(Object).
Другое отличие (как следствие) заключается в более высокой производительности IdentityHashMap по сравнению с HashMap, если последний хранит объекты с дорогостоящими методами equals() и hashCode().
Одним из основных требований к использованию HashMap является неизменяемость ключа, однако это требование не распространяется на IdentityHashMap, который не использует методы equals() и hashCode().
Согласно документации, такая структура данных может применяться для реализации сериализации/клонирования. Для выполнения подобных алгоритмов программе необходимо обслуживать таблицу со всеми ссылками на объекты, которые уже были обработаны. Такая таблица не должна рассматривать уникальные объекты как равные, даже если метод equals() возвращает true.
11. В чем разница между HashMap и WeakHashMap? Для чего нужна WeakHashMap?
Перед рассмотрением WeakHashMap кратко напомню, что такое WeakReference. В Java существует 4 типа ссылок: сильные (strong reference), мягкие (SoftReference), слабые (WeakReference) и фантомные (PhantomReference). Особенности каждого типа ссылок связаны с работой Garbage Collector. Если объект можно достичь только с помощью цепочки WeakReference (то есть на него не ссылаются сильные и мягкие ссылки), то данный объект будет отмечен для удаления. Хорошая статья с подробным описанием каждого типа ссылок - Understanding Weak References.
WeakHashMap - это структура данных, реализующая интерфейс Map и основанная на использовании WeakReference для хранения ключей. Таким образом, пара "ключ-значение" будет удалена из WeakHashMap, если на объект-ключ более не имеется сильных ссылок.
В качестве примера использования такой структуры данных можно привести следующую ситуацию: допустим имеются объекты, которые необходимо расширить дополнительной информацией, при этом изменение класса этих объектов нежелательно либо невозможно. В этом случае добавляем каждый объект в WeakHashMap в качестве ключа, а в качестве значения - нужную информацию. Таким образом, пока на объект имеется сильная ссылка (либо мягкая), можно проверять хэш-таблицу и извлекать информацию. Как только объект будет удален, то WeakReference для этого ключа будет помещен в ReferenceQueue и затем соответствующая запись для этой слабой ссылки будет удалена из WeakHashMap.
12. В WeakHashMap используются WeakReferences. А почему бы не создать SoftHashMap на SoftReferences?
SoftHashMap представлена в стронних библиотеках, например, в Apache Commons.
13. В WeakHashMap используются WeakReferences. А почему бы не создать PhantomHashMap на PhantomReferences?
PhantomReference при вызове метода get() возвращает всегда null, поэтому, я думаю, создание PhantomHashMap просто невозможно. Плюс назначение такой структуры данных тяжело представить.
14. Сделайте HashSet из HashMap (используйте только множество ключей, но не множество значений).
Set<Object> keySet = new HashSet<>(map.keySet());15. Сделайте HashMap из HashSet (HashSet<Map.Entry<K, V>>).
Map<K, V> map = new HashMap<>(set.size());
for (Map.Entry<K, V> entry : set) {
map.put(entry.getKey(), entry.getValue());
}