A new fast hash table in response to Google’s new fast hash table

Re:A new fast hash table in response to Google’s new fast ha... by ant6n on Tuesday May 29, 2018 @09:03AM (#17178734)

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

[ Parent | on HN ]

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 ]

Re:A new fast hash table in response to Google’s new fast ha... by zzzcpan on Tuesday May 29, 2018 @12:19PM (#17180527)

Only some primitive hash table algorithms have O(n) worst case access. No one implements those algorithms anymore though.

[ Parent | on HN ]

Re:A new fast hash table in response to Google’s new fast ha... by IncRnd on Tuesday May 29, 2018 @10:43AM (#17179552)

Big-O specifically refers to worst case, though, people use Big-O to refer to average or worst case scale in-practice.

[ Parent | on HN ]