我最近了解了不同的方法来处理在哈希表冲突。只见那用链表的分离链总是有更多的时间效率和空间效率，我们分配predefined内存线性探测这以后，我们可能不会使用，因为我们动态地使用内存分离链，从而为独立的链接用链表并不比直线更有效探索？如果是的话，为什么我们那么使用线性探测呢？

I recently learned about different methods to deal with collisions in hash tables. And saw that the separate chaining with linked lists is always more time efficient, and for space efficiency we allocate a predefined memory for Linear probing which later on we might not use,for separate chaining we utilize memory dynamically, so is separate chaining with linked list not more efficient than Linear probing?if yes why do we then use Linear probing at all?

推荐答案

我很惊讶，你看到链接哈希比线性探测快 - 在实践中，线性探测通常显著高于链快。事实上，这就是它的使用的主要原因。

I'm surprised that you saw chained hashing to be faster than linear probing - in practice, linear probing is typically significantly faster than chaining. In fact, that's the main reason it's used.

虽然链式散列是伟大的理论和线性探测有一些已知的理论的弱点（如需要的五通独立散列函数中来保证的O（1）预期查找中），在实践中线性探测通常显著更快由于参考局部性。具体地，它的速度更快访问一系列元素中的阵列比它遵循指针链表，所以线性探测趋于跑赢次链式散列即使它有调查多个元素

Although chained hashing is great in theory and linear probing has some known theoretical weaknesses (such as the need for five-way independence in the hash function to guarantee O(1) expected lookups), in practice linear probing is typically significantly faster due to locality of reference. Specifically, it's faster to access a series of elements in an array than it is to follow pointers in a linked list, so linear probing tends to outperform chained hashing even if it has to investigate more elements.

有线性其他WINS探测。例如，插入到一个线性探测哈希表不需要任何新的分配（除非你是老调重弹的表），所以在像网络路由器内存不足的应用程序，它很高兴知道，一旦表设置，该元素可以放置到它与的malloc的危险失败。

There are other wins in linear probing. For example, insertions into a linear probing hash table don't require any new allocations (unless you're rehashing the table), so in applications like network routers where memory is scarce, it's nice to know that once the table is set up, the elements can be placed into it with no risk of a malloc fail.

希望这有助于！