Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #18437 > unrolled thread

Question about HashMap and Map.Entry ...

Back to article view | Back to comp.lang.java.programmer

Contents

  Question about HashMap and Map.Entry ... Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2012-08-30 17:39 +0000
    Re: Question about HashMap and Map.Entry ... markspace <-@.> - 2012-08-30 10:46 -0700
      Re: Question about HashMap and Map.Entry ... Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-08-30 11:15 -0700
        Re: Question about HashMap and Map.Entry ... Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2012-08-30 19:24 +0000
          Re: Question about HashMap and Map.Entry ... Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2012-08-30 19:32 +0000
            Re: Question about HashMap and Map.Entry ... Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-08-30 13:08 -0700
              Re: Question about HashMap and Map.Entry ... Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2012-08-30 21:55 +0000
                Re: Question about HashMap and Map.Entry ... Robert Klemme <shortcutter@googlemail.com> - 2012-08-31 07:27 +0200
                  Re: Question about HashMap and Map.Entry ... Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2012-08-31 10:26 +0000
                    Re: Question about HashMap and Map.Entry ... Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-08-31 11:22 -0700
                      Re: Question about HashMap and Map.Entry ... Robert Klemme <shortcutter@googlemail.com> - 2012-09-01 11:06 +0200
          Re: Question about HashMap and Map.Entry ... markspace <-@.> - 2012-08-30 14:30 -0700
            Re: Question about HashMap and Map.Entry ... Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2012-08-30 22:42 +0000
          Re: Question about HashMap and Map.Entry ... markspace <-@.> - 2012-08-30 14:34 -0700
    Re: Question about HashMap and Map.Entry ... Lew <lewbloch@gmail.com> - 2012-08-30 13:42 -0700
      Re: Question about HashMap and Map.Entry ... Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> - 2012-08-30 22:34 +0000

#18437 — Question about HashMap and Map.Entry ...

Given a (Hash)Map<Long,Long> map and two Long values k and v,
Some task is to see if k is already in the map, and only if so,
then update the value in the map based on previous value and v.

Of course, that is trivial, and I've already implemented
it with containsKey(), get() and put().

It's just, that it seems to me that my piece of code
could be a bit *clearer*, if I could obtain the Map.Entry
for "k", and (if that isn't null) do getValue() and
setValue(...) on the Entry.

What I'm missing, however, is:
  How would I get the Entry for a given key?
(apart from scanning all through the entrySet())

PS: using 1.6, but also interested in future (i.e. 1.7 or 
   even newer) prospects, and also in (any) explicit reasons
   for *not* having some map.getEntry(K k).
   Also, such an Entry should be tied to the Map just like
   those in the entrySet().  NavigableMap has methods that
   return Entries with "snapshot"-semantics, which is *not*
   what I'm looking for.

[toc] | [next] | [standalone]

#18438

On 8/30/2012 10:39 AM, Andreas Leitgeb wrote:

> What I'm missing, however, is:
>    How would I get the Entry for a given key?


What about:

   Long value = hashMap.get( key );
   if( value != null )
     hashMap.put( key , newValue );

This only updates the value for key if key is already present.  I think 
that's what you said you are doing.  It assumes that "null" is not a 
valid value for any key.  (That can be changed as well, but it's 
basically a scan through the entries at that point.)

[toc] | [prev] | [next] | [standalone]

#18439

On 8/30/12 10:46 AM, markspace wrote:
> On 8/30/2012 10:39 AM, Andreas Leitgeb wrote:
>
>> What I'm missing, however, is:
>>    How would I get the Entry for a given key?
>
>
> What about:
>
>    Long value = hashMap.get( key );
>    if( value != null )
>      hashMap.put( key , newValue );
>
> This only updates the value for key if key is already present.  I think
> that's what you said you are doing.  It assumes that "null" is not a
> valid value for any key.  (That can be changed as well, but it's
> basically a scan through the entries at that point.)

In theory, this does more work than it needs to, computing the hash 
bucket twice, scanning any collisions on the key's buckets, etc...  In 
practice, this is fast enough for most operations.

I would like to suggest to the OP to look into Trove 
<http://trove4j.sourceforge.net/>, which has support for primitive 
collections (longs, rather than Longs), which may be much faster and 
more memory efficient, depending on your use-cases.

[toc] | [prev] | [next] | [standalone]

#18442

Daniel Pitts <newsgroup.nospam@virtualinfinity.net> wrote:
> On 8/30/12 10:46 AM, markspace wrote:
>> On 8/30/2012 10:39 AM, Andreas Leitgeb wrote:
>>> What I'm missing, however, is:
>>>    How would I get the Entry for a given key?
>> What about: [...] I think that's what you said you are doing.
You thought essentially right, markspace ;-)

