哈希表的优点

哈希表的优点

如果你认为哈希表不实用、不方便或者不巧妙，请考虑如下情形：当一个哈希表有 n 个键和 k 个桶时，查找 n 个键的时间复杂度将从使用线性查找的 O(n) 下降至 O(n/k)！尽管这点改进看起来不起眼，你也必须意识到对于一个有 20 个槽的哈希数组，查找的次数将会下降为原来的 1/20！这让哈希表非常适合用于搭建词典或者其他这类需要大量数据查找的应用。