|
|
|
|
|
|
by ot
3738 days ago
|
|
|
What do you mean by constant-level time complexity? That the number of levels is constant? That's just because you bound the total number of keys to 2^32. With that constraint, anything is constant-time, even linear search. This is basically a trie built on the chinese-reminder decompositions of the keys. I'm not an expert in Go, but I'm sure you can use fixed-size arrays, and thus implement any open-addressing hash table with no space overhead. |
|
|
Comment 1: O(2 * 3 ... 29) is indeed constant level, but we don't like it. The put/get/delete operations on this tree are all constant level, but at most Sum(lg2~lg29) checks.
Comment 2: Yes, we can use fixed-size arrays and build an open-addressing hash table with no space overhead (load factor is 1), this makes 100% table space utilization, but any insertions would cause table to resize, which is an O(N) copy (where N is the table size). However, insertions on a tree node can be done locally, without moving the whole tree.