Как сделать операции HashSet равными O (n)?

Как я могу сделать операции HashSet равными O (n)?Как сделать операции HashSet равными O (n)?

У этого есть стандартные операции коллекции Добавить, Удалить, Содержит, но поскольку он использует реализацию на основе хэша, эти операции - O (1).

Но когда операции O (n)?

Спасибо!

источник

2014-12-26 user3917453

Почему вы хотите знать? И какой интерес у нас в том, чтобы сделать вещи медленнее, чем они есть? – fge

Почему вы хотите ухудшить его производительность от O (1) до O (n)? – Bhaskar

Операции, в общем, являются O (n), когда худший случай приводит к обходу всех существующих элементов. Итак, вставьте наибольшее число в уже отсортированный упорядоченный список. Однако обдумать это для хешированной структуры, учитывая, что это будет противоречить всему пункту, довольно бессмысленно. Единственный реалистичный ответ - иметь либо таблицу с плохим размером, либо дрянную хэш-функцию. – ChiefTwoPencils

Один патологический случай, который приведет к поведению O (n), когда все элементы имеют один и тот же хэш-код.

источник

2014-12-26 12:25:17 NPE

Ударьте меня! '@Override public final int hashCode() {return 42;/* универсальный ответ и случайный * /} ' – fge

@fge return 4 еще более случайный :) http://xkcd.com/221/ – cel

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

источник

2014-12-26 12:28:28 vlio20

Изготовление ключа хэша * должно быть * независимо от' n'. Речь идет о том, насколько уникальный ключ влияет на поиск и в свою очередь * производительность *. – TheLostMind

@TheLostMind Создание хэш-ключа не обязательно константа (по крайней мере, можно сделать это «O (n)»). – kraskevich

сам вопрос (я думаю) - это своего рода «любопытство» - поэтому нет смысла делать хеш-функцию в такой сложности. – vlio20

NPE в основном правильный.

Однако, я должен добавить, что в Java 8, HashMap и HashSet были улучшены, чтобы заменить длинные хэш-цепи с бинарными деревьями в том случае, когда тип ключа реализует Comparable. (См JEP-180)

Это означает, что патологический случай O(N) операций происходит только тогда, когда все элементы имеют один и тот же хэш-код И ключ типа не реализации Comparable. Если тип ключа реализует Comparable, то наихудшая сложность get на HashMap или HashSet равна O(logN).

источник

2014-12-26 12:45:21

Простой способ добиться этого без переопределения класса (как это делает NPE) - создать много ключей с одним и тем же хэш-кодом. например

Set<Long> longs = new HashSet<>(); 
for (int i = 0; i < 10000; i++) { 
    Long element = ((long) i << 32) + (i & 0xFFFFFFFFL); 
    assert element.hashCode() == 0; 
    longs.add(element); 
}

источник

2014-12-26 12:51:17

Как сделать операции HashSet равными O (n)?

ответ

Смежные вопросы