1. I have a question/hypothesis about hashmaps: They're always described as "O (1)" or "constant-time" algorithms because if you always use the same hash-width, certain operations always take the same amount of time. But it's the same result if you pad a binary tree to always be, e.g., 32 nodes deep.

If you have eight sets of 256 elements each and two sets of 4.2 billion each, can't you implement many of the operations through SIMD, let's say 64-bit MMX, to perform the same operation, on all eight 256 element sets at once in one MMX register, and it will take the same time as the operation on two 32-bit hashmaps?

If your CPU runs 8bit instructions four times faster than 32-bit ones, no need to do SIMD. The 8-bit (256 elements) hashmap will run twice as fast as the 16-bit hash width 65,536), which will run 2x speed vs 32-bit width (4.2 billion) even without parallelization, right?

But wouldn't that mean any hashmap will be "O (log in)" or "logarithmic time" if it starts as 8bit and converts in place to 16, 32, etc.? If in place is complicated, automatically making a new one and copying from old one, then deleting old, is the same, right? The only issue I can imagine is needing to store over 4.2 billion in one map on a 32-bit computer that lacks 64-bit extensions.

But that requires PAE to solve memory constraints anyways, and is a 64-bit Bigint library really slower than PAE? 128-bit would require something way bigger (and slower) than PAE, probably no faster than 128-bit Bigint libraries.

Of course, with the much slower, arbitrary-length Bigint libraries, this can scale infinitely, just like the "O (log)" trees.

What am I missing? It seems like my solution would be too self-evident, even to patent, and that everyone must have thought of it very early on.

2.