News for hackers. Stuff that matters.

A comment on A new fast hash table in response to Google’s new fast hash table. Parent comment

Re:A new fast hash table in response to Google’s new fast ha... by bufferoverflow on Tuesday May 29, 2018 @09:34AM (#17178989)
Average O(1), worst case O(n)

So worse than a B-tree or a Red-black tree for the worst case.

[ Parent | on HN ]
Re:A new fast hash table in response to Google’s new fast ha... by ant6n on Thursday May 31, 2018 @03:35AM (#17194628)
"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.
[ Parent | on HN ]