Hash Tables / Hash Maps

Question 1

What is a hash table?

Answer 1

A data structure that maps keys to values using a hash function.

Question 2

What is a hash map?

Answer 2

Another name for a hash table, often used interchangeably.

Question 3

What is a hash function?

Answer 3

A function that converts a key into an index in the hash table.

Question 4

What is the goal of a good hash function?

Answer 4

To distribute keys uniformly and minimize collisions.

Question 5

What is a collision in a hash table?

Answer 5

When two keys hash to the same index.

Question 6

What are common collision resolution techniques?

Answer 6

Chaining and open addressing.

Question 7

What is chaining?

Answer 7

A method where each table index points to a linked list of entries that hash to that index.

Question 8

What is open addressing?

Answer 8

A collision resolution method that finds another open slot in the table when a collision occurs.

Question 9

What are the types of open addressing?

Answer 9

Linear probing, quadratic probing, and double hashing.

Question 10

What is linear probing?

Answer 10

A technique where you check the next slot until an empty one is found.

Question 11

What is quadratic probing?

Answer 11

A technique where you check slots at increasing quadratic intervals.

Question 12

What is double hashing?

Answer 12

Using a second hash function to determine the step size when resolving collisions.

Question 13

What is the average-case time complexity for search, insert, and delete in a hash table?

Answer 13

O(1)

Question 14

What is the worst-case time complexity for hash table operations?

Answer 14

O(n), if many collisions occur.

Question 15

What is the load factor of a hash table?

Answer 15

The ratio of the number of entries to the number of buckets.

Question 16

Why is the load factor important?

Answer 16

High load factors increase the chance of collisions and degrade performance.

Question 17

What is rehashing?

Answer 17

The process of resizing the hash table and re-inserting all elements.

Question 18

When should you rehash a hash table?

Answer 18

When the load factor exceeds a certain threshold.

Question 19

What is a key in a hash map?

Answer 19

An identifier used to retrieve its associated value.

Question 20

What is a value in a hash map?

Answer 20

The data associated with a key.

Question 21

Can hash maps store duplicate keys?

Answer 21

No, each key must be unique.

Question 22

Can hash maps store duplicate values?

Answer 22

Yes, values can be duplicated.

Question 23

What happens if you insert a key that already exists?

Answer 23

Its value is updated.

Question 24

What is a hash collision attack?

Answer 24

An attack that exploits poor hash functions by causing many collisions.

Question 25

How do you prevent hash collision attacks?

Answer 25

Use strong cryptographic hash functions or randomized hashing.

Question 26

What is a dictionary in Python?

Answer 26

A built-in implementation of a hash map.

Question 27

What is a HashMap in Java?

Answer 27

A built-in hash table class from the Java Collections Framework.

Question 28

What are some applications of hash tables?

Answer 28

Caching, indexing, symbol tables, and lookup operations.

Question 29

What is the time complexity of rehashing?

Answer 29

O(n), since all elements must be re-inserted.

Question 30

How is deletion handled in open addressing?

Answer 30

By marking slots as deleted (lazy deletion) or reordering.

Question 31

What is a tombstone in hash tables?

Answer 31

A marker used to indicate a deleted entry during open addressing.

Question 32

What is a hash set?

Answer 32

A hash table that stores only keys, not key-value pairs.

Question 33

What is the difference between a hash table and an array?

Answer 33

Arrays use numeric indices; hash tables use keys and hash functions.

Question 34

What is clustering in open addressing?

Answer 34

The buildup of many entries in a sequence of slots, reducing performance.

Question 35

What is the primary benefit of using a hash table?

Answer 35

Constant-time average access for insert, search, and delete.

Question 36

What is a perfect hash function?

Answer 36

A hash function that causes no collisions for a specific set of keys.

Question 37

What is a universal hash function?

Answer 37

A family of hash functions designed to reduce the probability of collision.

Question 38

What is an example use case for hash tables in compilers?

Answer 38

Symbol tables for storing variable names and scopes.

Question 39

What is the difference between a hash table and a tree map?

Answer 39

Hash tables offer O(1) access; tree maps offer sorted keys with O(log n) access.

Question 40

What is the default initial capacity of Java’s HashMap?

Answer 40

16

Question 41

What is the default load factor for Java’s HashMap?

Answer 41

0.75

Question 42

What happens when a hash table reaches its capacity?

Answer 42

It resizes (rehashes) to a larger table.

Question 43

Can keys in a hash table be of any type?

Answer 43

Yes, as long as they are hashable (immutable and implement a proper hash function).

Question 44

What makes a data type hashable?

Answer 44

It must implement a stable and consistent hash function and be immutable.

Question 45

What is the modulo operator used for in hash functions?

Answer 45

To confine the hash value to a valid index range.

Question 46

What is an example of poor hash function design?

Answer 46

Using the length of a string as the hash — it causes many collisions.

Question 47

What is a common hash function for strings?

Answer 47

Polynomial rolling hash or djb2.

Question 48

What is the purpose of equals() and hashCode() in Java?

Answer 48

They ensure consistent behavior for keys in a HashMap.

Question 49

What is a multimap?

Answer 49

A hash table that allows multiple values for a single key.

Question 50

How do you iterate through all keys in a hash map?

Answer 50

Use a key set or an iterator over the entry set.