常用的哈希表实现与树的比较

假设你说的是时间复杂性。

map<size_t,Bucket> 对bucket的访问将导致O(logn)时间复杂度。您需要具有O(1)访问时间复杂性的内容,例如 vector<Bucket> 符合哈希表的预期时间复杂度。

散列表的时间复杂度可以是好的,也可以是差的,这取决于散列表的填充方式。

在最好的情况下,每个bucket最多有一个条目,通过key访问是O(1)。这是哈希表通常引用的复杂性。

在最坏的情况下,每个键都有相同的哈希值,按键访问有效地搜索一个列表,从而导致O(n)行为。

现实世界中的使用通常介于这两个极端之间,希望更接近O(1)。

你的另一个被接受的答案 question

阿尔伯特,你的问题的关键是,没有一个哈希表,而是有很多哈希表。

这里问题的核心是一些操作的big-O复杂性。平均来说,哈希表应该产生O(1)复杂度来查找一个项。二叉树的平均结果是O(logn)。

就速度而言,它实际上取决于N的大小,因为这些都是渐进的复杂性,因此当N很大(比如百万)时,它们代表数量级,而对于小集合,实际速度可能有很大的不同。

因此,与其试图详细阐述你的问题,我认为你应该更好地掌握哈希表。快速概述:

• 哈希表可以用bucket实现,也可以不用bucket实现:非bucket实现包括开放寻址方案(顺便说一句,开放寻址方案对缓存更友好)。
• bucket可以用链表实现,也可以不用链表实现。其他方案包括使用另一个哈希函数(每个bucket本身就是一个哈希表)或二叉树(map),后者需要一些排序。

阅读维基百科上的文章,它将阐述这些观点以及更多。

如果表被广泛链接(即已满),那么探测过程将花费更多的时间来解决冲突。在理论上最坏的情况下,所有值都将映射到同一个哈希键,哈希函数将花费所有时间跟踪链,即O(n)。

在实践中,除非你的散列函数真的被破坏了,否则你应该得到O(1)来满足所有的实际目的(注意,对于较小的表,你可以取一个较大散列值的模)。如果您有一个可以扩展的基于哈希表的容器,那么它可能会执行扩展操作,这将非常昂贵(1)。

树将是O(logn)而不是O(1),尽管如果树是不平衡的,那么搜索也可以变成有效的线性操作。请注意,这在某些常见场景中是一个问题,例如按键顺序插入节点时(假设对基于树的集合执行浅层复制操作)。通常,使用诸如红黑树之类的平衡树算法来保持树的效率。树的另一个优点是可以按顺序遍历树并生成键的有序列表,而不必显式地对它们进行排序。

1. 有关扩展成本相对较低的哈希操作的示例,请参见 Linear Hash Table

实现可以很容易地减少“超大”haskey。例如,它可以使用以下结构:

typedef list< pair<Key,Value> > Bucket;
const int HashSize = 511;
Bucket[HashSize] Hashtable;
inline size_t HashIndex(Key k) { return hash(k) % HashSize; }

当然,在实践中,HashSize不是一个常数。如果插入的元素超过几千个,则会导致性能急剧下降。而且,如果元素较少,它会占用相当多的内存。因此,实现用这个内部参数做一些聪明的事情。因此,每个bucket的值数是O(1),找到正确的bucket也是O(1)。这就是这样一个实现如何检索O(1)中的任何值。