betacode

Руководство Java HashMap

  1. HashMap
  2. Как работает HashMap?

1. HashMap

HashMap<K,V> - это класс в Java коллекции интерфейсов и классов (Java Collection Framework), который реализует interface Map<K,V>. HashMap полностью поддерживает все функции, указанные в interface Map, включая дополнительные функции.
HashMap позволяет хранить пары ключей и значений (key & value). Ключи не могут быть продублированы.
public class HashMap<K,V> extends AbstractMap<K,V>
                      implements Map<K,V>, Cloneable, Serializable
Характеристики HashMap:
  • HashMap содержит пары ключей и значений.
  • Он может иметь один null ключ и несколько null значений.
  • HashMap не поддерживает порядок ключей.
  • Он работает на основе техники хеширования (hashing technique). (См. более подробное объяснение этой техники ниже).
Давайте рассмотрим этот простой пример, используя HashMap для имитации телефонной книги, в которой номер телефона является ключом (key), а имя владельца - значением (value). Ключи никогда не дублируются.
HashMapEx1.java
package org.o7planning.hashmap.ex;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;
 
public class HashMapEx1 {
 
    public static void main(String[] args) {
        Map<String, String> phonebook = new HashMap<String, String>();
 
        phonebook.put("01000005", "Tom");
        phonebook.put("01000002", "Jerry");
        phonebook.put("01000003", "Tom");
        phonebook.put("01000004", "Donald");
        
        Set<String> phoneNumbers = phonebook.keySet();
 
        for (String phoneNumber : phoneNumbers) {
            String name = phonebook.get(phoneNumber);
            
            System.out.println("Phone Number: " + phoneNumber + " ==> Name: " + name);
        }
    }
}
Output:
Phone Number: 01000004 ==> Name: Donald
Phone Number: 01000003 ==> Name: Tom
Phone Number: 01000005 ==> Name: Tom
Phone Number: 01000002 ==> Name: Jerry
В основном все функции HashMap соответствуют спецификации interface Map, поэтому вы можете прочитать следующую статью о Map, чтобы узнать больше о том, как использовать HashMap:
См. Также: Класс WeakHashMap - это вариант, экономящий память класса HashMap. Сопоставления, которые на самом деле не нужны, автоматически удаляются Java Garbage Collector (сборщиком мусора Java)

2. Как работает HashMap?

Разработчики Java использовали метод хеширования (hashing technique) для класса HashMap для хранения данных и повышения его производительности. Теперь давайте посмотрим, как эта техника используется в HashMap. Мы в основном анализируем,что происходит, когда мы вызываем эти методы: HashMap.put(K,V), HashMap.get(K) и HashMap.remove(key).
HashMap<K,V> управляет массивом объектов Node<K,V>, которые будут заменены другим более крупным массивом, если всем его элементам были присвоены значения.
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
Класс Node<K,V> состоит из 4 полей (field). Поле next - это ссылка на следующий объект Node. Это может быть не следующий элемент в массиве.
static class Node<K,V> implements Map.Entry<K,V> {
    int hashcode;
    K key;
    V value;
    Node<K,V> next;
}
HashMap гарантирует, что те Node, которые имеют один и тот же hashcode (хэш-код), будут иметь последовательные ссылки. Это помогает ему быстро найти все Node с одним и тем же указанным hashcode.
HashMap.put(key,value)
При вызове метода HashMap.put(key,value), HashMap будет искать Node с условием node.hashcode == hash(key). Если совпадение не найдено, массиву будет назначен новый объект Node. (См. рисунок ниже)
В противном случае HashMap быстро идентифицирует те последовательные Node, которые удовлетворяют условию node.hashcode == hash(key), и значительно сужает область поиска Node по key.
  • Если Node, соответствующий key, найден, то Node.value будет присвоено новое значение.
  • В противном случае создается новый объект Node и присваивается массиву (см. рисунок ниже).
HashMap.get(key)
При вызове метода HashMap.get(key), HashMap быстро идентифицирует последовательные Node, удовлетворяющие условию node.hashcode == hash(key), что значительно сужает область поиска Node по key. Затем он ищет Node по key и возвращает node.value, если он найден, в противном случае он возвращает null.
HashMap.remove(key)
Вывод: Метод Object.hashcode() возвращает hashcode (хэш-код) объекта, который по умолчанию генерируется JVM и редко дублируется. Подклассы класса Object могут переопределить (override) этот метод, чтобы вернуть пользовательский hashcode .
HashMap использует технику хеширования (hashing technique) дляулучшения своей производительности, потому что сравнение 2 чисел всегда быстрее, чем сравнение 2 объектов.

Руководства Java Collections Framework

Show More

Новейшие статьи

    Show More