> In theory, this does more work than it needs to, computing the hash 
> bucket twice,...

That lets it look like I was caring for performance and 
(premature, of course) optimization, which I've indeed
often a weakness for, but which isn't relevant for this
thread.

Let's say, I've got a method that takes an Map.Entry, and
the new value, and it updates the Entry's value accordingly.

So far I happened to use it for all keys in a Map, so 
I iterated the entrySet, and called the method on each
loop-cycle.

Now, I'd rather call that method for specific keys, and
that's how I'd arrive at the outset of this thread.

My choice is now:
a) duplicating the method's code into one that operates
     on the map directly for a key, or inlining the method's
     code directly into the loop-body. (what I did)
b) creating an anonymous "implementation" of Map.Entry
     with key&value, and writing the value back to the
     map unconditionally afterwards. (I don't care about
     eventually overwriting with same value)

but unfortunately not:
c) getting some darned Map-backed Entry just for that
     darned key ;-)

> I would like to suggest to the OP to look into Trove <...>,
> which has support for primitive collections (longs, rather
> than Longs), which may be much faster and more memory efficient,
> depending on your use-cases.

If the TLongLongHashMap had a method to return a
java.util.Map.Entry<Long,Long>, then I'd be all for it ;-)

But it was still interesting to read about adjustOrPutValue(),
foreach*() and putIfAbsent() methods. These might come in handy some
time, and it's good to know, these trove collections offer stuff beyond
merely wrapping the primitives directly, compared to java.util.HashMap.

[toc] | [prev] | [next] | [standalone]

#18443

Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> wrote:
> b) creating an anonymous "implementation" of Map.Entry
>      with key&value, and writing the value back to the
>      map unconditionally afterwards. (I don't care about
>      eventually overwriting with same value)

Damn, on re-read, I notice, that my own implementation of
Map.Entry could just hold a ref to the map and implement
setValue() to write the value back into the Map...

Maybe, even, the HashMap's entrySet()'s items even do that
for the Map-"backing". - I know, I could look into src.zip,
but probably won't.

[toc] | [prev] | [next] | [standalone]

#18445

On 8/30/12 12:32 PM, Andreas Leitgeb wrote:
> Andreas Leitgeb <avl@gamma.logic.tuwien.ac.at> wrote:
>> b) creating an anonymous "implementation" of Map.Entry
>>       with key&value, and writing the value back to the
>>       map unconditionally afterwards. (I don't care about
>>       eventually overwriting with same value)
>
> Damn, on re-read, I notice, that my own implementation of
> Map.Entry could just hold a ref to the map and implement
> setValue() to write the value back into the Map...
>
> Maybe, even, the HashMap's entrySet()'s items even do that
> for the Map-"backing". - I know, I could look into src.zip,
> but probably won't.
>
Or, if you know all the keys before hand, you can use instead Map<Long, 
MyLongWrapper> map.

MyLongWrapper would have .set() and .get(), or even .actUpon() depending 
on the semantics you need.

Again, I suggest Trove, I seem to recall they had an interface that 
supported exactly what you are trying to accomplish.

[toc] | [prev] | [next] | [standalone]

#18450

Daniel Pitts <newsgroup.nospam@virtualinfinity.net> wrote:
> On 8/30/12 12:32 PM, Andreas Leitgeb wrote:
>> Damn, on re-read, I notice, that my own implementation of
>> Map.Entry could just hold a ref to the map and implement
>> setValue() to write the value back into the Map...
> Or, if you know all the keys before hand, you can use instead Map<Long, 
> MyLongWrapper> map.

I know all the relevant keys before hand. I currently do
an initial map.put(k,0L) for each relevant "k".

> MyLongWrapper would have .set() and .get(), or even .actUpon()
> depending on the semantics you need.

Indeed, that is a more elegant approach, than mine.
Although it won't save me the extra containsKey(), as I'll
be also having "k"s that aren't in the map, I'll turn my
auxiliary Entry-taking method from the outer class into a
method of some inner class MyLongWrapper that only needs
the extra "v" as parameter...

> Again, I suggest Trove, I seem to recall they had an interface that 
> supported exactly what you are trying to accomplish.

Yep, they seem to have inspired your suggestion, but now
that I know it, I don't actually need TLong*HashMap 
anymore. (My processing on the values is none of these
trove-predefined ones, anyway)

[toc] | [prev] | [next] | [standalone]

#18464

