COS 212 Hashing and Data Structures

Hashing

• Average and worst-case complexity of searching, inserting, and deleting in unsorted arrays, sorted arrays, unsorted linked lists, sorted linked lists, skip lists, binary search trees (BST), and B-Trees.

Hash Functions

• Basic idea: save items in a key-indexed table where the index is a function of the key.
• Properties of a good hash function:
  • Easy to compute
  • Each index is equally likely to be generated for each key
  • A perfect hash function assigns a unique index to each key

Types of Hash Functions

Extraction

• Use a selection of digits as the key
• Choose the part of the key that is least likely to repeat

Division Hashing

• Hash function: hash(K) = K % T where T is the size of the hash table
• Works best when T is a large prime number
• Alternatively: hash(K) = (K % p) % T where p is a prime number greater than T

Folding

• Designed to increase variability of hash codes
• Split the key into equal parts and combine them using a simple operation like addition
• Apply division hashing to restrict the index to the desired range
• Examples: shift folding and boundary folding

Mid-Square Function

• Square the key
• Use the middle section of a desired length as the hash value
• Advantage: the entire key is used, producing more variation
• Can be combined with other hash functions like folding

Hashing Strings

• Use ASCII codes to hash strings
• Methods:
  • Concatenate ASCII codes and apply division hashing
  • Add ASCII values and apply division hashing