SUNY Geneseo Department of Computer Science

Hash Tables

Return to List of Lectures

Questions?

Hash Tables

Example (simple): build a hash table keyed by day number in year (1 - 365) containing holiday information, e.g., (1, New Years Day), (33, Ground Hog Day), etc.

• Idea 1: main table is a string array indexed 0 through 365 with strings containing holiday names. If multiple holidays fall on the same day of the year, join the names in the string with “and”

• This is a direct addressed table
• Pseudocode

            class HolidayTable

                string[ 0 .. 365 ] T

                insert( d, name )
                    if T[d] == empty
                        T[d] = name
                    else
                        T[d] = T[d] + "and" + name

                search( d )
                    return T[d]

                delete( d )
                    T[d] = empty

• Idea 2: compress the table down to maybe 20 entries, to not waste as much space.
  • Now use a real hash function to map days to table indices, e.g.,

            hash( d )
                return d % 20

• Table entries are linked lists, with nodes containing both key (day) and data (holiday name)

• Some methods for this structure:

            insert( d, name )
                q = hash( d )
                InsertFront( T[q], <d,name> )
                
            search( d )
                q = hash( d )
                b = find( T[q], d )
                return name( b )

Hashing string keys

• Start with numeric codes for letters
• Use all letters to better distribute keys over table, e.g., add up the codes for all the letters in the string
• Take sum (or whatever number you calculate from the letters) mod the table size

Hand out hashing homework

Next

Analysis of hashing

Read

• Appendix C.2 through “Discrete probability distributions” (bottom of page 1189 to bottom of 1191)
• Appendix C.3 through “Expected value of a random variable” (middle of page 1196 through middle of 1199)
• “Analysis of hashing with chaining” in section 11.2 (middle of page 258 through bottom of 260)