временная сложность содержит метод в хеш-таблице? - PullRequest
Новая
       10

временная сложность содержит метод в хеш-таблице?

3 голосов
/ 05 января 2012

Я только что видел код метода contains в java.util.Hashtable.java. Он имеет цикл, который просматривает каждую запись в Hashtable и сравнивает ее с переданным аргументом.

Я читал, что метод содержит постоянное время. Как это возможно, когда у него есть цикл, который просматривает каждую запись. 

 public synchronized boolean contains(Object value) {
if (value == null) {
    throw new NullPointerException();
}

Entry tab[] = table;
for (int i = tab.length ; i-- > 0 ;) {
    for (Entry<K,V> e = tab[i] ; e != null ; e = e.next) {
    if (e.value.equals(value)) {
        return true;
    }
    }
}
return false;
}

1 Ответ

6 голосов
/ 05 января 2012

Hashtable.contains() пытается найти запись с равным значением .Это поиск по ключу , который является постоянным временем (в обычном случае) в хеш-таблицах.

Документы разъясняют это:

Проверяет, отображается ли какой-либо ключуказанное значение в этой хеш-таблице.Эта операция более дорогая, чем метод containsKey.

Обратите внимание, что этот метод по функциональности идентичен containsValue (которое является частью интерфейса Map в структуре коллекций).

...