hash table
Hash table and link list combo?
So, I’ve been given an assignment that has us using hash tables and linked list (in C), and we are using it as a kind of phone log. We are supposed to log who called, their number, and keep the order that they called. The problem is I cant figure out why we would need a hash table. Should i try to break it up by every 10 calls, or what? I need some help thinking about this.
Also, I’m not sure how to create a hash table. I’m using the gedit feature in Linux, so I dont think there is pre-existing code.
Please help and thanks in advance.
Keep in mind that a phone company would have millions of customers. Let’s assume that we identify each customer by their phone number.
If you just use a linked list to store the phone record. When it comes time to bill them, how will you find all of their records? If you just have a linked list you’ll have to scan the entire set of records (which contains millions and millions of calls each day).
So the hash table allows you to quickly find a particular caller by their ID (their phone number). Then, once you find that caller you will have a linked list of each of their phone records.
Let me try to explain graphically:
Caller: (408) 555-1212
Who they called: (415) 555-1212, Time: 3:01pm, Date: 12/3/08, etc.
Find the linked list of records for caller identified by 4085551212
Hash Table
[0] key=…
[1] key=…
…
[n] key=4085551212 value=phoneRecordsLinkedList
…
phoneRecordsLinkedList
PhoneRecord1 = “Who they called: (415) 555-1212, Time: 3:01pm, Date: 12/3/08, etc.”
PhoneRecord2 = …
PhoneRecord3 = …
CS 61B Lecture 21: Hash Tables