On 30.08.2012 23:55, Andreas Leitgeb wrote:
> Daniel Pitts <newsgroup.nospam@virtualinfinity.net> wrote:
>> On 8/30/12 12:32 PM, Andreas Leitgeb wrote:
>>> Damn, on re-read, I notice, that my own implementation of
>>> Map.Entry could just hold a ref to the map and implement
>>> setValue() to write the value back into the Map...
>> Or, if you know all the keys before hand, you can use instead Map<Long,
>> MyLongWrapper> map.
>
> I know all the relevant keys before hand. I currently do
> an initial map.put(k,0L) for each relevant "k".
>
>> MyLongWrapper would have .set() and .get(), or even .actUpon()
>> depending on the semantics you need.
>
> Indeed, that is a more elegant approach, than mine.
> Although it won't save me the extra containsKey(), as I'll
> be also having "k"s that aren't in the map,

containsKey() is unnecessary work.  Just get(), and if it's null create 
a new MyLongWrapper.  Btw, if you use long as member instead of Long 
then you do not even necessarily have more objects.

containsKey() is only ever useful if you have null values in a Map or 
are just interested in the fact whether a key is present or not.  Other 
than that just get() is more efficient even though effects might be 
negligible.

Cheers

	robert

-- 
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/

[toc] | [prev] | [next] | [standalone]

#18469

Robert Klemme <shortcutter@googlemail.com> wrote:
> On 30.08.2012 23:55, Andreas Leitgeb wrote:
>> Daniel Pitts <newsgroup.nospam@virtualinfinity.net> wrote:
>>> Or, if you know all the keys before hand, you can use instead
>>>  Map<Long,MyLongWrapper> map.
>>> MyLongWrapper would have .set() and .get(), or even .actUpon()
>>> depending on the semantics you need.

My code now looks essentially like this: (containing class omitted)

  void doSomething() {
     // Val could be a static nested or a toplevel class, as well
     //  I've got it here for local context. I'd separate it out
     //  only if profiling results suggested doing so. ;-)
     final class Val {
        private long val=0; long getVal() { return val; }
        void actUpon(long arg) { val = some_formula_on_val_and_arg; }
     }
     Map<Long,Val> map = new HashMap<Long,Val>()
     for (Long key : listOfInterestingKeys) { map.put(key,new Val()); }

     // the main iteration: (each foo has two keys and a value)
     for (Foo foo : fooCollection) { Val fw;
        fw=map.get( foo.key1 ); if (fw != null) fw.actUpon(foo.value);
        fw=map.get( foo.key2 ); if (fw != null) fw.actUpon(foo.value);
        // plus some more stuff using also the "uninteresting" keys.
     }
     for (Map.Entry<Long,Val> me : map.entrySet() ) {
        doSomething(me.getKey(),me.getValue().getVal());
     }
  }

Again: thanks, Daniel Pitts, for pointing me the right direction
with a mutable value-wrapper class, instead of some Entry-alike!

> containsKey() is unnecessary work.  Just get(), and if it's null [...]

Was indeed. And my action for null happened to be "ignore".

> Btw, if you use long as member instead of Long then you do not even
> necessarily have more objects.

While that happened to apply to my case, it wasn't really a primary concern.

[toc] | [prev] | [next] | [standalone]

#18481

On 8/31/12 3:26 AM, Andreas Leitgeb wrote:
> Robert Klemme <shortcutter@googlemail.com> wrote:
>> On 30.08.2012 23:55, Andreas Leitgeb wrote:
>>> Daniel Pitts <newsgroup.nospam@virtualinfinity.net> wrote:
>>>> Or, if you know all the keys before hand, you can use instead
>>>>   Map<Long,MyLongWrapper> map.
>>>> MyLongWrapper would have .set() and .get(), or even .actUpon()
>>>> depending on the semantics you need.
>
> My code now looks essentially like this: (containing class omitted)
>
>    void doSomething() {
>       // Val could be a static nested or a toplevel class, as well
>       //  I've got it here for local context. I'd separate it out
>       //  only if profiling results suggested doing so. ;-)
>       final class Val {
>          private long val=0; long getVal() { return val; }
>          void actUpon(long arg) { val = some_formula_on_val_and_arg; }
>       }
>       Map<Long,Val> map = new HashMap<Long,Val>()
>       for (Long key : listOfInterestingKeys) { map.put(key,new Val()); }
>
>       // the main iteration: (each foo has two keys and a value)
>       for (Foo foo : fooCollection) { Val fw;
>          fw=map.get( foo.key1 ); if (fw != null) fw.actUpon(foo.value);
>          fw=map.get( foo.key2 ); if (fw != null) fw.actUpon(foo.value);
>          // plus some more stuff using also the "uninteresting" keys.
>       }
>       for (Map.Entry<Long,Val> me : map.entrySet() ) {
>          doSomething(me.getKey(),me.getValue().getVal());
>       }
>    }
>
> Again: thanks, Daniel Pitts, for pointing me the right direction
> with a mutable value-wrapper class, instead of some Entry-alike!
>
>> containsKey() is unnecessary work.  Just get(), and if it's null [...]
>
> Was indeed. And my action for null happened to be "ignore".
>
>> Btw, if you use long as member instead of Long then you do not even
>> necessarily have more objects.
>
> While that happened to apply to my case, it wasn't really a primary concern.
>
The real reason IMHO to use "long" over "Long", is that Long can be 
null, and sometimes that just doesn't make any sense semantically. The 
fact that it tends to be faster and use less memory is just a benefit.

