Flashcards on C++ Hashing

Click on the flashcard to see the answer


What is hashing?

Hashing is the process of converting a given key into another value by applying a hash function. The resulting value is used as an index in a hash table.

What is a hash table?

A hash table is a data structure that stores keys and associated values. It uses a hash function to compute an index into an array where the corresponding value can be found.

What is a hash function?

A hash function is a function that takes in a key and returns an index into an array. It should be deterministic (i.e., given the same key, it should always return the same index) and evenly distribute keys across the array.

What is collision resolution in hashing?

Collision resolution is the process of handling the case where two keys hash to the same index in a hash table. There are multiple techniques such as chaining and open addressing.

What is open addressing?

Open addressing is a collision resolution technique where if a collision occurs, the program searches for the next available slot in the hash table and places the key-value pair there.

What is probing in open addressing?

Probing is the process of searching for the next available slot in open addressing. Different types of probing include linear probing and quadratic probing.

What are the advantages of hashing?

The advantages of hashing include efficient lookups, insertions, and deletions; ability to handle large amounts of data; and efficient use of memory.

What are the disadvantages of hashing?

The disadvantages of hashing include potential for collisions, difficulty of resizing hash tables, and the need for a good hash function.

What is a hash map in C++?

A hash map in C++ is a data structure that stores key-value pairs using a hash table. It provides efficient lookup, insertion, and deletion operations.

How are hash maps implemented in C++?

Hash maps in C++ are typically implemented using separate chaining or open addressing for collision resolution. STL provides a map and unordered_map classes that implement hash map.

What is perfect hashing?

Perfect hashing is a technique where there are no collisions in the hash table. This is achieved by creating a hash function that guarantees a unique index for each key.

What is the time complexity of operations in a hash table?

On average, lookup, insertion, and deletion operations in a hash table take O(1) time. However, in the worst case, they can take O(n) time due to collisions.

What is the difference between a hash set and a hash map?

A hash set is a data structure that stores a collection of unique values, while a hash map stores key-value pairs. Both use hash tables for efficient storage and retrieval.

What are some common hashing algorithms?

Some common hashing algorithms include MD5, SHA-1, and SHA-256. These algorithms are used for secure hashing and digital signatures.

What is the importance of a good hash function?

A good hash function is essential for efficient and correct operation of a hash table. It should evenly distribute keys across the array and avoid clusters of keys at certain indices to minimize collisions.

What is hashing?

Hashing is the process of converting a given key into another value by applying a hash function. The resulting value is used as an index in a hash table.

What is a hash table?

A hash table is a data structure that stores keys and associated values. It uses a hash function to compute an index into an array where the corresponding value can be found.

What is a hash function?

A hash function is a function that takes in a key and returns an index into an array. It should be deterministic (i.e., given the same key, it should always return the same index) and evenly distribute keys across the array.

What is collision resolution in hashing?

Collision resolution is the process of handling the case where two keys hash to the same index in a hash table. There are multiple techniques such as chaining and open addressing.

What is open addressing?

Open addressing is a collision resolution technique where if a collision occurs, the program searches for the next available slot in the hash table and places the key-value pair there.

What is probing in open addressing?

Probing is the process of searching for the next available slot in open addressing. Different types of probing include linear probing and quadratic probing.

What are the advantages of hashing?

The advantages of hashing include efficient lookups, insertions, and deletions; ability to handle large amounts of data; and efficient use of memory.

What are the disadvantages of hashing?

The disadvantages of hashing include potential for collisions, difficulty of resizing hash tables, and the need for a good hash function.

What is a hash map in C++?

A hash map in C++ is a data structure that stores key-value pairs using a hash table. It provides efficient lookup, insertion, and deletion operations.

How are hash maps implemented in C++?

Hash maps in C++ are typically implemented using separate chaining or open addressing for collision resolution. STL provides a map and unordered_map classes that implement hash map.

What is perfect hashing?

Perfect hashing is a technique where there are no collisions in the hash table. This is achieved by creating a hash function that guarantees a unique index for each key.

What is the time complexity of operations in a hash table?

On average, lookup, insertion, and deletion operations in a hash table take O(1) time. However, in the worst case, they can take O(n) time due to collisions.

What is the difference between a hash set and a hash map?

A hash set is a data structure that stores a collection of unique values, while a hash map stores key-value pairs. Both use hash tables for efficient storage and retrieval.

What are some common hashing algorithms?

Some common hashing algorithms include MD5, SHA-1, and SHA-256. These algorithms are used for secure hashing and digital signatures.

What is the importance of a good hash function?

A good hash function is essential for efficient and correct operation of a hash table. It should evenly distribute keys across the array and avoid clusters of keys at certain indices to minimize collisions.

Share


Login to Save


Share



Login to Save


Explore Other Decks


Made for Grade 7

L'Illuminismo


View Deck
Made for Grade 8

Ivan Franko - Ukrainian Literary Phenomenon


View Deck
Made for Grade 9

Computer Components


View Deck

Explore More