2 ms·

I thought a hash table has O(n) access.

• bufferoverflow 8y ago
  Average O(1), worst case O(n) So worse than a B-tree or a Red-black tree for the worst case.
  • ant6n 8y ago
    "Average O(1)" is an oxymoron. Big Oh is about the worst case. The only thing that makes sense is "Amortized O(1)", but I believe its possible to create access cases where hash tables are slower.
• IncRnd 8y ago
  Big-O specifically refers to worst case, though, people use Big-O to refer to average or worst case scale in-practice.
• zzzcpan 8y ago
  Only some primitive hash table algorithms have O(n) worst case access. No one implements those algorithms anymore though.