Что за магия в Hashset находит невероятно быстрые дубликаты? - PullRequest
Новая
       23

Что за магия в Hashset находит невероятно быстрые дубликаты?

0 голосов
/ 05 июня 2018

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

Теперь я хотел проверить уникальность и выполнить цикл по списку следующим образом: 

for(int i=0;i<hashArrayList.size();i++)
{
   long refValue = hashArrayList.get(i)
   for(int j=i+1;j<hashArrayList.size();j++)
   {
      if(refValue == hashArrayList.get(j))
      --> UNIQUENESS VIOLATION, now EXPLODE!!
   }
}

ThisЭто займет ЧАСЫ.

Теперь о Hashset, который сам по себе не допускает дублирование.Hashset.addAll (hashArrayList) занимает 4 секунды!исключая / не добавляя дубликаты для этого списка с 5 миллионами элементов.

Как это происходит?И: Является ли мой цикл ArrayList настолько глупым?

Ответы [ 3 ]

0 голосов
/ 05 июня 2018

Внутренняя работа Hashmap

Более того, вы используете цикл внутри цикла, что делает сложность O (n ^ 2) менее эффективной по сравнению с хэш-картой.

0 голосов
/ 05 июня 2018

Коллекция на основе хеша не нуждается в зацикливании для проверки наличия элементов с одинаковым ключом.

Представьте, что у вас есть 1000 объектов X. В вашем случае вы просматриваете список каждый раз, когда добавляете что-то.

Коллекция на основе хеша вычисляет хеш объекта, просматривает, есть ли другие элементы с таким же хешем, а затем просто нужно проверить, равен ли один из них новому элементу.Если у вас есть хорошая хеш-функция, которая возвращает уникальный хеш для уникальных элементов, вам просто нужно вычислить число.

Конечно, если вы просто скажете: «Я ленив, и я переопределил свой метод hashCode с помощью return1 ", тогда у вас будет то же количество сравнений, что и для сбора хеша.

Пример: представьте, что у вас есть следующий HashSet: 

HashSet: [[obj1], [null], [null], [null], [obj2, obj3, obj4]]

Как видите, базовая структура(может быть) следующим образом: массив, содержащий другие структуры данных с фактическими записями.Теперь, если вы поместите obj5 в HashSet, он вызовет obj5.hashCode ().Исходя из этого, он рассчитает внешний индекс этого объекта.Допустим, это 4: 

HashSet: [[obj1], [null], [null], [null], [obj2, obj3, obj4]]
                                                  ^ obj5

Теперь у нас есть три других объекта с таким же индексом.Да, нам нужен цикл, чтобы проверить, равны ли некоторые из них новому obj5, но если у вас есть более крупный HashSet с миллионами записей, сравнение с некоторыми элементами будет намного быстрее, чем сравнение со всеми элементами.В этом преимущество коллекции на основе хеша.

0 голосов
/ 05 июня 2018

Вы делаете совершенно другое сравнение.

С ArrayList у вас есть вложенный цикл для , который делает его O(n^2).

Но с HashSet вы не делаете никаких циклов, а просто добавляете к нему n элементов, что составляет O(n).Внутренне HashSet использует HashMap, ключом которого являются отдельные элементы списка, а значением является static Object .

Исходный коддля HashSet (Java 8) 

public HashSet(Collection<? extends E> c) {
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
}

addAll вызовов add

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

Итак, в конечном итоге все сводится к вставке объекта (здесь long *)1029 *) в HashMap, который обеспечивает постоянную производительность по времени 1

1 Из Javadoc HashMap ( выделениеmine )

Эта реализация обеспечивает постоянную производительность для основных операций (получение и сдача), при условии, что хеш-функция правильно распределяет элементы между сегментами

...