> So index into your actual table, and check to see what's stored there
But that check isn't a constant time lookup. The lookup time can vary. (Analogously, a lookup in a phone book can vary in time; we can't necessarily go to the exact spot the first time.) So the total time for both steps must vary as well. I think.
I think where you're getting confused is that you're conceptualizing this like a search problem, where you compare values and inspect each member to see if it matches the target.
That's not what's going on here. Instead, you use the value as in input into a function that tells you where to look for it, then you look, to see if it's there.
If it's not there, it won't be anywhere else, so you don't have to keep looking. Things get interesting with collisions but that's a subject for another time.
Comments
> So index into your actual table, and check to see what's stored there
But that check isn't a constant time lookup. The lookup time can vary. (Analogously, a lookup in a phone book can vary in time; we can't necessarily go to the exact spot the first time.) So the total time for both steps must vary as well. I think.
I think where you're getting confused is that you're conceptualizing this like a search problem, where you compare values and inspect each member to see if it matches the target.
That's not what's going on here. Instead, you use the value as in input into a function that tells you where to look for it, then you look, to see if it's there.
If it's not there, it won't be anywhere else, so you don't have to keep looking. Things get interesting with collisions but that's a subject for another time.
OK, thanks, I'm starting to understand. Good explanation. I quit being lazy and searched around too, to see that it's possible.