You are asking for a guess as to what people mean by inexact terminology. Hash tables are not really "searched" in any real sense other than to determine if an associated value was already stored.
In your example, the keys are the employee name.
- The hash of a name as input computes a value that resolves to a
bucket.
- That bucket can be empty.
- If the bucket isn't empty, then return the value stored in the bucket.
This has an obvious problem to it, and you might notice that associative arrays that are part of the standard datatypes or class libraries of many popular languages, can not deal with this problem.
If you have "John Smith" as an employee and hire a 2nd employee named "John Smith" there is no way for a hash table to tell the difference between the two people. So to be clear, if you try and add a new John Smith, it will either reject the new John Smith or overwrite the salary value for the one that was first stored. This is an implementation detail that might fall within the scope of your question, and explains why we have id#'s associated with our identities or in essentially any database system.
The main issue that hash tables have to deal with is hash collisions. This is when there are 2 or more inputs that hash to the same value.
Typically what happens is that after the hash computation occurs, it looks into the bucket data structure. There are 2 possibilities:
- Bucket is empty
- Bucket has one or more entries
So what is needed to resolve multiple entries? Some of the other answers enumerate or go into detail as to the schemes that have been employed to deal with collisions. The obvious and simple answer is that often the stored data structures include the key: value pair together.
Assume that "Bob Jones" and "Sam Smith" both hash to bucket 'Z'. In bucket Z you might find a linked list of values like this:
Bucket Z: ["Sam Smith": 23000] -> ["Bob Jones": 48500]
The -> represents a pointer that the implementation uses to find the next entry.
Hopefully this illustrates the way a bucket can actually store multiple salary values for different names and still return the correct salary associated with the original key. This could be considered an actual "search" because the system needs to search for a the value associated with the original key, but the hash itself is simply a computation. Look at well known hash algorithms like MD5 or SHA1 for examples. A Hash is a computation and not a search. A Hash table is a data structure that combines hashed values as the index for finding a previously stored value, or storing a new value.
