Как работает набор хэшей в Java

В core java interview questions Часто засыпают вопросами о структуре коллекции. У меня брали интервью в Goldman Sachs, и там мне задали вопрос, от которого я остолбенел. Интервьюер спросил, как вы реализуете Set в Java, другими словами, внутреннюю работу HashSet или как работает HashSet в java. То есть, как убедиться, что каждый элемент уникален, не используя Set interfaces или классы, реализующие Set Interface.

Читайте Также: Как работает HashMap в java

Я дал ответ, хотя и прошел квалификационный раунд собеседования, но ответ далек от удовлетворительного.

Поэтому я вернулся домой и провел кое-какие исследования. Итак, наконец-то я получил ответ и делюсь им с вами.

Установите внутреннюю реализацию в Java

Каждый элемент в наборе уникален. Чтобы в наборе не было повторяющихся элементов.

Поэтому в java, если мы хотим добавить элементы в набор, мы пишем такой код

public class JavaHungry {    
    public static void main(String[] args)
    {
        // TODO Auto-generated method stub

        HashSet

Он выведет результат: Набор равен [3, Java Hungry, ]

Теперь давайте добавим повторяющийся элемент в приведенный выше код

public class JavaHungry {

    public static void main(String[] args)
    {
        HashSet

Он выведет результат: Набор равен [3, Java Hungry, ]

Теперь, что происходит внутри, когда вы передаете повторяющиеся элементы в метод add() объекта Set, он вернет false и не добавит в хэш-набор, так как элемент уже присутствует. Пока все хорошо.

Но главная проблема возникает в том, как он возвращает false. Итак, вот ответ

Когда вы открываете реализацию HashSet метода add() в Java Api, который rt.jar , вы найдете в нем следующий код

public class HashSet
extends AbstractSet
implements Set, Cloneable, java.io.Serializable

{
    private transient HashMap map;

    // Dummy value to associate with an Object in the backing Map

    private static final Object PRESENT = new Object();



    public HashSet() {
        map = new HashMap<>();
    }

    // SOME CODE,i.e Other methods in Hash Set


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



    // SOME CODE ,i.e Other methods in Hash Set
}

Итак, мы достигаем уникальности в наборе, внутренне в java с помощью HashMap. Всякий раз, когда вы создаете объект HashSet, он создает объект HashMap, как вы можете видеть в выделенных курсивом строках в приведенном выше коде.

Мы уже обсуждали Как HashMap работает внутри java .

Как мы знаем, в HashMap каждый ключ уникален. Итак, что мы делаем в наборе, так это передаем аргумент в add (элемент E), который является E, в качестве ключа в хэш-карте. Теперь нам нужно связать некоторое значение с ключом, поэтому разработчик Java APIs передал фиктивное значение (new Object () ), на которое ссылается ссылка на объект PRESENT.

Итак, на самом деле, когда вы добавляете строку в HashSet, например HashSet.add(3), что делает java внутренне, так это то, что она помещает этот элемент E здесь 3 в качестве ключа в HashMap (созданный во время создания объекта HashSet), и некоторое фиктивное значение, которое является объектом объекта, передается в качестве значения для ключа.

Теперь, если вы увидите код метода HashMap put(Ключ k, значение V), вы найдете что-то вроде этого

 public V put(K key, V value) {

//Some code

}

Главное, на что следует обратить внимание в приведенном выше коде, это то, что put (key, value) вернет

1. нулевой, если ключ уникален и добавлен на карту

2. Старое значение ключа, если ключ является дубликатом

Итак, в методе HashSet add() мы проверяем возвращаемое значение метода map.put(ключ,значение) с нулевым значением

т.е.

   public boolean add(E e) {

            return map.put(e, PRESENT)==null;

       }

Так , если map.put(ключ,значение) возвращает null , то

map.put(e, вернет значение true, и элемент будет добавлен в HashSet.

Так, если map.put(ключ, значение) возвращает старое значение ключа, то

map.put(e, вернет значение false, и элемент не будет добавлен в HashSet.

Если у вас все еще есть какие-либо сомнения, пожалуйста, напишите в комментариях.

Читайте Также: Лучший Книги для изучения Java

Оригинал: “https://dev.to/javahungry/how-hashset-works-in-java-439f”