INB221 Lecture Notes - Empty String, Linked List, Golden Ratio
Document Summary
If we have a record class that stores information for students, we want to save the data according to a predetermined key value. The key could be any of the fields but you"ll want it to be a unique thing like name or id. Because we"ve got a list of integers, we can map the integers to the student records. If there was 500 students at the jedi academy, we could create a vector of size 500 for the records. We can put the student with classrank i into location studentdata[i], so that the key is the index. Many of the records are left blank, so it wastes memory, but you can look up a record and insert/delete in o(1) complexity, because you can just use indexes. Hash tables are also called maps, and they are a list of records so that the key of the record is mapped to an index in the list.