Module 14: Dynamic Memory Continued

Question 1

hash tables

Answer 1

data structure that employs an array (which may be on the stack or the heap and a hashing function. it may also include linked lists to allow for collisions

Question 2

multi-file development

Answer 2

refers to spreading your code across multiple files; the intent is to centralize common code that other developers could use

Question 3

key

Answer 3

portion of your data used to map to bucket

Question 4

value

Answer 4

bucket number in hash table array (aka index number)

Question 5

hash function

Answer 5

maps key to value (common variations follow)

Question 6

associative array

Answer 6

what a hash table actually is i.e., an array whose index is associated with your custom data type

Question 7

collision

Answer 7

when more than 1 key maps to the same value, the result is a bucket that contains more than one data item. we use linked lists to allow collisions a “perfect” hash table has no collisions (but then it becomes more of a lookup table)

Question 8

load factor

Answer 8

number of entries in table or the number of buckets. represents a metric that allows you to determine the tradeoff between time to search and space costs

Question 9

function pointers

Answer 9

pointers that point to functions. the pointer stores the address in program memory of the first instruction in the function

Question 10

arrays

Answer 10

• need to allocate a fixed size, cannot grow if you need to add more entries
• adding things to the end of an array is easy, if there is space
• inserting or deleting from the middle of an array is painful, since you need to shift things in an array
• finding things in an array is easy

Question 11

linked lists

Answer 11

• easy to add new elements to the front or back as needed
• inserting or deleting in the middle of the list is not a problem (but is tricky)
• finding things in the list involves “traversing” the list until we find what we need
• this is not hard but it is more time-consuming than addressing the exact element you desire
• once the linked list gets long, finding things inside them becomes very time consuming
• so, search is an issue with linked lists

Question 12

review of our implementation of a hash table

Answer 12

combination of an array, linked lists, and a hashing function

• gives us the “fast” addressability of an array with the efficiency of a dynamically allocated linked list
• note: an array of linked lists is not a hash table (it lacks the hashing function)

Question 13

to insert a node into a hash table:

Answer 13

1. apply hashing function to the incoming data to determine the bucket it belongs to
2. address the bucket
3. insert the node into the linked list addressed by the bucket

Question 14

to find a node in a hash table

Answer 14

1. apply the hash function to the data we wish to find to reveal which bucket it’s in
2. address the bucket
3. search for the node in the linked list addressed by the bucket #

Question 15

uses of function pointers

Answer 15

can “call” a function inside a function that has been passed as an argument

• also referred to as a “callback” function
• often used in asynchronous programming, event loops, and GUI programming
• -if an “event” occurs (e.g. a certain button is clicked), caller’s function is executed to “handle” the event

offers tremendous flexibility in writing libraries used by other programmers

• programmer uses a library and gives its flexibility by calling user code at runtime
• -library runs another person’s code
• -double-edged sword: lots of power, lots of problems!