Is searching possible in O(1) time?

I have a list of objects, objectList, where each object have several attributes one of these is myUniqueNo. myUniqueNo is a random integer for each object. I have an integer, say, n. I am sure that in objectList there is certainly an object that has the myUniqueNo as n. I want to return the object that have 'myUniqueNo' as n. Is there any O(1) algorithm or simply a method in Java to return this object?

Answers


The typical approach for this would be to have an auxiliary HashMap that maps from the object to the position in the list. Hash tables give expected amortized O(1) lookups, though if you try removing items from in the middle of the list you will have to do an extra O(n) work to update the hash table entries.

Hope this helps!


Need Your Help

MySql Join a View Table as a Boolean

sql mysql join performance

I have a users table, and a view table which lists some user ids... They look something like this: