Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > idea for more efficient HashMap

Reply
Thread Tools

idea for more efficient HashMap

 
 
Roedy Green
Guest
Posts: n/a
 
      01-12-2013
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.
 
Reply With Quote
 
 
 
 
Stefan Ram
Guest
Posts: n/a
 
      01-12-2013
Roedy Green <(E-Mail Removed)> writes:
>What if you could implement an interface on your objects so that
>HashMap could use them directly without separate key or Entry glue?.


http://en.wikipedia.org/wiki/Linked_...ternal_storage

 
Reply With Quote
 
 
 
 
Volker Borchert
Guest
Posts: n/a
 
      01-12-2013
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 <(E-Mail Removed)>
"I'm a mechanic, not a doctor." Volker Borchert <(E-Mail Removed)>
 
Reply With Quote
 
Robert Klemme
Guest
Posts: n/a
 
      01-13-2013
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/
 
Reply With Quote
 
Kevin McMurtrie
Guest
Posts: n/a
 
      01-15-2013
In article <(E-Mail Removed)>,
Roedy Green <(E-Mail Removed)> 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
 
Reply With Quote
 
Robert Klemme
Guest
Posts: n/a
 
      01-16-2013
On Tuesday, January 15, 2013 6:56:29 AM UTC+1, Kevin McMurtrie wrote:
> In article <(E-Mail Removed)>,
> Roedy Green <(E-Mail Removed)> 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
 
Reply With Quote
 
Lars Enderin
Guest
Posts: n/a
 
      01-17-2013
2013-01-16 23:31, Robert Klemme skrev:
> On Tuesday, January 15, 2013 6:56:29 AM UTC+1, Kevin McMurtrie wrote:
>> In article <(E-Mail Removed)>,
>> Roedy Green <(E-Mail Removed)> 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
 
Reply With Quote
 
Kevin McMurtrie
Guest
Posts: n/a
 
      01-18-2013
In article <(E-Mail Removed)>,
Lars Enderin <(E-Mail Removed)> 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 <(E-Mail Removed)>,
> >> Roedy Green <(E-Mail Removed)> 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
 
Reply With Quote
 
Robert Klemme
Guest
Posts: n/a
 
      01-20-2013
On 18.01.2013 04:30, Kevin McMurtrie wrote:
> In article <(E-Mail Removed)>,
> Lars Enderin <(E-Mail Removed)> 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 <(E-Mail Removed)>,
>>>> Roedy Green <(E-Mail Removed)> 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/
 
Reply With Quote
 
Eric Sosman
Guest
Posts: n/a
 
      01-20-2013
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
http://www.velocityreviews.com/forums/(E-Mail Removed)d
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
reuse HashMap$Entry (or HashMap in total) to avoid millions of allocations Vince Darley Java 4 03-02-2010 07:48 AM
java.util.Properties extending from HashMap<Object, Object> insteadof HashMap<String, String> Rakesh Java 10 04-08-2008 04:22 AM
Efficient hashmap serialization? Sn0tters@yahoo.co.uk Java 16 09-07-2005 02:27 PM
Nested conditional expressions ---- good idea/bad idea? nimmi_srivastav@yahoo.com C Programming 10 02-02-2005 10:51 PM
An efficient computation idea. Please comment Aaron Fude Java 10 12-20-2004 07:18 PM



Advertisments