Hash 函数的冲突（碰撞）是什么原因导致的？

Question

RT.尽量帮忙介绍具体点啊~
新手小白提问，还请多多关照~

Answer 1

你可以把hash想象成一个数组，现在你想把一个数据存到hash表中。那么问题来了：这个数据应该存到哪里？

于是，你需要一个hash函数，这个函数的作用就是把你要存的数据映射成hash表中的一个位置，这个位置就是你要存放该数据的地方。一般把hash表的每个位置都叫做“槽（slot）”，很形象，你要往槽里放数据。假如你要存的数据为k，存放在哪个槽里呢？很简单，存在hash（k）这个槽里。

这个hash函数是你自己选的。这里我以《算法导论》里面的一个题目举例：现在你选的hash函数是这样的：

hash(k) = k mod 9

假设hash表的大小为9（即有9个槽），现在要把一串数据存到表里：5,28,19,15,20,33,12,17,10

简单计算一下：hash(5)=5, 所以数据5应该放在hash表的第5个槽里；hash(28)=1，所以数据28应该放在hash表的第1个槽里；hash(19)=1，也就是说，数据19也应该放在hash表的第1个槽里——于是就造成了碰撞（也称为冲突，collision）。

解决冲突的方法有拉链法，开放定址法等，就不多说了

Answer 2

不同的key用同样的Hash算法,可能会得到相同的hash值

Answer 3

吾生也有涯，而知也无涯

Answer 4

很簡單，答案是「無限對於有限來說，總是過多了」。

hash是這樣的一類函數，接受「任意」的輸入，返回一個長度有限的序列。比如輸出一個三十二字符長的字符串，對於每一位，有 (+ 10 26) 種可能，十個數字以及二十六個拉丁字母，不區分大小寫。那麼對於32的長，一共有(^ 36 32)種不同組合。這是一個很大的數，但是對於「無限的輸入」，他還是太小了，因為他是有限的。 對於64的長，這個數字更大，但是，對於「無限的輸入」，他還是太小了，因為他是有限的。

無限對於有限來說，總是過多了。