Re: idea for more efficient HashMap

From:

Robert Klemme <shortcutter@googlemail.com>

Newsgroups:

comp.lang.java.programmer

Date:

Sun, 20 Jan 2013 20:28:36 +0100

Message-ID:

<am2ur4FllauU1@mid.individual.net>

On 18.01.2013 04:30, Kevin McMurtrie wrote:

In article <50F7C307.7060407@telia.com>,
Lars Enderin <lars.enderin@telia.com> 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 <9hc2f8ltgn1bmdsrk8vb9kuu1vi5dkl2r5@4ax.com>,
Roedy Green <see_website@mindprod.com.invalid> 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/