JavaRush /Java блог /Архив info.javarush /HashMap и ConcurrentHashMap популярные вопросы на собесед...
furs08
11 уровень

HashMap и ConcurrentHashMap популярные вопросы на собеседованиях

Статья из группы Архив info.javarush
В моем прошлом превью я рассказывал о том “Как работает HashMap в Java”. Я рассказывал о внутренностях этого класса и о том как они вписываются в концепцию. Но когда меня спросили о HashMap и связанных с ним вещах опрашивающий не остановился только лишь на основной концепции. В ходе дискуссии затрагиваются разные направления, в итоге все сводится к тому либо вы действительно понимаете эти вещи либо нет. HashMap и ConcurrentHashMap популярные вопросы на собеседованиях - 1В этом превью я постараюсь освятить все основные темы вопросов на собеседованиях: Затрагиваемые темы:
  1. Как создать ключ для HashMap?
  2. Различия между HashMap и ConcurrentHashMap?
  3. Различия между Collections.synchronizedMap(HashMap) и HashMap?
  4. Различия между ConcurrentHashMap и Collections.synchronizedMap(HashMap)?
  5. Различия между HashMap и HashTable?
  6. Различия между HashTable и Collections.synchronizedMap(HashMap)?
  7. Влияние случайных/фиксированных значений hashCode() для ключа
  8. Использование HashMap в несинхронизированном коде многопоточных приложений
