我们为什么以及在哪里使用哈希？ [英] why and where do we use hashing?

问题描述

为什么我们使用哈希进行搜索？在二叉搜索树上使用散列有什么好处？

why do we use hashing for search? what are advantages of using hashing over binary search tree?

推荐答案

散列通常是一个恒定时间操作，而二叉树具有对数时间复杂度。

Hashing is generally a constant time operation whereas a Binary Tree has a logarithmic time complexity.

因为哈希的计算不是基于集合中的项目数，而是基于要搜索的项目，所以集合的大小与找到物品所需的时间。然而，大多数散列算法会产生冲突，从而增加时间复杂度，因此不太可能获得完美的恒定时间查找。

Because a hash is calculated not based on the number of items in the collection but on the item being searched for, the size of the collection has no bearing on the time it takes to find an item. However most hashing algorithms will have collisions which then increases the time complexity so it's very unlikely to get a perfect constant time lookup.

使用二叉树，你必须做在找到该项目之前进行log2N比较。

With a binary tree, you have to do up to log2N comparisons before the item can be found.

这篇关于我们为什么以及在哪里使用哈希？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！