Hashing

Hash Functions

• Take a variable amount of data
• Run it through a mathematical transformation
• Produce a fixed size integer
• Mathematical operations are O(1)

Hash Tables

• Collection class with O(1) access times
• Array + hash function
• Elements get stored in array at location of hash
• Only works if array is same size of elements (direct hashing)
• Or if the set of hashes is smaller than the set of items (can cause collisions)
• Allows values to be stored and looked up using a key (key, value)

Perfect Hashing

• Each item has a unique hash value
• E.g. 52 playing cards and an array of size 52
• Does not work well in real life (unknown data, complex data)
• E.g. Strings, custom objects, etc

Fixed Sized Arrays

• Generally, take the modulo of the result, worry about collisions later

Try It Out

• Insert the following elements into an array of size 10
• Apple, cat, java, ball, Pittsburgh
• Hash function (# vowels) * (# consonants) + (# letters)

Collisions

• Occurs whenever not using direct hashing
• Range of keys > array range
• Handle with either open addressing or chaining

Open Addressing

• If slot indicated by hash function is full, insert into another slot
• Works until load factor is 100%
• Probe sequence determines where to look for next available slot
• Insertions and lookups must use same probe sequence
• Removed elements must be recorded
• Each slot must record whether it is empty, full, or deleted
• A slot can only be empty until the first time a value is inserted, after that it is either full or deleted

Open Addressing: Linear Probing

• On collision, repeatedly scan adjacent cells until empty one is found
• Wrap around end of array (using modulus)
• If many keys hash to same location, may cause long searches
• Full? Track size separately or track index

Try It Out

• Hash table: Array of size 7
• Hash function: abs(key) % 7
• Keys to add: 4, 8, -3, 24, 18, 13

Open Addressing: Quadratic Probing

• Add square of probe number (modulo array size) to get next slot
• Avoids creating clusters
• Tends to spread data out more, reduce collisions

Try It Out

• Hash table: Array of size 10
• Hash function: (# letters - 1)
• Keys to add: ant, kona, java, ball, actors

Open Addressing: Double Hashing

• Define two hash functions h1 and h2
• h1(key) determines intitial slot
• h2(key) determines the step size for next probe
• h2(key) != 0
• Choose two hash functions that are generally much different from each other

Open Addressing: Table Size

• Load factor can not exceed 100%
• If the table size ever changes, each element must be reinserted into the hash table (taking into account new size)

Chained Hashing

• Each array slot refers to linked list of elements
• On insertions, hash function gives slot, then item is added to end of list
• Lookups must traverse list to find element
• Still want to expand table to keep lists short (if list under constant limit, considered O(1)
• Still need good hash function to spread of slots

Try It Out

• Hash table array of size 7
• Hash function: abs(key) % 7
• Keys to add: 4, 8, -3, 24, 18, 13
• Trace contains: 8, 4, 19, 17
• Remove: 18, -3

Summary

• Avoid collisions as much as possible (good hash function to spread out data)
• Manage collisions when they do happen (open addressing, chaining)
• Keep load factor down
• Next time: Coming up with good hash functions