COS 212 Hashing and Data Structures

Study Notes

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

Description

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.