Complex Structures
Caches
A cache is like a jewelry box. A jewelry box, is small, and generally holds the most valuable things in your possession, so in my case it holds an excessive amount of seeds.
If you had a very large closet, and you were looking for a specific piece of jewelry, it would take a long time. You would have to walk deep into the caverns of your closet. Then you would all the way back out, and then walk all the way back to get it again every time you wore it. That’s dumb. But you "aren’t stupid", so you put all the most used pieces into your jewelry box.
Now, jewelry boxes are not infinite, so you can only store a few pieces in there. That is a cache! Now the method for jewelry that we talked about is more specifically the idea for the LRU cache. That is least recently used. There are MANY other ways to handle a cache, and a jewelry box, and I don’t want to get too mired down by them.
This example is just like RAM and hard disk storage in computing. RAM is much faster than hard disk storage. Caches work with RAM to allow users access to data that is used frequently, or whichever caching scheme is deemed appropriate.
Hash Collisions
As you know from the terminology section, hashing is the method by which data is partitioned into sections of a hash. Each section of a hash is like a box. So, when you have you put something into a hashing function, it picks a box, and places it there. What if, two things are assigned to the same box? Well, luckily we have a data structure that can help us out, linked lists.
The box is turned into a linked list, however this comes at a price, access. We can no longer guarantee that we will be able to access the values at a given key in constant time, since a linked list could be N elements long. This is why most hashes say that when a hash/dictionary becomes too packed, we must resize. This can happen when a box stores more than a certain number of items. It can also happen when a hash stores more items than originally anticipated. It resizes itself (maybe it had 10 boxes before, now it has 20), and assigns the values in the boxes to the appropriate locations.
Heaps
Heaps do not easily lend themselves to explanations, but luckily I am a boss and can explain anything through analogies. Heaps, are like boarding groups for flights. Flights usually have a first class, a business class, and a coach section.
If an airline boarded the first class first, then business, then coach, but no one was in business class, what happens? You just board coach next. This is exactly like a min heap. Or max heap, depending on how you feel about people who sit in first class.
There are two types of heaps, a min heap, and a max heap. In a min heap the lowest value is on top. Let's say its 1. The values below 1 are greater than 1, and less than the numbers beneath them. Heaps are great for finding the minimum, or maximum, in a group of numbers.
If you don't understand, have a toddler read this page and then explain it to you. A heap is a pile of numbers, you can think of them as nodes. The top node points to a value, in a min heap that is the lowest value. In a max heap, that is the highest value. When you take the top node off of the heap, you replace it with the next value. A heap's head node looks at all the children, finds the lowest value, and makes that the new head. Simple.