Same goes for all primitives vs primitive wrappers.

[toc] | [prev] | [next] | [standalone]

#18497

On 08/31/2012 08:22 PM, Daniel Pitts wrote:

> The real reason IMHO to use "long" over "Long", is that Long can be
> null, and sometimes that just doesn't make any sense semantically. The
> fact that it tends to be faster and use less memory is just a benefit.
>
> Same goes for all primitives vs primitive wrappers.

Definitively agree.  I mentioned it only as an additional benefit. 
Another reason to use object types is of course that the data structure 
is a generic one (such as keys or values in a Map) so there is no other 
option. :-)

Kind regards

	robert

[toc] | [prev] | [next] | [standalone]

#18448

On 8/30/2012 12:24 PM, Andreas Leitgeb wrote:
> Daniel Pitts <newsgroup.nospam@virtualinfinity.net> wrote:
>> On 8/30/12 10:46 AM, markspace wrote:
>>> On 8/30/2012 10:39 AM, Andreas Leitgeb wrote:
>>>> What I'm missing, however, is:
>>>>     How would I get the Entry for a given key?
>>> What about: [...] I think that's what you said you are doing.
> You thought essentially right, markspace ;-)
>

OK...

>
> Let's say, I've got a method that takes an Map.Entry, and
> the new value, and it updates the Entry's value accordingly.
>
...
>
> Now, I'd rather call that method for specific keys, and
> that's how I'd arrive at the outset of this thread.


I think Lew has the correct analysis.  I was going more on gut instinct 
rather than analyzing carefully, but I don't see what is better, or more 
clear, or more desirable about your method, compared to the code I posted.

I think it would help if you actually posted your code.  I really can't 
fathom the use case for this, and English prose descriptions aren't 
helping.  I can barely understand what it is you are doing to implement 
this.  The "why" of it is completely beyond me.  Maybe some code will 
spark some kind of idea for improvement....

[toc] | [prev] | [next] | [standalone]

#18452

markspace <-@> wrote:
> ..., but I don't see what is better, or more 
> clear, or more desirable about your method, compared to the code I posted.

In hindsight, it was:
  "matching up with a previous less-than-ideal design decision."

Probably (unless something even better occurs to me soon), I'll write
a simple MyLongWrapper (as Daniel suggested), that will become the value-
type of that HashMap, and that'll contain the specific value-update logic.

[toc] | [prev] | [next] | [standalone]

#18449

On 8/30/2012 12:24 PM, Andreas Leitgeb wrote:
> Daniel Pitts <newsgroup.nospam@virtualinfinity.net> wrote:
>> On 8/30/12 10:46 AM, markspace wrote:
>>> On 8/30/2012 10:39 AM, Andreas Leitgeb wrote:
>>>> What I'm missing, however, is:
>>>>     How would I get the Entry for a given key?
>>> What about: [...] I think that's what you said you are doing.
> You thought essentially right, markspace ;-)
>

OK...

>
> Let's say, I've got a method that takes an Map.Entry, and
> the new value, and it updates the Entry's value accordingly.
>
...
>
> Now, I'd rather call that method for specific keys, and
> that's how I'd arrive at the outset of this thread.


I think Lew has the correct analysis.  I was going more on gut instinct 
rather than analyzing carefully, but I don't see what is better, or more 
clear, or more desirable about your method, compared to the code I posted.

I think it would help if you actually posted your code.  I really can't 
fathom the use case for this, and English prose descriptions aren't 
helping.  I can barely understand what it is you are doing to implement 
this.  The "why" of it is completely beyond me.  Maybe some code will 
spark some kind of idea for improvement....

[toc] | [prev] | [next] | [standalone]

#18447

