Рубрики

Внутренняя работа HashMap в Java

В этой статье мы увидим, как метод get и put hashmap работает внутренне. Какие операции выполняются. Как делается хеширование Как значение выбирается по ключу. Как хранится пара ключ-значение.

Как и в предыдущей статье , HashMap содержит массив Node, и Node может представлять класс, имеющий следующие объекты:

  1. int hash
  2. К ключ
  3. Значение V
  4. Узел следующий

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

Хэш

Хеширование — это процесс преобразования объекта в целочисленную форму с помощью метода hashCode (). Для лучшей производительности HashMap необходимо правильно написать метод hashCode (). Здесь я беру ключ своего собственного класса, чтобы я мог переопределить метод hashCode (), чтобы показать разные сценарии. Мой Ключ класс

//custom Key class to override hashCode()
// and equals() method
class Key
{
  String key;
  Key(String key)
  {
    this.key = key;
  }
  
  @Override
  public int hashCode() 
  {
     return (int)key.charAt(0);
  }

  @Override
  public boolean equals(Object obj)
  {
    return key.equals((String)obj);
  }
}

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

метод hashCode ()

Метод hashCode () используется для получения хеш-кода объекта. Метод hashCode () класса объекта возвращает ссылку на память объекта в целочисленной форме. Определение метода hashCode () является общедоступным родным hashCode (). Это указывает на то, что реализация hashCode () является нативной, поскольку в java нет прямого метода для извлечения ссылки на объект. Можно предоставить собственную реализацию hashCode ().
В HashMap hashCode () используется для вычисления сегмента и, следовательно, для расчета индекса.

метод equals ()

Метод equals используется для проверки того, что 2 объекта равны или нет. Этот метод предоставляется классом Object. Вы можете переопределить это в своем классе, чтобы обеспечить собственную реализацию.
HashMap использует equals () для сравнения ключа, равны ли они или нет. Если метод equals () возвращает true, они равны, иначе не равны.

Ковши

Ведро является одним из элементов массива HashMap. Он используется для хранения узлов. Два или более узла могут иметь одно и то же ведро. В этом случае структура списка ссылок используется для соединения узлов. Ковши разные по вместимости. Соотношение между ковшом и вместимостью выглядит следующим образом:

capacity = number of buckets * load factor

Один сегмент может иметь более одного узла, это зависит от метода hashCode (). Чем лучше ваш метод hashCode (), тем лучше будут использоваться ваши сегменты.

Расчет индекса в Hashmap

Хеш-код ключа может быть достаточно большим, чтобы создать массив. Сгенерированный хеш-код может находиться в диапазоне целых чисел, и если мы создадим массивы для такого диапазона, это легко вызовет исключение outOfMemoryException. Таким образом, мы генерируем индекс, чтобы минимизировать размер массива. В основном следующая операция выполняется для расчета индекса.

index = hashCode(key) & (n-1).

где n — количество сегментов или размер массива. В нашем примере я буду считать n размером по умолчанию, равным 16.

  • Изначально Empty hashMap: здесь размер hashmap принимается равным 16.
    HashMap map = new HashMap();
    

    HashMap:

  • Вставка пары ключ-значение: размещение одной пары ключ-значение над HashMap
    map.put(new Key("vishal"), 20);
    

    шаги:

    1. Рассчитать хеш-код Key {«vishal»}. Будет сгенерировано как 118.
    2. Рассчитайте индекс, используя метод индекса, это будет 6.
    3. Создайте объект узла как:
      {
        int hash = 118
      
        // {"vishal"} is not a string but 
        // an object of class Key
        Key key = {"vishal"}
      
        Integer value = 20
        Node next = null
      }
    4. Поместите этот объект в индекс 6, если там нет других объектов.

    Теперь HashMap становится:

  • Вставка другой пары «ключ-значение»: теперь, добавив другую пару,
    map.put(new Key("sachin"), 30);
    

    шаги:

    1. Рассчитать хэш-код ключа {«sachin»}. Будет сгенерировано как 115.
    2. Рассчитайте индекс, используя метод индекса, это будет 3.
    3. Создайте объект узла как:
      {
        int hash = 115
        Key key = {"sachin"}
        Integer value = 30
        Node next = null
      }
    4. Поместите этот объект в индекс 3, если там нет других объектов.
      Теперь HashMap становится:

  • В случае столкновения: теперь, добавив еще одну пару,

    map.put(new Key("vaibhav"), 40);
    

    шаги:

    1. Рассчитайте хеш-код ключа {«vaibhav»}. Будет сгенерировано как 118.
    2. Рассчитайте индекс, используя метод индекса, это будет 6.
    3. Создайте объект узла как:
       {
        int hash = 118
        Key key = {"vaibhav"}
        Integer value = 40
        Node next = null
      }
    4. Поместите этот объект в индекс 6, если там нет других объектов.
    5. В этом случае объект узла находится по индексу 6 — это случай столкновения.
    6. В этом случае проверьте с помощью методов hashCode () и equals (), что оба ключа совпадают.
    7. Если ключи совпадают, замените значение текущим значением.
    8. В противном случае подключите этот объект узла к предыдущему объекту узла через связанный список, и оба хранятся в индексе 6.
      Теперь HashMap становится:

