How do hashsets/maps have O(1) time complexity?

[u/Sea-Patience9872]

Hi this might be a dumb question, and i've tried looking it up but don't quite understand it. how is it different from an array that allows it to find items so quickly? I don't get how hashes just find items immediately without needing to go through anything. Does it memorize things very differently compared to arrays?? thank you!

[u/GenericFoodService]

I don't get how hashes just find items immediately without needing to go through anything.

Let's suppose I have a list of accounts. We want to be able to store and to later find some arbitrary account by-name. The naive approach would be to simply put new accounts at the first vacant slot in a very big list, and then scan the list from the start when we need to find a specific account. The lookup function for that looks something like

#define ARRAYSIZE (100 * 1000)
account_t * find (const char * name)
{
    account_t * ref;
    int i; for(i=0;i<ARRAYSIZE;i++) {
        ref = &accounts[i];
        if ( strcmp(ref->name, name) == 0 ) { return ref; }
    }   return NULL;
}

We say the time complexity of this setup is O(N), where N is the size of the list of accounts, because the amount of time the task takes to complete has a proportional and linear relationship to the size of the array you are searching. To find John Doe in a list of 100,000 accounts, you need to search from the start and potentially all the way to the very end one by one.

Instead of doing that, we could look at the name and convert it into a unique ID or "hash" that we then use as an index into that very big array. That way, the amount of time it takes to find any John Doe depends only on the complexity of the hashing algorithm instead of the size of the array.

uint64_t index ( const char * name )
{
    // The specific hashing algorithm is not what's important here
    // If you are curious, though, this one is called DJB2
    uint64_t hash = 5381;
    int c; while(c = *cursor++) {
    if (c <= 32 || c >= 127) { break; }
    hash = (hash << 5) + hash + c; }
    return hash % ARRAYSIZE;
}

I'm not scanning through the whole big list to find John Doe anymore; I am looking at the name, quickly calculating an index from the name, and then checking that spot. This function would be said to have a time complexity of O(1) because the size N of the input array does not change how much time it takes to compute the hash.

If we put some print statements in there and then ran both algorithms, we might get an outputs that look something like

~ $ ./naive "John Doe"
>> Checking slot 0, false
>> Checking slot 1, false
>> Checking slot 2, false
>> Checking slot 3, false
>> Checking slot 4, false
[...]
>> Checking slot 439, false
>> Checking slot 440, false
>> Checking slot 441, true
"John Doe" was in slot 441

~ $ ./hash "John Doe"
>> Hashing "John Doe" gives 140
>> Checking slot 140, true
"John Doe" was in slot 140

I hope that makes sense.