Results 1 to 1 of 1

Thread: Hashmaps Question/Hypothesis

  1. #1 Hashmaps Question/Hypothesis 
    Forum Freshman
    Join Date
    Jul 2019
    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.

    Last edited by JordanonTech; January 21st, 2020 at 11:09 PM.
    Reply With Quote  


Similar Threads

  1. Who could help me with this hypothesis question?
    By Rosalinevii in forum Education
    Replies: 4
    Last Post: April 21st, 2013, 09:12 PM
  2. Hypothesis Help!
    By Theanimal in forum Biology
    Replies: 1
    Last Post: March 11th, 2013, 02:47 AM
  3. The hypothesis of ones
    By Mark Ian in forum Pseudoscience
    Replies: 0
    Last Post: October 14th, 2010, 07:55 PM
  4. A question regarding forming a hypothesis
    By tarektarek in forum Personal Theories & Alternative Ideas
    Replies: 0
    Last Post: January 5th, 2010, 09:53 PM
  5. Hypothesis
    By Raymond K in forum Physics
    Replies: 6
    Last Post: May 2nd, 2008, 10:27 AM
Tags for this Thread

View Tag Cloud

Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts