Orien Daily
🔑 鸽巢原理：哈希冲突不是偶然，是你早就该预见的事
很多人第一次学哈希表时，会把“冲突”理解成实现不够好，像是程序员手滑造成的小事故。可如果你换个角度想：把更多元素塞进更少的桶里，冲突根本不是“可能发生”，而是“必然发生”。这背后最朴素的理由，就是离散数学里那个看起来像常识、但威力很大的结论——鸽巢原理。
它说得很简单：如果有 n+1 只鸽子，却只有 n 个鸽巢，那至少有一个巢里会有两只鸽子。放到计算机里，鸽子可以是键，鸽巢可以是哈希桶。假设你设计了一个哈希函数，把任意学号映射到 1000 个位置里。那只要插入 1001 个互不相同的键，就不管你的哈希函数多“聪明”，都一定会有至少两个键落到同一个位置。这不是概率问题，而是计数问题。
这件事的重要性在于，它帮你把很多工程直觉校正过来。比如有人会问：“能不能设计一个完全不冲突的通用哈希函数？”如果输入空间远大于输出空间，答案就是不能。你最多只能让冲突“分布得更均匀”，而不可能从根本上消灭它。于是哈希表真正的设计重点，就从“避免冲突”变成了“冲突出现后怎么处理得足够快”——链地址法、开放定址、再哈希，本质上都在回答这个问题。
鸽巢原理还有个更容易被忽视的味道：它不告诉你“哪两个键会撞”，却能先一步证明“总会有键撞”。这跟很多算法分析很像。我们有时并不需要精确知道最坏情况发生在哪个输入上，只要能先证明某种坏事一定存在，就已经足够指导设计。比如你把 367 个人放进一年 366 个可能生日里，必然有人同一天生日；同样地，把大量请求打到有限端口、缓存槽位、分片节点上，也一定会出现共享与争用。很多系统问题，底层都藏着一个鸽巢原理的影子。
🧪 课后一题
如果一个哈希表只有 256 个桶，现在已经插入了 300 个互不相同的键，能否断言“至少有一个桶里有两个以上的键”？进一步说，能否断言“至少有一个桶里有两个以上的键”之外，还有没有更强的结论？
💡 易混淆点
鸽巢原理证明的是“必然存在冲突”，不是“冲突会很多”，更不是“哈希函数设计得差”。很多人把“发生冲突”直接等同于“哈希函数烂”，这是误解。评价一个哈希函数，关键看的是分布是否均匀、是否抗构造输入，而不是是否能在输出空间有限的前提下神奇地消灭冲突。
CS
![📸 黄礼志 (X)[260628] 1:02AM KST (12:02AM 🇹🇼)[260628] 凌晨 1:02（韩国标准时间 12:02 🇹🇼）原文 #黄礼志](/static/https://cdn5.telesco.pe/file/QpCS5M_2gTPKW49M_ibW8cnIHuMponz_IqG9WkH4YM0PlJJIUlCBXFMo62URWzbIq7QCm1zOZUvNy_GmlI1DiqFatc3a8M5nahf84i9ItOdbyMACkBK8DIEE3tMTZFrZtHta599y7n2h9BeQMm9wMmrV1IJTeJI4BtKYHnsBb2qpIrVVlFpWn3LVh-JYNIDP2AC0WUk68ZeXwSIJlWa8fLy6RRGOWIP5y0i0appVvNyVg8nHRnjpQr0LOuExd0HMQijJa_sNsr6yeqhMY91wvaBJZYI-y2rHp4w0vkFyO1uw9mGUxVU-dKDJRxqRJLX7YwadR1X9SuKiAAx09JCMdQ.jpg)
