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

This quiz covers the concepts of hashing, data structures, and their complexities in terms of search, insert, and delete operations. Learn about the average and worst-case scenarios for unsorted arrays, sorted arrays, linked lists, skip lists, BST, and B-Trees.