Unique Long for Map

Discussion in 'Java' started by caultonpos@gmail.com, Mar 11, 2008.

  1. Guest

    Hi,

    I have a common need to keep a small cache of values which are often
    identified by two or more long values.

    e.g. (1,2) ---- > "Abc"
    (1,9) -----> "Def"

    For performance I like using a hashtable but to use it I do this:

    public void addToCache(Long nbr1, Long nbr2, String value) {
    StringBuffer sb = new StringBuffer(32);
    sb.append(nbr1);
    sb.append(":");
    sb.append(nbr2);
    hashtable.put (sb.toString(), value);
    }

    or something similar to that. The point is to make the key unique I
    create a String. I would imagine lookups would be more efficient if
    the key was not a String but a number. But how to make a unique
    number from these two. Perhaps if I knew both numbers would be less
    than a billion then (nbr1 * 1,000,000,00 + nbr2) but that seems a
    little clunky.

    Is there a well defined method to create a single unique number based
    upon two values?

    thanks!

    Greg
     
    , Mar 11, 2008
    #1
    1. Advertising

  2. Eric Sosman Guest

    wrote:
    > Hi,
    >
    > I have a common need to keep a small cache of values which are often
    > identified by two or more long values.
    >
    > e.g. (1,2) ---- > "Abc"
    > (1,9) -----> "Def"
    >
    > For performance I like using a hashtable but to use it I do this:
    >
    > public void addToCache(Long nbr1, Long nbr2, String value) {
    > StringBuffer sb = new StringBuffer(32);
    > sb.append(nbr1);
    > sb.append(":");
    > sb.append(nbr2);
    > hashtable.put (sb.toString(), value);
    > }
    >
    > or something similar to that. The point is to make the key unique I
    > create a String. I would imagine lookups would be more efficient if
    > the key was not a String but a number. But how to make a unique
    > number from these two. Perhaps if I knew both numbers would be less
    > than a billion then (nbr1 * 1,000,000,00 + nbr2) but that seems a
    > little clunky.
    >
    > Is there a well defined method to create a single unique number based
    > upon two values?


    Yes: Concatenate them, as you have done above. You
    could also build a BigInteger or a BitSet or some other
    object; uniqueness is preserved if the bits of nbr1 do
    not interact with those of nbr2. Clearly, though, nothing
    you do can guarantee uniqueness when mapping 128 bits of
    input to a 32-bit hashCode() value.

    Absent other information about the joint distributions
    of nbr1 and nbr2, all I can suggest is that you build a
    LongPair class that implements equals() and hashCode().
    And if you're so avid for performance, you should probably
    be trafficking in longs rather than Longs. (But since you
    describe your cache as "small," one wonders whether this is
    the optimization you should be spending your time on ...)

    --
    Eric Sosman
    lid
     
    Eric Sosman, Mar 11, 2008
    #2
    1. Advertising

  3. Roedy Green Guest

    Roedy Green, Mar 11, 2008
    #3
  4. Mark Space Guest

    wrote:

    > Is there a well defined method to create a single unique number based
    > upon two values?


    I totally agree with Roedy and Eric here. I think this works, I didn't
    actually try it. And I should use generics.


    public class SomeClass{
    private HashMap hashTable = new HashMap();

    private static class HashEntry {
    long long1;
    long long2;

    public HashEntry(long long1, long long2) {
    this.long1 = long1;
    this.long2 = long2;
    }

    @Override
    public int hashCode() {
    return (int) ((long1 + 17) * 37 + long2 + 17);
    }

    @Override
    public boolean equals(Object obj) {
    if (obj == null) {
    return false;
    }
    if (getClass() != obj.getClass()) {
    return false;
    }
    final SomeClass.HashEntry other = (SomeClass.HashEntry) obj;
    if (this.long1 != other.long1) {
    return false;
    }
    if (this.long2 != other.long2) {
    return false;
    }
    return true;
    }
    }

    public void addToChache( long a, long b, String value ) {
    hashTable.put( new HashEntry(a, b), value );
    }
    }
     
    Mark Space, Mar 11, 2008
    #4
  5. "" <> writes:

    > I have a common need to keep a small cache of values which are often
    > identified by two or more long values.
    >
    > e.g. (1,2) ---- > "Abc"
    > (1,9) -----> "Def"
    >
    > For performance I like using a hashtable but to use it I do this:
    >
    > public void addToCache(Long nbr1, Long nbr2, String value) {
    > StringBuffer sb = new StringBuffer(32);
    > sb.append(nbr1);
    > sb.append(":");
    > sb.append(nbr2);
    > hashtable.put (sb.toString(), value);
    > }


    > or something similar to that. The point is to make the key unique I
    > create a String.


    That could be overkill. Also, comparing strings (of up to 41 chars) is
    slower than comparing two longs.

    > I would imagine lookups would be more efficient if
    > the key was not a String but a number. But how to make a unique
    > number from these two. Perhaps if I knew both numbers would be less
    > than a billion then (nbr1 * 1,000,000,00 + nbr2) but that seems a
    > little clunky.


    It is. It will break if the limit rises to 10 billion. Arbitrary limits
    are ... well, arbitrary.

    > Is there a well defined method to create a single unique number based
    > upon two values?


    Don't create a number, just create an object containing those longs:

    public class TableKey {
    public final long l1; // or make it private and add a getLongValue1();
    public final long l2;
    public TableKey(long l1, long l2) {
    this.l1 = l1;
    this.l2 = l2;
    }
    public boolean equals(Object o) {
    if (o == this) { return true; }
    if (!(o instanceof TableKey)) { return false; }
    TableKey other = (TableKey) o;
    return l1 == other.l1 && l2 == other.l2;
    }
    public int hashCode() {
    return (int) (l1 ^ (l1 >> 32)) * 31 + (l2 ^ (l2 >> 32)); // or something
    }
    }

    Not tested.

    Good luck
    /L
    --
    Lasse Reichstein Nielsen -
    DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
    'Faith without judgement merely degrades the spirit divine.'
     
    Lasse Reichstein Nielsen, Mar 11, 2008
    #5
  6. Roedy Green Guest

    On Mon, 10 Mar 2008 18:32:05 -0700 (PDT), ""
    <> wrote, quoted or indirectly quoted someone who
    said :

    >or something similar to that. The point is to make the key unique I
    >create a String. I would imagine lookups would be more efficient if
    >the key was not a String but a number. But how to make a unique
    >number from these two. Perhaps if I knew both numbers would be less
    >than a billion then (nbr1 * 1,000,000,00 + nbr2) but that seems a
    >little clunky.


    XOR is magic for mashing two numbers together while preserving the
    differentness.

    See http://mindprod.com/jgloss/xor.html

    I also showed you the use of relatively prime multipliers in
    http://mindprod.com/jgloss/hashcode.html

    These are all very quick to implement, so you can empirically test
    them to see which works best.

    --

    Roedy Green Canadian Mind Products
    The Java Glossary
    http://mindprod.com
     
    Roedy Green, Mar 11, 2008
    #6
  7. Lasse Reichstein Nielsen schreef:
    > "" <> writes:
    >
    >> I have a common need to keep a small cache of values which are often
    >> identified by two or more long values.
    >>
    >> e.g. (1,2) ---- > "Abc"
    >> (1,9) -----> "Def"
    >>
    >> For performance I like using a hashtable but to use it I do this:
    >>
    >> public void addToCache(Long nbr1, Long nbr2, String value) {
    >> StringBuffer sb = new StringBuffer(32);
    >> sb.append(nbr1);
    >> sb.append(":");
    >> sb.append(nbr2);
    >> hashtable.put (sb.toString(), value);
    >> }

    >
    >> or something similar to that. The point is to make the key unique I
    >> create a String.

    >
    > That could be overkill. Also, comparing strings (of up to 41 chars) is
    > slower than comparing two longs.
    >
    >> I would imagine lookups would be more efficient if
    >> the key was not a String but a number. But how to make a unique
    >> number from these two. Perhaps if I knew both numbers would be less
    >> than a billion then (nbr1 * 1,000,000,00 + nbr2) but that seems a
    >> little clunky.

    >
    > It is. It will break if the limit rises to 10 billion. Arbitrary limits
    > are ... well, arbitrary.
    >
    >> Is there a well defined method to create a single unique number based
    >> upon two values?

    >
    > Don't create a number, just create an object containing those longs:
    >
    > public class TableKey


    Jakarta Commons Collections has ‘MultiKey’ for this, but you could of
    course take Lasse’s suggestion.

    H.
    --
    Hendrik Maryns
    http://tcl.sfs.uni-tuebingen.de/~hendrik/
    ==================
    http://aouw.org
    Ask smart questions, get good answers:
    http://www.catb.org/~esr/faqs/smart-questions.html


    -----BEGIN PGP SIGNATURE-----
    Version: GnuPG v2.0.4-svn0 (GNU/Linux)
    Comment: Using GnuPG with SUSE - http://enigmail.mozdev.org

    iD8DBQFH1mbAe+7xMGD3itQRAibsAJ9HNamKByvCSmEqbiArb030ZrobQwCfW8Nx
    KiOyHkTUYd1gbVXtpwUDFOM=
    =yq1J
    -----END PGP SIGNATURE-----
     
    Hendrik Maryns, Mar 11, 2008
    #7
  8. Mark Space Guest

    Hendrik Maryns wrote:

    > Jakarta Commons Collections has ‘MultiKey’ for this, but you could of
    > course take Lasse’s suggestion.
    >
    > H.


    Good find, thanks for the tip. :)
     
    Mark Space, Mar 11, 2008
    #8
  9. Guest

    On Mar 10, 8:32 pm, "" <>
    wrote:
    > Hi,
    >
    > I have a common need to keep a small cache of values which are often
    > identified by two or more long values.
    >
    > e.g.  (1,2) ---- > "Abc"
    >         (1,9) -----> "Def"
    >
    > For performance I like using a hashtable but to use it I do this:
    >
    > public void addToCache(Long nbr1, Long nbr2, String value) {
    >    StringBuffer sb = new StringBuffer(32);
    >    sb.append(nbr1);
    >    sb.append(":");
    >    sb.append(nbr2);
    >    hashtable.put (sb.toString(), value);
    >
    > }
    >
    > or something similar to that.  The point is to make the key unique I
    > create a String.  I would imagine lookups would be more efficient if
    > the key was not a String but a number.   But how to make a unique
    > number from these two.  Perhaps if I knew both numbers would be less
    > than a billion then (nbr1 * 1,000,000,00 + nbr2)  but that seems a
    > little clunky.
    >
    > Is there a well defined method to create a single unique number based
    > upon two values?
    >
    > thanks!
    >
    > Greg


    Great, thanks for all the good replies !

    Greg
     
    , Mar 13, 2008
    #9
    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. George Marsaglia

    Assigning unsigned long to unsigned long long

    George Marsaglia, Jul 8, 2003, in forum: C Programming
    Replies:
    1
    Views:
    707
    Eric Sosman
    Jul 8, 2003
  2. Daniel Rudy

    unsigned long long int to long double

    Daniel Rudy, Sep 19, 2005, in forum: C Programming
    Replies:
    5
    Views:
    1,219
    Peter Shaggy Haywood
    Sep 20, 2005
  3. Mathieu Dutour

    long long and long

    Mathieu Dutour, Jul 17, 2007, in forum: C Programming
    Replies:
    4
    Views:
    496
    santosh
    Jul 24, 2007
  4. Bart C

    Use of Long and Long Long

    Bart C, Jan 9, 2008, in forum: C Programming
    Replies:
    27
    Views:
    829
    Peter Nilsson
    Jan 15, 2008
  5. veryhotsausage
    Replies:
    1
    Views:
    1,842
    veryhotsausage
    Jul 4, 2008
Loading...

Share This Page