Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-1224565

Hashtable growth should be based on prime numbers

    XMLWordPrintable

    Details

      Description

      From ###@###.### Fri Oct 13 10:17:08 1995
      From: ###@###.### (Ken Arnold - Sun Labs)
      To: arthur.vanhoff@Eng
      Subject: primes in hash table

      I'm submitting the following as a bug, but since the bug report doesn't
      give me any ack that it recieved the report, I'm sending it to you, too.

      I'm reporting the lack-of-ack to the Appropriate Authorities...

      The java.util.Hashtable class doesn't know from primes. It
      takes any initial capacity I give it, and it doubles (!) the
      size when it runs out of space, thereby guaranteeing an even
      number, not a prime. It is well known that hash
      tables are most efficient (by a large amount, on average)
      when the size of the hash table is prime. This is usually
      accomplished by having a table of known primes, or a simple
      test for primeness, since it usually doesn't take very long
      to find the next prime by rounding up until you find one.

      At the very least, growth should be by 2*size - 1, which has
      a *tendency* to be prime, if size is already prime, but that's
      pretty crude.

        Attachments

          Issue Links

            Activity

              People

              Assignee:
              jjb Josh Bloch
              Reporter:
              ahoffsunw Arthur Hoff (Inactive)
              Votes:
              0 Vote for this issue
              Watchers:
              0 Start watching this issue

                Dates

                Created:
                Updated:
                Resolved:
                Imported:
                Indexed: