View source for 4.1.2.3 Hash Tables (Hashing Functions, Collision Resolution)

=== 4.1.2.3 Hash Tables: Super-Fast Lookups ===
Imagine you have a huge closet with many numbered hooks, and you want to store your clothes so you can find them super fast. A '''hash table''' is like that closet! It's a data structure that helps computers store and find information incredibly quickly.

Instead of looking through every item, a hash table uses a special trick: it takes the information you want to store (like a piece of clothing) and uses a special "hashing function" to calculate ''exactly which hook number'' to put it on. When you want to find that item later, you just use the same hashing function, and it tells you the hook number immediately!

==== Hashing Functions ====
A '''hashing function''' is like a secret recipe or a special math formula. It takes any piece of information (like a word, a number, or a name) and turns it into a smaller, fixed-size number, which is usually an index (a hook number) in the hash table. A good hashing function tries to make sure that different pieces of information end up on different hooks.

* '''Example:''' If you have a list of student names, a hashing function could turn each name into a unique locker number where their records are stored.

==== Collision Resolution ====
What happens if two different pieces of information try to go on the ''same hook'' (the same index) in the hash table? This is called a '''collision'''! Since only one item can go on each hook, the hash table needs a plan to solve this. This plan is called '''collision resolution'''.

There are different ways to resolve collisions, but a common one is to have a small "overflow" area or a mini-list attached to each hook. So, if a hook is already taken, the new item just gets added to that mini-list. When you search for an item, you go to its hook number, and then if there's a mini-list, you quickly check through that small list to find your item.

* '''Example:''' If two students are assigned the same locker number, the school might put their items in a small, clearly labeled box ''inside'' that locker.

==== Bibliography for Hash Tables ====

* '''Kiddle:''' [https://kids.kiddle.co/Hash_function Hash function Facts for Kids]
* '''HackerEarth:''' [https://www.hackerearth.com/practice/data-structures/hash-tables/basics-of-hash-tables/tutorial/ Basics of Hash Tables Tutorials & Notes | Data Structures]
* '''Fiveable:''' [https://library.fiveable.me/key-terms/data-structures/collision-resolution Collision resolution - (Data Structures) - Vocab, Definition, Explanations]
* '''GeeksforGeeks:''' [https://www.geeksforgeeks.org/dsa/collision-resolution-techniques/ Collision Resolution Techniques]