Блог

java.util.Set реализации удаляют дублирующиеся элементы.

Как дублирующиеся элементы удаляются внутренне в java.util.Set ?

На самом деле, AFAIK из исходных текстов, большинство Set реализаций в java даже не проверяют, содержится ли элемент уже.

Они просто всегда выполняют add() в своей внутренней структуре, которая содержит установленные элементы, и позволяют этому объекту обрабатывать случай дублирования.

например, HashSet вызывает put(K,V) внутренний HashMap , который просто вставляет новый объект, перезаписывая старую запись, если она дублируется.

Немного углубившись в ваш вопрос, я предполагаю, что вы наблюдаете странное поведение с java.util.HashSet (обычно то, что все используют по умолчанию).

В соответствии с контрактом java.util.Set можно получить один и тот же объект в java.util.HashSet два раза подобным образом:

 import java.util.HashSet;
import java.util.Set;

public class SetTest 
{
  public static void main(String[] args) 
  {
    MyClass myObject = new MyClass(1, "testing 1 2 3");

    Set<MyClass> set = new HashSet<MyClass>();
    set.add(myObject);

    myObject.setHashCode(2);
    set.add(myObject);

    System.out.println(set.size());  // this will print 2.
  }

  private static class MyClass 
  {
    private int hashCode;
    private String otherField;

    public MyClass(int hashCode, String otherField) 
    {    
      this.hashCode = hashCode;
      this.otherField = otherField;
    }

    public void setHashCode(int hashCode) 
    {
      this.hashCode = hashCode;
    }

    public boolean equals(Object obj) 
    {    
      return obj != null amp;amp; obj.getClass().equals(getClass()) amp;amp; ((MyClass)obj).otherField.equals(otherField);
    }

    public int hashCode() 
    {
      return hashCode;
    }
  }
}
  

После указателя из @jitter и взгляда на исходный код вы можете понять, почему это могло произойти.

Как говорит @jitter, java.util.HashSet использует java.util.HashMap внутренне. Когда хэш меняется между первым и вторым добавлением, в java.util.HashMap используется другой сегмент, и объект находится в наборе дважды.

Пример кода может выглядеть немного искаженным, но я видел, как это происходит в естественных условиях с классами домена, где хэш создается из изменяемых полей, а метод equals не синхронизирован с этими полями.

Простой способ выяснить это — посмотреть в исходном коде интересующий вас код.

Каждый JDK имеет src.zip включен, который содержит исходный код для общедоступных классов, так что вы можете просто найти исходный код для HashSet и посмотреть 🙂 Я часто использую Eclipse для этого. Запустите его, создайте новый Java-проект, установите JVM в качестве установленного JDK (если нет, вы используете JRE по умолчанию в системе, который не имеет src.zip ) и Ctrl-Shift-T для перехода к HashSet.

Прочитайте ваш вопрос более подробно:

Вы не можете добавлять дубликаты из java doc для Set.add() или вы имеете в виду addAll?:

Добавляет указанный элемент в этот набор, если он еще не присутствует (необязательная операция). Более формально, добавляет указанный элемент e к этому набору, если набор не содержит элемента e2, такого что (e==null ? e2==null : e.равно(e2)). Если этот набор уже содержит элемент, вызов оставляет набор неизменным и возвращает false. В сочетании с ограничением на конструкторы это гарантирует, что наборы никогда не будут содержать повторяющихся элементов.

Добавляет указанный элемент в набор, если он еще не присутствует. Если набор уже содержит элемент, вызов оставляет набор неизменным и возвращает false.В сочетании с ограничением на конструкторы это гарантирует, что наборы никогда не будут содержать повторяющихся элементов.

Во-первых, set не «Удаляет» дубликаты, он вообще не позволяет вводить дубликаты.

Позвольте мне познакомить вас с реализацией метода set.add(e).

set.add(e) возвращает логическое значение, указывающее, было ли добавлено e в набор или нет.

Давайте возьмем этот простой код для примера:

Мы получим x как true и y как false .

Давайте посмотрим, что на самом деле делает add():

Итак, HashSet в основном использует HashMap внутренне и отправляет элемент в качестве ключа (и пустой инициализированный объект с именем PRESENT в качестве значения.). Это map.put(k,v) либо возвращает значение null, если ключ никогда не существовал, либо возвращает старое значение, которое имел ключ.

Поэтому при выполнении set.add(1) в первый раз мы получаем null в ответ на map.put(1,PRESENT) , и именно поэтому мы получаем true .

И когда мы вызываем его во второй раз, мы не получаем null в ответ на map.put(1,PRESENT) и, следовательно, set.add(1) возвращает false .

(Вы можете углубиться в метод put, который внутренне вызывает putVal и использует хэш, чтобы определить, существует ли уже ключ, в зависимости от того, какой из них возвращает значение null или old.)

И поскольку мы используем HashMap внутренне, который использует hash для определения уникальности ключа, у нас никогда не будет одного и того же элемента дважды в HashSet.