Итак приступим:
  1. Создание ключа для HashMap

    Одной из главных необходимостей является то, что мы должны возвращать значение объекта без ошибок. Правильно? В противном случае непонятно как представить себе структуру данных которую вы проектируете. Это будет невозможно использовать. Чтобы решить, что мы создали хороший ключ мы должны знать как работает HashMap. Работа HashMap построена на принципах Хеширования. Ключ в хэш-коде используются прежде всего в сочетании с методом equals(), для добавления и поиска элемента по HashMap. Если хэш-код объекта меняется на другую пару ключ – значение(key-value), то значение от карты(Map) получить практически невозможно. Данный случай называется утечкой памяти. Чтобы избежать этого ключ и карта должны быть неизменны. Это главная причина того что неизменяемые классы такие как String, Integer и остальные классы подобного рода являются хорошим выбором для создания ключа.

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

  2. Различия между HashMap и ConcurrentHashMap

    Чтобы лучше визуализировать СoncurrentHashMap нужно рассматривать этот класс как группу HashMap’ов. Чтобы брать и класть значения пар(key-value) в HashMap необходимо вычислить хэш-код и найти правильный сегмент массива Collection.Entry. В ConcurrentHashMap отличие заключается во внутренней структуре для хранения пар key-value. ConcurrentHashMap имеет дополнительную концепцию сегментов. Будет легко понять если представить, что один сегмент эквивалентен одному HashMap[концептуально]. ConcurrentHashMap разделена на множество сегментов [по умолчанию их число равно 16] при инициализации. ConcurrentHashMap похожим потокам примерно (16) получать одновременный доступ к этому сегменту, каждый поток работает одновременно с высоким параллелизмом. Отсюда, если ваша пара key-value хранится в сегменте 10 не нужно блокировать остальные 15 сегментов дополнительно. Такая структура обеспечивает очень высокий уровень параллелизма.

    HashMap и ConcurrentHashMap популярные вопросы на собеседованиях - 2

    Другими словами Concurrent HashMap использует множество замков и каждый замок управляет одним сегментом структуры. Установки данных в определенном сегменте заблокированы для получения в этом сегменте так синхронизированы операции обновления. При получении данных, чтения на лету используется без синхронизации. Если считывать данные на лету то сегмент блокируется и запись производится в синхронизированный блок.

  3. Различия между HashMap и Collection.synchronizedMap(HashMap)

    Все на самом деле просто! HashMap не синхронизирована и Collection.synchronizedMap(HashMap) возвращает упакованные методы HashMap которые являются синхронизированными get и put методами.

    Фактически, Collection.synchronizedMap(HashMap) внутренне созданного внутреннего класса SunchronizedMap содержащего пары key-value передающиеся в HashMap как аргумент. Такой пример внутренних классов ничего не меняет в первоначальных параметрах HashMap и является полностью независимым.

  4. Различия между ConcurrentHashMap и Collections.synchronizedMap(HashMap)

    Оба являются синхронизированными версиями HashMap c различиями в функциональности и внутренней структуре. Как указано выше ConcurrentHashMap состоит из внутренних сегментов, которые могут рассматриваться как независимые HashMap’ы концептуально. Все эти сегменты могу быть заблокированы отдельными потоками выполняемыми одновременно. Таким образом несколько потоков могу одновременно получить/положить пары key-value из ConcurrentHashMap без блокирования/ожидания друг друга.

    Из Collections.synchronizedMap() мы получаем синхронизированную версию HashMap и доступ в блокировании образом. Это означает то что если несколько потоков пытаются получить доступ к synchronizedMap в одно и тоже время им будет позволено взять/положить пары key-value по одному синхронизированному образу.

  5. Различия между HashMap и HashTable

    Этот вопрос также является простым. Главное различие в том что HashTable синхронизирован а HashMap нет. Если вас спросят по другим причинам то скажите им что HashTable является наследием класса (часть JDK 1.0) который был произведен в рамках коллекции реализовав интерфейс Map позже. В нем все еще есть вещи которых нету в HashMap такие к примеру как Enumerators(счётчики). Другой незначительной причиной является то что HashMap поддерживает ключ со значением null.(Отображаемый как пустая область памяти). HashTable не поддерживает ключ со значением null и вызывает исключение NullPointerException, при попытке его задать.

  6. Различия между HashTable и Collection.synchronized(HashMap)

    До сих пор вы возможно только знали об их сходствах. Оба являются синхронизированными версиями коллекций. Оба имеют синхронизированные методы внутри. Оба блокируют потоки и заставляют ждать когда можно взять/положить что-либо в коллекцию. Так в чем же различия? Хорошо! Нет основных различий для указанных выше причин. Производительность обоих одинакова. Единственное что различает их это то что HashTable наследуемый класс он получил свои дополнительные функции такие как Enumerators(счетчики).

  7. Влияние случайных/фиксированных значений для значения ключа.

    Влияние в обоих случаях будь то фиксированное значение или случайное будет иметь одинаковый результат и это необъяснимое поведение. Большое значение имеет место в HashMap где поставить пару key-value и где восстановить. Если положение объекта ключа меняется каждый раз то его положение будет рассчитываться каждый раз разными способами. Таким образом объект хранящийся в HashMap будет потерян навсегда с минимальной возможностью восстановления. Поэтому значения ключей являются неизменными и каждый раз возвращают уникальные значения.

  8. Использование HashMap в несинхронизированном коде многопоточных приложений.

    — в худшем случае это может вызвать бесконечный цикл.

    — Да.

    — Ты был прав это действительно может привести к бесконечному циклу. Ты спросишь: "Как?"

    — Хорошо! Вот причина!

    HashMap имеет концепцию повторного хеширования, когда достигает своего верхнего предела. Это процесс создания новой области памяти и копирования туда существующих элементов. Допустим Поток A положил пару key-value в Map и повторное хеширование началось, в то же время поток Б начал манипулировать с областью памяти используя операцию put(положить). Во время повторного хеширования существует возможность для создания циклической зависимости где элемент находящийся в ссылочном листе [в любой области памяти] может указывать на любой предыдущий узел в ту же область памяти. Это приведет к бесконечному циклу так как код повторного хеширования содержит в себе while(TRUE) {//получаем следующий узел} который будет работать бесконечно.

    Посмотрите внимательно на этот код содержащий метод передачи использующий операцию повторного хеширования:

    
    public Object get(Object key) {
        Object k = maskNull(key);
        int hash = hash(k);
        int i = indexFor(hash, table.length);
        Entry e = table[i];
     
        //While true is always a bad practice and cause infinite loops
     
        while (true) {
            if (e == null)
                return e;
            if (e.hash == hash && eq(k, e.key))
                return e.value;
            e = e.next;
        }
    }
    

    Подробней об этом в следующей статье. Если вы нашли статью полезной пожалуйста поделитесь с друзьями! Счастливого обучения!

Комментарии (6)
ЧТОБЫ ПОСМОТРЕТЬ ВСЕ КОММЕНТАРИИ ИЛИ ОСТАВИТЬ КОММЕНТАРИЙ,
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ
partiec Уровень 33
15 июля 2023
материал негоден
LucС Уровень 18
13 июля 2020
ConcurrentHashMap разделена на множество сегментов [по умолчанию их число равно 16] при инициализации.- это было до Java 8,где он был полностью переписан и теперь это массив узлов,внутри которого сегменты(до Java 8 было без массива)
Андрей Хромов Уровень 2
6 июля 2020
Судя по всему оригинал здесь: HashMap and ConcurrentHashMap Interview Questions
17 апреля 2019
Фактически, Collection.synchronizedMap(HashMap) внутренне созданного внутреннего класса SunchronizedMap содержащего пары key-value передающиеся в HashMap как аргумент. Сами то поняли что это означает?)
Кирилл Орлов Уровень 19
19 февраля 2019
Машинный перевод. Смысл очень сложно уловить, хоть отредактировали бы, перед выкладыванием