Question about HashMap and Map.Entry ...

Discussion in 'Java' started by Andreas Leitgeb, Aug 30, 2012.

  1. 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.
    Andreas Leitgeb, Aug 30, 2012
    #1
    1. Advertising

  2. Andreas Leitgeb

    markspace Guest

    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.)
    markspace, Aug 30, 2012
    #2
    1. Advertising

  3. Andreas Leitgeb

    Daniel Pitts Guest

    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.
    Daniel Pitts, Aug 30, 2012
    #3
  4. Daniel Pitts <> 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.
    Andreas Leitgeb, Aug 30, 2012
    #4
  5. Andreas Leitgeb <> 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.
    Andreas Leitgeb, Aug 30, 2012
    #5
  6. Andreas Leitgeb

    Daniel Pitts Guest

    On 8/30/12 12:32 PM, Andreas Leitgeb wrote:
    > Andreas Leitgeb <> 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.
    Daniel Pitts, Aug 30, 2012
    #6
  7. Andreas Leitgeb

    Lew Guest

    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
    Lew, Aug 30, 2012
    #7
  8. Andreas Leitgeb

    markspace Guest

    On 8/30/2012 12:24 PM, Andreas Leitgeb wrote:
    > Daniel Pitts <> 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....
    markspace, Aug 30, 2012
    #8
  9. Andreas Leitgeb

    markspace Guest

    On 8/30/2012 12:24 PM, Andreas Leitgeb wrote:
    > Daniel Pitts <> 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....
    markspace, Aug 30, 2012
    #9
  10. Daniel Pitts <> 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)
    Andreas Leitgeb, Aug 30, 2012
    #10
  11. Lew <> 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.
    Andreas Leitgeb, Aug 30, 2012
    #11
  12. 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.
    Andreas Leitgeb, Aug 30, 2012
    #12
  13. On 30.08.2012 23:55, Andreas Leitgeb wrote:
    > Daniel Pitts <> 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/
    Robert Klemme, Aug 31, 2012
    #13
  14. Robert Klemme <> wrote:
    > On 30.08.2012 23:55, Andreas Leitgeb wrote:
    >> Daniel Pitts <> 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.
    Andreas Leitgeb, Aug 31, 2012
    #14
  15. Andreas Leitgeb

    Daniel Pitts Guest

    On 8/31/12 3:26 AM, Andreas Leitgeb wrote:
    > Robert Klemme <> wrote:
    >> On 30.08.2012 23:55, Andreas Leitgeb wrote:
    >>> Daniel Pitts <> 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.
    Daniel Pitts, Aug 31, 2012
    #15
  16. 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
    Robert Klemme, Sep 1, 2012
    #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,412
    emilchacko
    Mar 2, 2010
  2. AtomicBob
    Replies:
    14
    Views:
    870
    Toby Inkster
    May 2, 2006
  3. Sharad
    Replies:
    3
    Views:
    398
    Sharad
    Sep 27, 2006
  4. www
    Replies:
    30
    Views:
    2,995
    Adam Maass
    Oct 23, 2007
  5. Rakesh
    Replies:
    10
    Views:
    12,167
    Mike Schilling
    Apr 8, 2008
Loading...

Share This Page