Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

Data Structures the Fun Way > 10 HASH TABLES > Flashcards

10 HASH TABLES Flashcards

1
Q

What are hash tables?

A

Dynamic data structures optimized for insertions and lookups

Hash tables use mathematical functions to point us toward the data’s location, enabling quick retrieval of information.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is the primary goal of using hash tables?

A

To find and retrieve information quickly

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

How do hash tables enable efficient retrieval?

A

By mapping target values directly to their indices using a hash function

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is a key in the context of data structures?

A

A single value stored with or derived from the data that can identify a record

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Fill in the blank: Hash tables use __________ to compute a value’s index.

A

[hash functions]

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is a major downside of using an idealized data structure with an array bin for every possible key?

A

Excessive memory usage

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What happens when two different keys map to the same hash value?

A

A collision occurs

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is the division method in hashing?

A

A simple hash function that computes the hash value using the formula f(k) = k % b

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

True or False: Hash functions can only map numeric keys.

A

False

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is chaining in hash tables?

A

An approach for handling collisions by storing a linked list in each bin

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is the purpose of a hash function?

A

To map keys into the hash table

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What kind of data structures can use keys for organization?

A
  • Sorted arrays
  • Tries
  • Hash tables
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is the primary challenge when using hash functions?

A

Handling collisions

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Fill in the blank: A hash table’s structure may include an array of __________.

A

[ListNodes]

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What does the term ‘hash value’ refer to?

A

The location in the hash table where a key is stored

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

How can we alleviate collisions in hash tables?

A
  • Increasing the size of the hash table
  • Choosing a better hash function
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What does the modulo operation do in the context of hash functions?

A

It computes the remainder after division, determining the hash value

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What is a potential problem with a simplistic hash function?

A

It may produce many collisions for certain key distributions

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What is an example of a real-world application of hash tables?

A

Registration tables at events like conferences

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

True or False: Hash tables can store two different items in the same element of the array.

A

False

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What does the ListNode structure in a hash table contain?

A
  • key
  • value
  • next
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What is the main limitation of using hash tables?

A

They are not a perfect solution for every problem

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Fill in the blank: The hash function partitions keys into __________.

A

[disjoint sets]

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

What is a hash table using a linked list to store entries within the same bin?

A

A data structure that uses linked lists to handle collisions by chaining multiple entries that hash to the same bin.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
What is the purpose of the HashTableInsert function?
To insert a new key-value pair into the hash table with chaining.
26
What happens if the bin is empty in the HashTableInsert function?
A new linked list node holding the key and value is created.
27
What does the WHILE loop in HashTableInsert check for?
It checks if the current key matches the key being inserted and if there are more entries in the list.
28
How do you update a value if the key already exists in the hash table?
Set current.value = value.
29
What is the purpose of the HashTableLookup function?
To search for a key in the hash table and return its associated value.
30
What does HashTableLookup return if the bin is empty?
null.
31
What does the WHILE loop in HashTableLookup check?
It checks if the current key matches the target key and if the current entry is not null.
32
What is the purpose of the HashTableRemove function?
To find and remove a key from the hash table.
33
What additional information must be tracked in HashTableRemove to splice out a node?
The last node before the current node.
34
What is the primary advantage of using chaining in hash tables?
It allows for handling collisions by linking entries in the same bin.
35
What is linear probing in hash tables?
An approach to handle collisions by checking adjacent bins until an empty bin is found.
36
What structure is used to store key-value pairs in a hash table with linear probing?
HashTableEntry.
37
What happens when the number of keys reaches the size of the hash table?
There are no available bins left for new entries.
38
What is the significance of the count variable in the HashTableInsert function?
It prevents infinite loops by tracking the number of bins checked.
39
What is a key requirement for a good hash function?
It must map keys uniformly throughout the space of bins.
40
What does it mean for a hash function to be deterministic?
It maps the same key to the same hash bin every time.
41
What is a common method for handling non-numeric keys in hashing?
Transforming the non-numeric input into a numeric value.
42
What is Horner's method in string hashing?
A technique that multiplies the running sum of character values by a constant after each addition.
43
What is a potential downside of a poorly designed hash function?
It can lead to many collisions and inefficient lookups.
44
Fill in the blank: A good hash function should have a predefined range corresponding to the number of _______.
hash buckets.
45
True or False: Linear probing can lead to clustering, making it inefficient as the hash table fills up.
True.
46
What happens if the HashTableInsert function cannot find an empty bin?
It returns False, indicating the item could not be inserted.
47
What is the main disadvantage of linear probing compared to chaining?
It may require iterating over many entries during a search.
48
When searching for a key in a hash table with linear probing, what does the code return if the key is not found?
null.
49
What is the purpose of the StringHash function?
To compute a hash value for a given string based on its characters and a constant multiplier ## Footnote The function reduces the range of the key space using a mathematical function.
50
What does the variable 'total' represent in the StringHash function?
The running sum of the character values multiplied by a constant ## Footnote This helps in creating a unique hash value for the input string.
51
What is the typical value for CONST in the StringHash function?
A prime number larger than the largest value for any character ## Footnote This helps in minimizing collisions in the hash table.
52
What are hash tables particularly useful for?
Tracking a set of items and implementing data structures like dictionaries and sets ## Footnote This is essential for efficient data management in programming.
53
What data structures does Python use hash tables to implement?
Dictionaries and sets ## Footnote These structures benefit from fast lookups and insertions.
54
In a breadth-first search, what type of data structure is used to track future options?
A queue ## Footnote This allows for exploring nodes level by level.
55
In a depth-first search, what type of data structure is used to track future options?
A stack ## Footnote This allows for exploring nodes as deeply as possible before backtracking.
56
What is the role of hash tables in avoiding loops during graph searches?
They store the set of already visited items ## Footnote This prevents re-adding items that have already been explored.
57
How are visited nodes tracked in a breadth-first search using hash tables?
By mapping the letter's index in the alphabet into bins ## Footnote This allows for organized storage and quick lookups.
58
What is a collision in the context of hash tables?
When different keys map to the same location in the hash table ## Footnote This requires additional structures like linked lists to handle.
59
What is one trade-off of using hash tables compared to tree-based structures?
Collisions requiring additional levels of indirection ## Footnote This can complicate access to data in the hash table.
60
Fill in the blank: Hash tables provide a new way of organizing data by using a _______.
[mathematical function]
61
What is one application of hash functions outside of data structures?
Partitioning items or spreading out work ## Footnote Examples include load balancing tasks among servers.
62
Why are hash tables considered a vital tool for computer scientists?
They provide fast access time and reasonable memory trade-offs ## Footnote This makes them highly efficient for various applications.

Data Structures the Fun Way (15 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2025 Bold Learning Solutions. Terms and Conditions