If value does not exist in a Set or Hash Key, is it still O1 time?

Question

Given I have this real-world example

const whitelist = new Set(['192.0.2.1', '192.0.2.2','192.0.2.3']) //hard-coded ip list
const clientIP = request.headers.get("Client-IP");

if (await isSiteDown(request) && !whitelist.has(clientIP))
{
    return fetch('https://my-error-page.example.com');
}
return fetch(request)

I let's say user's ip is 192.0.2.4 and is not in the whitelist, would this still be in constant time search?

Yes, for the same reason the look-up is O(1) if it *is* present. — jonrsharpe, Mar 08 '21 at 16:10

score 1 · Accepted Answer · answered Mar 08 '21 at 16:14

Yes. It won't go through all the items and see if the string being searched for is one of the items - rather, it'll look up only that string to see if the Set contains it, which will take constant time.

It's a bit like checking whether a property exists on an object (without messing with prototypes) - eg obj.hasOwnProperty('bar') doesn't iterate through all properties on the object to see if any match, it looks to see if only the bar property exists.

The same is true for Maps and their .has / .get methods.

If value does not exist in a Set or Hash Key, is it still O1 time?

1 Answers1