<p>I am self studying for the USACO and I’m trying to learn everything I can about computer science. Unfortunately, I am not very smart and have trouble reading Wikipedia. Can someone explain what a hash table is?</p>
<p>A hashtable is a list of hashes (numbers) that is calculated for each element in the table for easy lookup. Like if you have a function that adds up the number of 1’s in a sequence, then the hash for 011011 would be 4, and so the table would have 4 for the hash of 011011, and then other hashes for other values in the table.</p>
<p>Lookup time is O(1) if your hash is good, like if you can guarantee under a certain % of collisions. For example our previous hash is not a good hash because 110110 has the same hash value, and so these collisions would increase the lookup time.</p>
<p>That was fast. I guess I’m smarter than I thought.</p>
<p>Well, this has been pretty well-covered! I’m marking this thread as “best source.”</p>