Andreas Leitgeb wrote:
> Given a (Hash)Map<Long,Long> map and two Long values k and v,
> Some task is to see if k is already in the map, and only if so,
> then update the value in the map based on previous value and v.
> 
> Of course, that is trivial, and I've already implemented
> it with containsKey(), get() and put().
> It's just, that it seems to me that my piece of code
> could be a bit *clearer*, if I could obtain the Map.Entry
> for "k", and (if that isn't null) do getValue() and
> setValue(...) on the Entry.

I dispute that that would be clearer. You'd be using part 
of the inner and should-be-hidden machinery of the Map 
to express what 'containsKey()' already directly and quite 
clearly expresses.

Also, modifying an 'Entry' might be synonymous with, but 
is not the same as "put the key and value in the Map", 
which 'Map#put(K key, V value)" is.

> What I'm missing, however, is:
>   How would I get the Entry for a given key?
> (apart from scanning all through the entrySet())

A quick scan of the Javadocs for 'Map.Entry' says, sorry, no.

> PS: using 1.6, but also interested in future (i.e. 1.7 or 

Java 7 is not the future. It's the present. It's up to 7u7 already.
As of November 2012, a few short months away, Java 6 will be 
the past.

>    even newer) prospects, and also in (any) explicit reasons
>    for *not* having some map.getEntry(K k).

Because 'Map' already has 'get(K k)'.

>    Also, such an Entry should be tied to the Map just like
>    those in the entrySet().  NavigableMap has methods that
>    return Entries with "snapshot"-semantics, which is *not*
>    what I'm looking for.

A quick scan of the Javadocs for 'Map.Entry' says, sorry, no.
"The only way to obtain a reference to a map entry is from the iterator 
of this collection-view. These Map.Entry objects are valid only for the 
duration of the iteration; more formally, the behavior of a map entry 
is undefined if the backing map has been modified after the entry was 
returned by the iterator, except through the setValue operation on the 
map entry."

"V setValue(V value) ...  (optional operation)."

-- 
Lew

[toc] | [prev] | [next] | [standalone]

#18451

Lew <lewbloch@gmail.com> wrote:
> Andreas Leitgeb wrote:
>> Given a (Hash)Map<Long,Long> map and two Long values k and v,
>> Some task is to see if k is already in the map, and only if so,
>> then update the value in the map based on previous value and v.
>> [...]
>> It's just, that it seems to me that my piece of code
>> could be a bit *clearer*, if I could obtain the Map.Entry
>> for "k", and (if that isn't null) do getValue() and
>> setValue(...) on the Entry.

> I dispute that that would be clearer. You'd be using part 
> of the inner and should-be-hidden machinery of the Map 
> to express what 'containsKey()' already directly and quite 
> clearly expresses.

I wouldn't have used any "inofficial" functionality. Any
(just theoretically) existing method of HashMap directly
returning a map-backed Entry, surely would have said in
the docs, under which circumstances null would be returned.

> Also, modifying an 'Entry' might be synonymous with, but 
> is not the same as "put the key and value in the Map", 
> which 'Map#put(K key, V value)" is.

As I *know* the key is in the map (see previous paragraph),
and also know, that there are no concurrency-issues (as the
map is an unshared local variable), the semantic difference
can be neglected, can't it?

>>   How would I get the Entry for a given key?
>> (apart from scanning all through the entrySet())
> A quick scan of the Javadocs for 'Map.Entry' says, sorry, no.

Well, I had already done a medium-speed-scan, myself, before
posting, but thanks for affirmation.

>> PS: using 1.6, but also interested in future (i.e. 1.7 or 
> Java 7 is not the future. It's the present.

True, but it's still in my project's (and likely not only
that one's) future :-)   Damn, parts of other projects here
still need Java 1.4 (or, exactly, source="1.4" target="1.4"
in build.xml), because Oracle 10.2's sqlj (or the like)
insists on it and explicitly refuses newer Java or classes
compiled for newer Java. 

> ... These Map.Entry objects are valid only for the 
> duration of the iteration; more formally, the behavior of a map entry 
> is undefined if the backing map has been modified after the entry was 
> returned by the iterator, except through the setValue operation on the 
> map entry."

The validity-limit of Map.Entries wouldn't have been a problem for me.
The only modifications on the map at that stage would have been value-
updates via obtained Map.Entries. And once a new Map.Entry would have
been obtained, the previous one would no longer have been used.
Anyway, it's moot, as there just isn't a map-backed Entry-returning
method in java.util.HashMap in the known parts of this universe.

> "V setValue(V value) ...  (optional operation)."
It is a supported operation for the entrySet()-members, so my
(unfulfilled) wish was of course for an Entry supporting that.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.java.programmer

csiph-web