time complexity of contains method in hashtable?

Question

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

Are you asking about contains or containsKey. contains checks to see if the map contains a value, which requires checking all entries. — Michael Krussel
– Michael Krussel, Commented Jan 4, 2012 at 21:54
If you are concerned about performance, you should consider HashMap or ConcurrentHashMap if you need it to be thread safe. — Peter Lawrey
– Peter Lawrey, Commented Jan 4, 2012 at 21:58
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; } — Sampath Pasupunuri
– Sampath Pasupunuri, Commented Jan 6, 2012 at 18:49
What I would do is calculate the hash of that value ( which would be the bucket) and see if that value exists in that bucket. — user982733
– user982733, Commented Jan 6, 2012 at 19:24

Community · Accepted Answer · 2020-06-20 09:12:55Z

7

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).

edited Jun 20, 2020 at 9:12

CommunityBot

11 silver badge

answered Jan 4, 2012 at 21:52

Jon Skeet

1.5m893 gold badges9.3k silver badges9.3k bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

James Montagne Over a year ago

Fair enough, comment redacted :)

Sampath Pasupunuri Over a year ago

what is the time complexity for Hashtable.contains() method?

Jon Skeet Over a year ago

@user926120: Given that it has to scan through the whole table, O(n)

Collectives™ on Stack Overflow

time complexity of contains method in hashtable?

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related