Loading ...
Sorry, an error occurred while loading the content.

983Re: Sorting the keys of formatted (pretty printed) JSON output

Expand Messages
  • kriszyp
    Apr 10, 2008
    • 0 Attachment
      --- In json@yahoogroups.com, John Cowan <cowan@...> wrote:
      >
      > Tatu Saloranta scripsit:
      >
      > > > There would be a penalty for keeping a TreeMap versus a HashMap.
      > > > HashMap obviously performs better (constant time put & get) for
      when
      > >
      > > I understand this, and it's a valid point.
      >
      > Actually, it isn't. Even though the javadoc claims that get and put
      > are constant time, a moment's reflection shows that this cannot be so.
      >
      > HashMap is implemented (in OpenJDK, and almost certainly in earlier
      > versions) using an array of specialized objects that implement
      Map.Entry.
      > Each element of the array is one hash bucket, and the Entry objects form
      > a linked list. So average get/put time is approximately N/c*2, where c
      > is the capacity (initially 16 unless specified otherwise), which is
      O(N).
      > The hope is that N/c*2 is always small enough that the performance looks
      > like O(1), but as N grows, c is increased using a full rehash, which is
      > again O(N) and is independent of c.

      Not true. Full rehashes are indeed O(N), but they take place at a
      frequency proportional to 1/c because each time a rehash takes place
      the size is doubled, so the rehashes become farther apart the larger c
      gets. Therefore the average rehash time for a put operation is
      O(N*1/c) which averages to constant time. Both get and put only have
      to iterate through their own bucket, so as long as the hash method is
      reasonable, both get and put are indeed O(1), constant time operations.
      Kris
    • Show all 7 messages in this topic