Path: csiph.com!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder2.hal-mli.net!de-l.enfer-du-nord.net!feeder1.enfer-du-nord.net!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail
From: Robert Klemme <shortcutter@googlemail.com>
Newsgroups: comp.lang.java.programmer
Subject: Re: idea for more efficient HashMap
Date: Sun, 13 Jan 2013 19:44:50 +0100
Lines: 39
Message-ID: <algdl5Ff2dvU1@mid.individual.net>
References: <9hc2f8ltgn1bmdsrk8vb9kuu1vi5dkl2r5@4ax.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-Trace: individual.net hOP+9b0N1+zUMrNuqJwoJQ2ORidFl34qMgwIHuUILnr9hkp/OHDgvnMtdOrSdfR8g=
Cancel-Lock: sha1:JI9lui04P0MqF3PaaFZN/iRrx8c=
User-Agent: Mozilla/5.0 (Windows NT 6.0; WOW64; rv:17.0) Gecko/20130107 Thunderbird/17.0.2
In-Reply-To: <9hc2f8ltgn1bmdsrk8vb9kuu1vi5dkl2r5@4ax.com>
Xref: csiph.com comp.lang.java.programmer:21382

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/