PSET5 - 3 conceptual questions (debug not needed)

Question

Question 1 (hash) – is it even remotely possible to reverse engineer the hash function when given lots of output?

For example if the underlying hash function is something simple like tolower(word[0]) % N, and we are given 100,000+ words from the dictionary and all their respective hash values, will the computer eventually be smart enough to connect the dots and know that we are using the ASCII table and a modulo?

Question 2 (load) – the conventional way to insert a node to an existing linked list, according to the pset5 walkthrough, is to link the new node to the first element and then set the header to the new node, so the linked list (in the example of an alphabetically sorted document) will look like HE -> HB -> HA etc.

Can we do it the other way around so that you first look through the existing linked list, and find the only node that has the NULL pointer, and set it to link to the new node, so the list will look like HA -> HB -> HE. I can’t think of why in theory this might not be working, and would love to know a). why CS50 seems to avoid this seemingly more intuitive method on purpose? b). what’re the pros and cons comparing to the conventional way?

The reason I’m asking this question is that it seems that BTC blockchain is done and verified in the HA -> HB -> HE order, and it seems that always having to break/reconnect the header when a new node is introduced is intuitively not a very secured practice.

Question 3 (unload) – let’s say someone did all the coding work and it’s our job to make sure the unload is thorough, but we can’t access to their code and can only write our own code to check (but not allowed to use things like valgrind), let’s say if they freed all the memory except one node in the middle of a linked list (like a space garbage floating in the void without any linkage).

Is it even possible to use a while loop again to go through the now almost perfectly cleaned hash table again and identify that particular node?

Answer 1

Q1: Is it possible? Yes, if you have software specializing in decription. Simple hash functions like encoding the first letter would be easy for systems designed to decode. Highly complex hashes? The odds go down. Some hash functions would be impossible to decode. You're basically asking if a computer can break codes. Just ask the NSA or the CIA.

Q2: Absolutely. There are many ways to insert a node into a linked list. Inserting at the beginning is simply one of the quickest ways to do it. It's a fixed O(n) time. If you're inserting anywhere else into the linked list, it takes time to find where to insert a new node. The question is whether it's more important to create the linked list quickly or to be able to search it efficiently and quickly. For example, there are ways to create a linked list that can be searched with a binary search. In that case, it's necessary to have an ordered list. This topic is extensive, so feel free to google it.

Q3: No. Think about this scenario. A linked list depends on each node having the address of the next node. Once a node is freed, the address of the next node is lost (unless you saved the addresses somewhere.) So, if only one or two nodes are left behind because the other nodes have been deleted, they're lost. That's the definition of a memory leak. At this point, the only way to release the memory is to terminate the program. That will release all memory used by the program as part of OS housekeeping.