为什么我们在哪里使用哈希？

为什么我们使用散列进行搜索？在二叉搜索树上使用散列有什么优点？为什么我们在哪里使用哈希？

来源

2011-02-25 nikitha.vyas

http://www.cs.auckland.ac.nz/~jmor159/PLDS210/hash_tables.html – 2011-02-25 13:29:26

维基百科解释说得好：

http://en.wikipedia.org/wiki/Hash_table#Features

摘要：插入一般都是缓慢的，读取比树木快得多。对于Java：任何时候当你有一些读/写很多的键/值对，并且一切都很容易写入RAM时，使用HashTable进行快速读取访问和难以置信的简单代码维护。

来源

2011-02-25 13:27:12

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

因为散列不是基于要搜索的集合中，但关于该项目的项目的数量来计算集合的大小上有需要找到一个项目的时间没有关系。然而，大多数散列算法会产生冲突，从而增加了时间复杂度，因此很难获得完美的恒定时间查找。

用二叉树，你必须做的最多log2N比较可以发现该项目之前。

来源

2011-02-25 13:28:01 Nick

可是啊（log2（n））来确认项目不存在，而不是接近O（1）以进行有效的哈希查找。 – 2011-02-25 13:52:26

散列意味着使用一些函数或算法将对象数据映射到一些代表性的整数值。这所谓的散列码（或简称为散列）可以被用来作为一种寻找地图中的项目时缩小了我们的搜索。

如果需要使用的算法的快速用于查找信息，你需要那么哈希表是最合适的算法使用，因为它只是生成您密钥对象的哈希和使用那要访问的目标数据 - 它是O（1）。其他是O（N）（大小为的链接列表N - 您必须逐个遍历一个列表，平均为N/2个）和O（log N）（二叉树 - 您的减半每次迭代搜索空间 - 只有当树的平衡，这取决于你的实现，一个不平衡的树可以具有性能显著恶化）。

来源

2011-02-25 13:29:42 ayush

哈希表是最好的用于搜索（=）如果具有较低的插入和均匀的时隙分布。时间复杂度为O（n + k） - 线性。

他们不是一个好主意，如果你想要做的比较操作（<，>）

来源

2011-02-25 13:32:13 shikhar

...或有排序的集合。 – 2011-02-25 13:53:03

为什么我们在哪里使用哈希？

回答

相关问题