This blog post describes what the pigeonhole principle states, demonstrates how to prove its correctness by contrapositive, then applies the pigeonhole principle to the hash table data structure. After reading this post, you should understand how to prove the pigeonhole principle, and recognize situations in computer science where it applies.