大家下午好
我们说哈希表有 O(1) 查找（假设我们有键），而链表有 O(1) 查找下一个节点（假设我们有对当前节点的引用）。
但是，由于Big-O 表示法的工作原理，它在表示（或区分）算法x的成本与算法x + m的成本方面不是很有用。
例如，即使我们将哈希表的查找和链表的查找都标记为 O(1)，这两个 O(1) 归结为确实非常不同的步数，
链表的查找固定在x步。但是，哈希表的查找是可变的。哈希表查找的成本取决于哈希函数的成本，因此哈希表查找所需的步数为：x + m，
其中x是一个固定数字
m是一个未知的变量值
换句话说，即使我们将这两个操作都称为 O(1)，哈希表查找的成本也比链表查找的成本高出一个数量级。
Big-O 表示法专门针对输入数据集合的大小。这确实有其优点，但也有其缺点，当我们将所有非n变量折叠并归一化为 1 时可以看出。我们再也看不到其中的 m 变量（散列函数）。
除了 Big-O 表示法之外，我们是否可以使用另一种（已建立的）表示法来表示固定成本 O(1) 表示x操作和可变成本 O(1) 表示x + m ( m，散列功能）操作次数？
"~" 包括常数因子 - 参见巴赫曼函数族
字面量 O(1)，这意味着正好 1 次操作
除非它没有。大 O-Notation 涉及与输入相关的复杂性的相对比较。如果算法确实采用恒定数量的步骤，完全独立于输入的大小，那么确切的步骤数量并不重要。
看一下 O(n) 的（非正式）定义：
意思是：有一定的k，所以对于每个n函数f都小于函数g。
在上述情况下，哈希表查找和链表查找将是f，并且g将是g(n) = 1。对于每种情况，您都可以找到一个kthat f(n) <= g(n) * k。
现在，这k不需要修复，它可以根据平台、实现、特定硬件而有所不同。唯一有趣的一点是它存在。这就是为什么哈希表查找和链表节点查找都是 O(1) 的原因：无论输入如何，两者都具有恒定的复杂性。在评估算法时，这很有趣，而不是物理步骤。
特别是关于 Hashtable 查找
是的，哈希函数确实需要可变数量的操作（取决于实现）。但是，它不会根据输入的大小进行可变数量的操作。Big O-Nation 专门针对输入数据集合的大小。散列函数采用单个元素。对于算法的评估，某个函数是否需要 10、20、50 或 100 次操作都没有关系，如果操作数不随输入大小而增加，则为 O(1)。在大 O-Notation 中无法区分这一点，因为这不是大 O-Notation 的意义所在。
问题是“操作数量”高度依赖于上下文。事实上，这就是发明大 O 表示法的原因——它似乎在对大量计算机进行建模时效果很好。
此外，程序员的“操作”数量并不意味着它实际花费了多少时间（例如它是否已经在缓存中？）或硬件实际花费了多少步骤（你的处理器究竟做了什么？它有微操作吗？）或者甚至有多少操作被指定给处理器（你的编译器为你做了什么？）。这些都是关注点，即使你试图定义一个足够抽象有用的精确概念。
所以。现在，它是 Big-O 与“操作”——无论“操作”对您和您的同事当时意味着什么。