CODEWITHSUNDEEP
javahashtablecontains
Sampath Pasupunuri
Sampath Pasupunuri

Reputation: 638

time complexity of contains method in hashtable?

I just saw the code of contains method in java.util.Hashtable.java. It has a loop that scans through each entry in the Hashtable and compares it with the argument passed.

I read that contains method takes constant time. How is it possible when it has a loop that scans through each entry.

 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;
}

Upvotes: 3

Views: 2763

Answers (1)

Jon Skeet
Jon Skeet

Reputation: 1500515

Hashtable.contains() tries to find an entry with an equal value. It's lookups by key which are constant time (in the usual case) in hash tables.

The docs clarify this:

Tests if some key maps into the specified value in this hashtable. This operation is more expensive than the containsKey method.

Note that this method is identical in functionality to containsValue, (which is part of the Map interface in the collections framework).

Upvotes: 7

Related Questions