Question

简要回答哈希表这种数据结构应用在查找操作中的优势？

Answer 1

优势：

从时间和空间的角度分析：

1. 时间高效：利用哈希可使插入、查找、删除、修改、替换操作的时间复杂度达到O(1)，这是其他查找方式无法达到的（比如树形查找O(logn)、二分查找O(logn)、顺序查找O(n)等）。即使出现碰撞，整体理论值也可以接近O(1)。

2. 空间可接受：哈希的比较合适的空间消耗以O(2n)最佳，对于其他同类算法（主要是树形查找方式），要分为两类。第一种是以叶子存放有效值的树(如b+树、线段树)，其空间消耗可认为是O(4n)；第二种是所有节点均存放有效值，空间消耗可认为O(n)。

Answer 2

简而言之：
哈希表是种数据结构，它可以提供快速的插入操作和查找操作。哈希表也有一些缺点它是基于数组的，数组创建后难于扩展某些哈希表被基本填满时，性能下降得非常严重。这个问题是哈希表不可避免的，即冲突现象：对不同的关键字可能得到同一哈希地址。