Особый случай: хеширование и равенство
Во-первых, нам нужно определить что-то в отношении допущений, а именно: наличие равных и функциональных отношений. Что я имею в виду под этим? Я имею в виду, что для множества исходных объектов S, для любых двух объектов x1 и x2, которые являются элементами S, существует (хеш) функция F такая, что:
if (x1.equals(x2)) then F(x1) == F(x2)
У Java такие отношения. Это позволяет вам проверять дубликаты как операцию, близкую к O (1), и, таким образом, сводит алгоритм к простой задаче O (n). Если заказ не важен, это простой вкладыш:
List result = new ArrayList(new HashSet(inputList));
Если заказ важен:
List outputList = new ArrayList();
Set set = new HashSet();
for (Object item : inputList) {
if (!set.contains(item)) {
outputList.add(item);
set.add(item);
}
}
Вы заметите, что я сказал "около O (1)". Это связано с тем, что такие структуры данных (как Java HashMap или HashSet) полагаются на метод, в котором часть хеш-кода используется для поиска элемента (часто называемого сегментом) в резервном хранилище. Количество ведер является степенью 2. Таким образом, индекс в этом списке легко рассчитать. hashCode () возвращает int. Если у вас есть 16 сегментов, вы можете найти, какой из них использовать, добавив хэш-код с 15, давая вам число от 0 до 15.
Когда вы пытаетесь положить что-то в это ведро, оно может быть уже занято. Если это так, то произойдет сравнение linear всех записей в этом сегменте. Если частота столкновений становится слишком высокой или вы пытаетесь поместить слишком много элементов в структуру, они будут увеличены, как правило, в два раза (но всегда на степень 2), и все элементы помещаются в новые корзины (на основе новых маски). Таким образом, изменение размера таких конструкций относительно дорого.
Поиск также может быть дорогим. Рассмотрим этот класс:
public class A {
private final int a;
A(int a) { this.a == a; }
public boolean equals(Object ob) {
if (ob.getClass() != getClass()) return false;
A other = (A)ob;
return other.a == a;
}
public int hashCode() { return 7; }
}
Этот код является абсолютно легальным и соответствует контракту equals-hashCode.
Если ваш набор не содержит ничего, кроме экземпляров A, ваша вставка / поиск теперь превращается в операцию O (n), превращая всю вставку в O (n 2 ).
Очевидно, что это крайний пример, но полезно указать, что такие механизмы также полагаются на относительно хорошее распределение хешей в пространстве значений, используемом картой или набором.
Наконец, нужно сказать, что это особый случай . Если вы используете язык без «ярлыка хэширования», то это уже другая история.
Общий случай: нет заказа
Если для списка не существует никакой функции упорядочения, то вы застряли с O (n 2 ) сравнением грубой силы каждого объекта с любым другим объектом. Итак, на Java:
List result = new ArrayList();
for (Object item : inputList) {
boolean duplicate = false;
for (Object ob : result) {
if (ob.equals(item)) {
duplicate = true;
break;
}
}
if (!duplicate) {
result.add(item);
}
}
Общий случай: заказ
Если существует функция упорядочения (как, например, со списком целых чисел или строк), то вы сортируете список (то есть O (n log n)), а затем сравниваете каждый элемент в списке со следующим ( O (n)), поэтому общий алгоритм равен O (n log n). В Java:
Collections.sort(inputList);
List result = new ArrayList();
Object prev = null;
for (Object item : inputList) {
if (!item.equals(prev)) {
result.add(item);
}
prev = item;
}
Примечание: В приведенных выше примерах предполагается, что в списке нет нулей.