Используя метод get ()

Теперь давайте попробуем метод get, чтобы получить значение. Метод get (K key) используется для получения значения по его ключу. Если вы не знаете ключ, то получить значение невозможно.

  • Получите данные для ключа sachin:
    map.get(new Key("sachin"));
    

    шаги:

    1. Рассчитать хеш-код ключа {«sachin»}. Будет сгенерировано как 115.
    2. Рассчитайте индекс, используя метод индекса, это будет 3.
    3. Перейти к индексу 3 массива и сравнить ключ первого элемента с заданным ключом. Если оба равны, то возвращают значение, в противном случае проверяют следующий элемент, если он существует.
    4. В нашем случае это первый элемент, а возвращаемое значение — 30.
  • Получить данные для ключа vaibahv:
    map.get(new Key("vaibhav"));
    

    шаги:

    1. Рассчитайте хеш-код ключа {«vaibhav»}. Будет сгенерировано как 118.
    2. Рассчитайте индекс, используя метод индекса, это будет 6.
    3. Перейдите к индексу 6 массива и сравните ключ первого элемента с заданным ключом. Если оба равны, то возвращают значение, в противном случае проверяют следующий элемент, если он существует.
    4. В нашем случае он не найден в качестве первого элемента, а следующий объект узла не равен нулю.
    5. Если следующий узел имеет значение null, вернуть null.
    6. Если следующий узел не является нулевым, перейдите ко второму элементу и повторяйте процесс 3, пока ключ не будет найден или следующий не будет нулевым.
  • // Java-программа для иллюстрации
    // внутренняя работа HashMap

    import java.util.HashMap;

      

    class Key {

        String key;

        Key(String key)

        {

            this.key = key;

        }

      

        @Override

        public int hashCode()

        {

            int hash = (int)key.charAt(0);

            System.out.println("hashCode for key: "

                               + key + " = " + hash);

            return hash;

        }

      

        @Override

        public boolean equals(Object obj)

        {

            return key.equals(((Key)obj).key);

        }

    }

      
    // Класс водителя

    public class GFG {

        public static void main(String[] args)

        {

            HashMap map = new HashMap();

            map.put(new Key("vishal"), 20);

            map.put(new Key("sachin"), 30);

            map.put(new Key("vaibhav"), 40);

      

            System.out.println();

            System.out.println("Value for key sachin: " + map.get(new Key("sachin")));

            System.out.println("Value for key vaibhav: " + map.get(new Key("vaibhav")));

        }

    }

    Выход:

hashCode for key: vishal = 118
hashCode for key: sachin = 115
hashCode for key: vaibhav = 118

hashCode for key: sachin = 115
Value for key sachin: 30
hashCode for key: vaibhav = 118
Value for key vaibhav: 40

Изменения HashMap в Java 8

Теперь мы знаем, что в случае коллизий хеш-объектов объекты хранятся в виде узла в связанном списке, а для сравнения ключей используется метод equals (). Это сравнение, чтобы найти правильный ключ в связанном списке, является линейной операцией, поэтому в худшем случае сложность становится O (n).
Для решения этой проблемы элементы хеширования Java 8 используют сбалансированные деревья вместо связанных списков после достижения определенного порога. Это означает, что HashMap начинается с хранения объектов Entry в связанном списке, но после того, как число элементов в хэше станет больше определенного порога, хэш изменится с использования связанного списка на сбалансированное дерево, что улучшит производительность в худшем случае с O (n) к O (войти n).

Важные моменты

  1. Сложность времени для метода «положить и получить» практически постоянна, пока перефразировка не завершена.
  2. В случае коллизии, т.е. индексы двух или более узлов совпадают, узлы объединяются списком ссылок, т.е. на второй узел ссылается первый узел, а на третий — второй, и так далее.
  3. Если данный ключ уже существует в HashMap, значение заменяется новым значением.
  4. хэш-код нулевого ключа равен 0.
  5. При получении объекта с его ключом связанный список просматривается до тех пор, пока ключ не совпадет или пока в следующем поле не будет найден ноль.

Эта статья предоставлена Вишалом Гаргом . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

Рекомендуемые посты:

Внутренняя работа HashMap в Java

0.00 (0%) 0 votes