Unique Long for Map

[caultonpos]

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

 

[Eric Sosman]

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 ...)

 

[Roedy Green]

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

not unique, but almost unique.

See http://mindprod.com/jgloss/hashcode.html
http://mindprod.com/jgloss/digest.html

 

[Mark Space]

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 );
}
}

 

[Lasse Reichstein Nielsen]

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

 

[Roedy Green]

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.

 

[Hendrik Maryns]

Lasse Reichstein Nielsen schreef:

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


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


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-----

 

[Mark Space]

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

H.

Good find, thanks for the tip.

 

[caultonpos]

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