Как эффективно удалить дубликаты из String[]?

Question

[irklogin]

Сразу хочу сказать, коллекции нельзя использовать (ArrayList , HashMap, HashSet etc.)
Нужно сравнивать хешируя.
В массиве сотни миллионов строк)
Подскажите по эффективности, пожалуйста

Comments

[Денис Загаевский]

Эффективность по скорости или по памяти?

[irklogin]

по скорости

[Денис Загаевский]

irklogin: фактически, вы можете взять ещё один офигенно большой массив String'ов, в который будете ложить элементы из первого массива по методу открытой адресации. Во вся случае, это поможет отсеять дубли. Остальное зависит от того, надо ли сохранять порядок ключей. Скорость будет O(1), память O(n).

[Tuvan]

Denis Zagayevskiy: И каким вы образом за О(1) удалите дубли?это не возможно

[Денис Загаевский]

Tuvan: Ошибочка, О(n), конечно)

Answer 1

[Evhen]

Эт почему нельзя использовать коллекции? о_О

1. Для данного решение нужна коллекция java.util.HashSet. Методы equals и hashCode в классе String реализованы эффективно, так что HashSet без проблем отсечет все дубли.
2. Зачем вы вообще строки грузили в массив? Сразу нужно было использовать HashSet.
3. С чего вы взяли что это будит менее эффективней, чем заливать все в массив?
4. Скорость доступа к элементам set-а такая же как и у массива: O(1).
5. Если вы грузите миллионы строк в массив, то явно экономия памяти у вас не в приоритете.

Comments

[mitekgrishkin]

< Эт почему нельзя использовать коллекции?
Лабораторка наверное

[Евгений Корначев]

В вопросе сказано про 'дубликаты', т.е. в массиве могут находиться одинаковые строки, поэтому хранение строк в ХешСете уже не подходит, нужно уточнение.

[Evhen]

Евгений Корначев: Вопрос - удалить дубликаты. HashSet не может содержат дубликаты. Если вы пытаетесь добавить строку, которая уже есть в сете, то она будит проигнорирована, в итоге вы получите коллекцию с набором уникальных строк

[X-NoNAME]

Eugene:
>она будит проигнорирована

Можно уточнить - проигнорирована или перезаписана?

[Евгений Корначев]

Eugene: Виноват, почему-то подумал что нужно удалить не все дубликаты, а только определенной строки.

[Evhen]

X-NoNAME: будит перезаписана ссылка