•The array would be far too big!
•The array would be mostly empty!
•. . . but search and insertion would be fast!
•What if there were a way to
–translate a student number to a unique index
–use a much smaller array
–still have O(1) worst case insertion and search
2 Hash Functions
•Ahash function transforms (translates) a data key into an array index.
•Given a key, we use the hash function to know where to put or ﬁnd the data.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
hash function h(key)This element gets stored at
•We usually denote the hash function using the letter h, and h(key)as the resulting index for a given
•Question: What is the time complexity of the search?
•Any function hto transform a key to an index is called a hash function.
•A hash function is called perfect if it transforms every unique key to a unique address.
•If his a perfect hash function, the search always takes exactly the same amount of time, regardless of
how many elements are in the table (O(1)).
•But this leads to familiar problems. With a perfect hash function:
–table capacity must be greater than the number of possible keys and this isn’t always known
ahead of time.
–most of the table will be unused if only a small number of keys are used.
•Sometimes perfection is not desirable!
•Let Nrepresent the number of possible uSask student numbers.
•Let nrepresent the number of real uSask students, past and present.
•Obviously: N >> n.
•We could try to ﬁnd a function hthat maps all nreal student numbers to an array of exactly the right
size, so that every index is unique.