idea for more efficient HashMap

Discussion in 'Java' started by Roedy Green, Jan 12, 2013.

  1. Roedy Green

    Roedy Green Guest

    Inside HashMap are little glue Entry objects that point to the key and
    value.

    What if you could implement an interface on your objects so that
    HashMap could use them directly without separate key or Entry glue?.

    e.g. getKey()
    getPrev()
    getNext()
    setPrev()
    setNext()

    One drawback would be your objects could live on only one such
    space-efficient HashMap.
    --
    Roedy Green Canadian Mind Products http://mindprod.com
    Students who hire or con others to do their homework are as foolish
    as couch potatoes who hire others to go to the gym for them.
     
    Roedy Green, Jan 12, 2013
    #1
    1. Advertising

  2. Roedy Green

    Stefan Ram Guest

    Stefan Ram, Jan 12, 2013
    #2
    1. Advertising

  3. Roedy Green wrote:
    > Inside HashMap are little glue Entry objects that point to the key and
    > value.
    >
    > What if you could implement an interface on your objects so that
    > HashMap could use them directly without separate key or Entry glue?.
    >
    > e.g. getKey()
    > getPrev()
    > getNext()
    > setPrev()
    > setNext()
    >
    > One drawback would be your objects could live on only one such
    > space-efficient HashMap.


    Use linear probing instead of chained buckets. IdentityHashMap does so.

    --

    "I'm a doctor, not a mechanic." Dr Leonard McCoy <>
    "I'm a mechanic, not a doctor." Volker Borchert <>
     
    Volker Borchert, Jan 12, 2013
    #3
  4. On 12.01.2013 10:55, Roedy Green wrote:
    > Inside HashMap are little glue Entry objects that point to the key and
    > value.
    >
    > What if you could implement an interface on your objects so that
    > HashMap could use them directly without separate key or Entry glue?.
    >
    > e.g. getKey()
    > getPrev()
    > getNext()
    > setPrev()
    > setNext()
    >
    > One drawback would be your objects could live on only one such
    > space-efficient HashMap.


    I've once implemented a hash map which uses double hashingand uses a
    single Object[] for storage of keys and values. It creates Entry
    instances on the fly while iterating. We did this to get rid of a few
    hundred thousand Entry instances and improve GC behavior of the
    application. Works pretty good.

    http://en.wikipedia.org/wiki/Double_hashing

    Side benefit of that implementation was that you get
    ConcurrentModificationException only if the map needed to be resized as
    part of an insert operation.

    I cannot share this implementation here as it is proprietary code. But
    you should pretty much have everything to implement it yourself. If you
    do it do not forget to create meaningful unit tests.

    Kind regards

    robert

    --
    remember.guy do |as, often| as.you_can - without end
    http://blog.rubybestpractices.com/
     
    Robert Klemme, Jan 13, 2013
    #4
  5. In article <>,
    Roedy Green <> wrote:

    > Inside HashMap are little glue Entry objects that point to the key and
    > value.
    >
    > What if you could implement an interface on your objects so that
    > HashMap could use them directly without separate key or Entry glue?.
    >
    > e.g. getKey()
    > getPrev()
    > getNext()
    > setPrev()
    > setNext()
    >
    > One drawback would be your objects could live on only one such
    > space-efficient HashMap.


    I've done this when efficiency demanded it. The downside is that you
    can't implement java.util.Map or java.util.Dictionary because of the way
    put(K,V) is declared.

    There's no need for hashed storage in Maps. Hashing is a good general
    purpose performer but special cases can do better. Maps having 1 to 10
    elements may perform better with the keys and values interleaved in one
    array. A search tree (TreeMap) can perform better when keys are large.
    --
    I will not see posts from Google because I must filter them as spam
     
    Kevin McMurtrie, Jan 15, 2013
    #5
  6. On Tuesday, January 15, 2013 6:56:29 AM UTC+1, Kevin McMurtrie wrote:
    > In article <>,
    > Roedy Green <> wrote:
    > > Inside HashMap are little glue Entry objects that point to the key and
    > > value.

    >
    > > What if you could implement an interface on your objects so that
    > > HashMap could use them directly without separate key or Entry glue?.
    > >

    >
    > > e.g. getKey()
    > > getPrev()
    > > getNext()
    > > setPrev()
    > > setNext()
    > >

    >
    > > One drawback would be your objects could live on only one such
    > > space-efficient HashMap.

    >
    > I've done this when efficiency demanded it. The downside is that you
    > can't implement java.util.Map or java.util.Dictionary because of the way
    > put(K,V) is declared.


    Why that? I actually have done that implementation (see above) and it is consistent with the Map interface.

    > I will not see posts from Google because I must filter them as spam


    That might be a mistake - you'll might lose valuable feedback that way.

    Kind regards

    robert
     
    Robert Klemme, Jan 16, 2013
    #6
  7. Roedy Green

    Lars Enderin Guest

    2013-01-16 23:31, Robert Klemme skrev:
    > On Tuesday, January 15, 2013 6:56:29 AM UTC+1, Kevin McMurtrie wrote:
    >> In article <>,
    >> Roedy Green <> wrote:
    >>> Inside HashMap are little glue Entry objects that point to the key and
    >>> value.

    >>
    >>> What if you could implement an interface on your objects so that
    >>> HashMap could use them directly without separate key or Entry glue?.
    >>>

    >>
    >>> e.g. getKey()
    >>> getPrev()
    >>> getNext()
    >>> setPrev()
    >>> setNext()
    >>>

    >>
    >>> One drawback would be your objects could live on only one such
    >>> space-efficient HashMap.

    >>
    >> I've done this when efficiency demanded it. The downside is that you
    >> can't implement java.util.Map or java.util.Dictionary because of the way
    >> put(K,V) is declared.

    >
    > Why that? I actually have done that implementation (see above) and it is consistent with the Map interface.
    >
    >> I will not see posts from Google because I must filter them as spam

    >
    > That might be a mistake - you'll might lose valuable feedback that way.
    >


    He will not see your post then...

    --
    Lars Enderin
     
    Lars Enderin, Jan 17, 2013
    #7
  8. In article <>,
    Lars Enderin <> wrote:

    > 2013-01-16 23:31, Robert Klemme skrev:
    > > On Tuesday, January 15, 2013 6:56:29 AM UTC+1, Kevin McMurtrie wrote:
    > >> In article <>,
    > >> Roedy Green <> wrote:
    > >>> Inside HashMap are little glue Entry objects that point to the key and
    > >>> value.
    > >>
    > >>> What if you could implement an interface on your objects so that
    > >>> HashMap could use them directly without separate key or Entry glue?.
    > >>>
    > >>
    > >>> e.g. getKey()
    > >>> getPrev()
    > >>> getNext()
    > >>> setPrev()
    > >>> setNext()
    > >>>
    > >>
    > >>> One drawback would be your objects could live on only one such
    > >>> space-efficient HashMap.
    > >>
    > >> I've done this when efficiency demanded it. The downside is that you
    > >> can't implement java.util.Map or java.util.Dictionary because of the way
    > >> put(K,V) is declared.

    > >
    > > Why that? I actually have done that implementation (see above) and it is
    > > consistent with the Map interface.
    > >
    > >> I will not see posts from Google because I must filter them as spam

    > >
    > > That might be a mistake - you'll might lose valuable feedback that way.
    > >

    >
    > He will not see your post then...


    The Google filter is real. Google doesn't maintain their systems so
    they're employed by Chinese crime gangs to flood many Usenet groups.

    My original point is that you can't gracefully enforce insertion of an
    object having the key, value, and collision link together when put(K,V)
    takes two arguments. It's unfortunate that Dictionary defines setter
    methods. There are so many cases where I want a widely supported
    implementation of V get(K) without the other things. Maybe if interface
    compatibility was more flexible it wouldn't be a problem.
    --
    I will not see posts from Google because I must filter them as spam
     
    Kevin McMurtrie, Jan 18, 2013
    #8
  9. On 18.01.2013 04:30, Kevin McMurtrie wrote:
    > In article <>,
    > Lars Enderin <> wrote:
    >
    >> 2013-01-16 23:31, Robert Klemme skrev:
    >>> On Tuesday, January 15, 2013 6:56:29 AM UTC+1, Kevin McMurtrie wrote:
    >>>> In article <>,
    >>>> Roedy Green <> wrote:
    >>>>> Inside HashMap are little glue Entry objects that point to the key and
    >>>>> value.
    >>>>
    >>>>> What if you could implement an interface on your objects so that
    >>>>> HashMap could use them directly without separate key or Entry glue?.
    >>>>>
    >>>>
    >>>>> e.g. getKey()
    >>>>> getPrev()
    >>>>> getNext()
    >>>>> setPrev()
    >>>>> setNext()
    >>>>>
    >>>>
    >>>>> One drawback would be your objects could live on only one such
    >>>>> space-efficient HashMap.
    >>>>
    >>>> I've done this when efficiency demanded it. The downside is that you
    >>>> can't implement java.util.Map or java.util.Dictionary because of the way
    >>>> put(K,V) is declared.
    >>>
    >>> Why that? I actually have done that implementation (see above) and it is
    >>> consistent with the Map interface.
    >>>
    >>>> I will not see posts from Google because I must filter them as spam
    >>>
    >>> That might be a mistake - you'll might lose valuable feedback that way.

    >>
    >> He will not see your post then...


    As I said above... :)

    > The Google filter is real. Google doesn't maintain their systems so
    > they're employed by Chinese crime gangs to flood many Usenet groups.


    My Usenet provider does a pretty decent job filtering spam for around 10
    EUR / year. So there are definitively ways to handle that.

    > My original point is that you can't gracefully enforce insertion of an
    > object having the key, value, and collision link together when put(K,V)
    > takes two arguments.


    What exactly do you mean by "collision link"?

    > It's unfortunate that Dictionary defines setter
    > methods. There are so many cases where I want a widely supported
    > implementation of V get(K) without the other things.


    Are you referring to the setter of Map.Entry<K,V>?

    Kind regards

    robert

    --
    remember.guy do |as, often| as.you_can - without end
    http://blog.rubybestpractices.com/
     
    Robert Klemme, Jan 20, 2013
    #9
  10. Roedy Green

    Eric Sosman Guest

    On 1/17/2013 10:30 PM, Kevin McMurtrie wrote:
    >[...]
    > My original point is that you can't gracefully enforce insertion of an
    > object having the key, value, and collision link together when put(K,V)
    > takes two arguments. It's unfortunate that Dictionary defines setter
    > methods. There are so many cases where I want a widely supported
    > implementation of V get(K) without the other things. Maybe if interface
    > compatibility was more flexible it wouldn't be a problem.


    One approach would be to write a class implementing the
    Map<K,V> interface, but whose put(K,V) method throws an
    exception (just as an UnmodifiableMap's does). Sketch:

    interface Mappable<K,V> {
    K getKey();
    V getValue();
    Mappable<K,V> getNext();
    // ...
    }

    class Mapping<K,V> implements Map<K,V> {
    @Override
    public V put(K key, V value) {
    throw new UnsupportedOperationException();
    }

    // Not an @Override
    public void put(Mappable<K,V> entry) {
    // ...
    }

    // ...
    }

    True, run-time instead of compile-time detection of the use
    of an unsupported method is not exactly graceful, but there's
    certainly precedent. (Maybe you can @deprecate the put(K,V)
    method; off-hand I don't know whether that works with a method
    that's not deprecated by its interface -- and even if you can,
    that only provides a compile-time guard for explicit uses of
    the Mapping class, not for references via its Map interface.)

    --
    Eric Sosman
    d
     
    Eric Sosman, Jan 20, 2013
    #10
  11. Roedy Green

    Roedy Green Guest

    On Thu, 17 Jan 2013 19:30:58 -0800, Kevin McMurtrie
    <> wrote, quoted or indirectly quoted someone
    who said :

    > Google doesn't maintain their systems so
    >they're employed by Chinese crime gangs to flood many Usenet groups.


    Nobody "maintains" (moderates) posts entering the newsgroups via other
    streams either. The only reason to deprecate Google Groups is they
    are more accessible for newbies. For me, they are the ones I want to
    talk to most.
    --
    Roedy Green Canadian Mind Products http://mindprod.com
    The first 90% of the code accounts for the first 90% of the development time.
    The remaining 10% of the code accounts for the other 90% of the development
    time.
    ~ Tom Cargill Ninety-ninety Law
     
    Roedy Green, Jan 29, 2013
    #11
  12. Roedy Green

    Arne Vajhøj Guest

    On 1/29/2013 4:41 AM, Roedy Green wrote:
    > On Thu, 17 Jan 2013 19:30:58 -0800, Kevin McMurtrie
    > <> wrote, quoted or indirectly quoted someone
    > who said :
    >> Google doesn't maintain their systems so
    >> they're employed by Chinese crime gangs to flood many Usenet groups.

    >
    > Nobody "maintains" (moderates) posts entering the newsgroups via other
    > streams either. The only reason to deprecate Google Groups is they
    > are more accessible for newbies. For me, they are the ones I want to
    > talk to most.


    I am sure that they frequently click on your links.

    Arne
     
    Arne Vajhøj, Jan 30, 2013
    #12
  13. On Tue, 29 Jan 2013 22:03:28 -0500, Arne Vajhøj <>
    wrote:

    >On 1/29/2013 4:41 AM, Roedy Green wrote:
    >> On Thu, 17 Jan 2013 19:30:58 -0800, Kevin McMurtrie
    >> <> wrote, quoted or indirectly quoted someone
    >> who said :
    >>> Google doesn't maintain their systems so
    >>> they're employed by Chinese crime gangs to flood many Usenet groups.

    >>
    >> Nobody "maintains" (moderates) posts entering the newsgroups via other
    >> streams either. The only reason to deprecate Google Groups is they
    >> are more accessible for newbies. For me, they are the ones I want to
    >> talk to most.

    >
    >I am sure that they frequently click on your links.


    I have clicked on a link of Roedy's when the link was of a
    subject of interest to me. I like to have helpful things available.

    Sincerely,

    Gene Wirchenko
     
    Gene Wirchenko, Jan 30, 2013
    #13
  14. Roedy Green

    Arne Vajhøj Guest

    On 1/30/2013 2:34 PM, Gene Wirchenko wrote:
    > On Tue, 29 Jan 2013 22:03:28 -0500, Arne Vajhøj <>
    > wrote:
    >
    >> On 1/29/2013 4:41 AM, Roedy Green wrote:
    >>> On Thu, 17 Jan 2013 19:30:58 -0800, Kevin McMurtrie
    >>> <> wrote, quoted or indirectly quoted someone
    >>> who said :
    >>>> Google doesn't maintain their systems so
    >>>> they're employed by Chinese crime gangs to flood many Usenet groups.
    >>>
    >>> Nobody "maintains" (moderates) posts entering the newsgroups via other
    >>> streams either. The only reason to deprecate Google Groups is they
    >>> are more accessible for newbies. For me, they are the ones I want to
    >>> talk to most.

    >>
    >> I am sure that they frequently click on your links.

    >
    > I have clicked on a link of Roedy's when the link was of a
    > subject of interest to me. I like to have helpful things available.


    If you liked the content then good for you.

    As you probably have noticed, then there is not universal agreement
    on the quality of those pages.

    I would go to Wikipedia instead.

    Arne
     
    Arne Vajhøj, Jan 31, 2013
    #14
  15. On Wed, 30 Jan 2013 21:35:40 -0500, Arne Vajhøj <>
    wrote:

    >On 1/30/2013 2:34 PM, Gene Wirchenko wrote:


    [snip]

    >> I have clicked on a link of Roedy's when the link was of a
    >> subject of interest to me. I like to have helpful things available.

    >
    >If you liked the content then good for you.
    >
    >As you probably have noticed, then there is not universal agreement
    >on the quality of those pages.


    That is true of the Internet in general. Planning on giving up
    on the Net?

    >I would go to Wikipedia instead.


    Any port in a storm.

    Sincerely,

    Gene Wirchenko
     
    Gene Wirchenko, Jan 31, 2013
    #15
  16. Roedy Green

    Arne Vajhøj Guest

    On 1/31/2013 1:47 PM, Gene Wirchenko wrote:
    > On Wed, 30 Jan 2013 21:35:40 -0500, Arne Vajhøj <>
    > wrote:
    >
    >> On 1/30/2013 2:34 PM, Gene Wirchenko wrote:

    >
    > [snip]
    >
    >>> I have clicked on a link of Roedy's when the link was of a
    >>> subject of interest to me. I like to have helpful things available.

    >>
    >> If you liked the content then good for you.
    >>
    >> As you probably have noticed, then there is not universal agreement
    >> on the quality of those pages.

    >
    > That is true of the Internet in general. Planning on giving up
    > on the Net?


    If there were a better network: yes. But there isn't.

    There are better places than Roedy's site for information
    about Java.

    Arne
     
    Arne Vajhøj, Feb 2, 2013
    #16
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Vince Darley
    Replies:
    4
    Views:
    4,429
    emilchacko
    Mar 2, 2010
  2. Aaron Fude
    Replies:
    10
    Views:
    568
    Mark Thornton
    Dec 20, 2004
  3. Replies:
    16
    Views:
    14,770
  4. Replies:
    10
    Views:
    1,243
    Big K
    Feb 2, 2005
  5. Rakesh
    Replies:
    10
    Views:
    12,180
    Mike Schilling
    Apr 8, 2008
Loading...

Share This Page