Hashing and Heaps: Week 9

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

What is the purpose of the hashCode method in HashSet and HashMap?

To provide an equals method

To sort elements in a specific order

To provide a unique identifier for each element (correct)

To implement separate chaining hashing

What happens when a hash table becomes too full?

Insertions might fail for open addressing hashing with quadratic resolution (correct)

The table is automatically resized

Probabilities of collision decrease

Running time for operations decreases

What is the primary difference between a priority queue and a regular queue?

Priority queue can only store strings

Priority queue maintains a FIFO discipline

Priority queue can only store integers

Priority queue does not maintain a FIFO discipline (correct)

What is the heap property in a binary heap?

All nodes store values that are at most as large as their descendants Signup and view all the answers

What is the purpose of the insert operation in a priority queue?

To insert an element into the queue Signup and view all the answers

What is the purpose of the deleteMin operation in a priority queue?

To delete the minimum element Signup and view all the answers

What is the advantage of using a binary heap in implementing a priority queue?

It is very suitable for implementing priority queues Signup and view all the answers

What is the purpose of rehashing in a hash table?

To increase the size of the table when it becomes too full Signup and view all the answers

What is the primary purpose of hashing in a data structure?

To find or store an item in a data structure Signup and view all the answers

What is the collision problem in hashing?

When an element is inserted and it hashes to the same value as an already inserted element Signup and view all the answers

What is the purpose of a hash function?

To compute the hash code from objects Signup and view all the answers

What is a perfect hash function?

A hash function that maps each key to a unique item Signup and view all the answers

What is separate chaining?

A technique to resolve collisions by keeping a list of all elements that hash to the same value Signup and view all the answers

What is the disadvantage of using separate chaining?

The need for using linked lists slows down the algorithm Signup and view all the answers

What is the formula for the index in quadratic probing?

hashed key + n2 Signup and view all the answers

What is the purpose of double hashing?

To resolve collisions by using a second hash function when the result of the hash function results in a collision Signup and view all the answers

Study Notes

Hash Table and Hash Function

Hashing is a technique that uses a key to find or store an item in a data structure.
A hash table is an array that contains objects (items) associated with their hash code (key).
A hash code is used as an array index into a hash table.
A good hash function has minimum collisions between objects.
Example of a hash function: hash(x) = x mod 10.

Collision Problem

When an element is inserted, it hashes to the same value as an already inserted element, resulting in a collision.
A collision needs to be resolved to maintain the integrity of the hash table.

Simple Collision Resolution Techniques

Separate Chaining:
- Keep a list of all elements that hash to the same value.
- All keys that map to the same table location are kept in a linked list.
- Disadvantages: slows down the algorithm, requires implementing another data structure.
Open Addressing:
- Linear Probing: search the table until an empty location is found.
- Quadratic Probing: uses a collision resolution technique to avoid primary clustering.
- Double Hashing: uses a second hash function to resolve collisions.
- Example of a good hash function: hash2 (x) = R - (x mod R), R a prime < TableSize.

Implementing HashSet and HashTable

The Standard Library includes hash table implementations of Set and Map, namely HashSet and HashMap.
The items in the HashSet (or the keys in the HashMap) must provide an equals and hashCode method.
HashSet and HashMap are currently implemented using separate chaining hashing.

Rehashing

When a table gets too full, the running time for operations increases.
Insertions might fail for open addressing hashing with quadratic resolution.
Probabilities of collision increase.

Implementation of Priority Queue

A priority queue is a data structure that allows at least two operations: insert and deleteMin.
Unlike a regular queue, the priority queue does not maintain a FIFO discipline.
The binary heap data structure is suitable for implementing priority queues.
A heap is a binary tree that is completely filled, with the possible exceptions of:
- Almost complete: all nodes are filled in, except the last level may have some nodes missing toward the right.
- The tree fulfills the heap property: all nodes store values that are at most as large as the values stored in their descendants.

Basic Heap Operations

Steps for inserting an element (X):
- Add an empty slot (a hole) to the end of the tree.
- Move the parent value into the hole until the heap property is satisfied.
The heap property ensures that the smallest element is stored in the root.

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Description

Learn about hashing techniques, hash tables, and hash functions in data structures. Understand how hash codes are used as array indices and the importance of minimizing collisions.