DATA Hashing and Heaps Vocab

Hash Table ADT

Allows constant average time for insertion, deletion, and search; does not support ordered operations like findMin or findMax

Hash Table Basics

Fixed-size array; hash function maps keys to indices

Hash Table Structure & Collisions

Table size = TableSize; hash function maps keys to [0, TableSize

Hash Function Examples

Integer keys: key % TableSize (preferably prime); String keys: sum ASCII values mod TableSize

String Hash Function (Code)

Simple hash function sums ASCII values of characters in a string

ASCII Table

Reference for ASCII values of letters

Another String Hash Function

Weighted sum of first three characters; limited combinations in English

Collisions Introduction

Two main resolution methods: Separate Chaining and Open Addressing

Separate Chaining

Each table slot holds linked list of elements with same hash

Separate Chaining Diagram

Visual representation of separate chaining

Separate Chaining Analysis

Load factor λ = elements / TableSize; average unsuccessful search examines λ nodes; successful search examines 1 + λ/2 nodes

Open Addressing Intro

Alternative to separate chaining; no linked lists used

Open Addressing Definition

On collision, probe for next empty cell using f(i); load factor λ < 0.5

Open Addressing Strategies

Linear Probing, Quadratic Probing, Double Hashing

Linear Probing

f(i) = i; sequential probing; can cause primary clustering

Linear Probing Example

Step-by-step insertion with linear probing

Linear Probing Complexity

Insert & find: O(n) worst case; deletion requires lazy deletion

Deletion in Probing Tables

Standard deletion not allowed; use lazy deletion; cells marked active or deleted

Linear Probing Performance

Expected probes for unsuccessful search = 1/(1

Linear Probing Graph

Shows probe counts vs load factor; performance degrades when table > half full

Quadratic Probing

f(i) = i²; reduces primary clustering

Quadratic Probing Example

Step-by-step insertion with quadratic probing

Quadratic Probing Limitations

Requires prime TableSize and λ < 0.5; may fail to find empty slot if table > half full

Quadratic Probing Detailed Example

Inserting keys 76, 40, 48, 5, 55, 47 into size-7 table; shows failure to insert 47 due to limited probe sequence

Quadratic Probing Analysis

May not explore all slots; if TableSize prime and λ < 0.5, empty slot will be found

Secondary Clustering

Quadratic probing avoids primary clustering but can cause secondary clustering; double hashing suggested

Double Hashing

Uses second hash function f(i) = i * hash₂(x); example hash₂(x) = R

Double Hashing Example

Step-by-step insertion using double hashing

TableSize Should Be Prime

Prime TableSize improves distribution in double hashing; quadratic probing simpler/faster for expensive hash functions

Separate Chaining vs Open Addressing

Separate chaining: easier, predictable; Open addressing: less memory, clustering issues

Rehashing

When table too full, create larger table (usually double) and re-insert all elements; costly O(N) but infrequent

Hashing Wrap-Up

Efficient for insert/delete/find; requires good hash function, prime table size, proper load factor; widely used

Priority Queue ADT

Defines priority queue with insert(k, x) and removeMin(); applications: standby flyers, auctions, stock market

Priority Queue Sorting

Using priority queue to sort (PQ-Sort); unsorted sequence → selection sort (O(n²)); sorted sequence → insertion sort (O(n²))

Heap Definition

Binary tree with heap-order property and complete binary tree structure; visual example given

Height of a Heap

O(log n); proof based on complete binary tree property

Heaps and Priority Queues

Heaps can implement priority queues; each node stores (key, element); diagram shown

Insertion into a Heap

Steps: 1) find insertion node (last node), 2) store key, 3) restore heap-order via upheap

Upheap

Restores order after insertion by swapping upward; runs in O(log n) time

Removal from a Heap

removeMin removes root: 1) replace root with last node’s key, 2) remove last node, 3) restore heap-order via downheap

Downheap

Restores order after removal by swapping downward; runs in O(log n) time

Updating the Last Node

Finding new last node in O(log n) steps

Heap-Sort

Heap-based priority queue sort gives O(n log n), faster than insertion/selection sort

Vector-based Heap Implementation

Heap stored in array/vector; children at 2i and 2i+1; enables in-place heap-sort

Merging Two Heaps

Merge by making new root and performing downheap

Bottom-Up Heap Construction

Build heap in O(n) time by merging pairs bottom-up; step-by-step examples shown

Analysis of Bottom-Up Construction

Proxy path analysis shows O(n) time; faster than n insertions (O(n log n))