Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > Unique Long for Map

Reply
Thread Tools

Unique Long for Map

 
 
caultonpos@gmail.com
Guest
Posts: n/a
 
      03-11-2008
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

 
Reply With Quote
 
 
 
 
Eric Sosman
Guest
Posts: n/a
 
      03-11-2008
http://www.velocityreviews.com/forums/(E-Mail Removed) 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
(E-Mail Removed)lid
 
Reply With Quote
 
 
 
 
Roedy Green
Guest
Posts: n/a
 
      03-11-2008
On Mon, 10 Mar 2008 18:32:05 -0700 (PDT), "(E-Mail Removed)"
<(E-Mail Removed)> wrote, quoted or indirectly quoted someone who
said :

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

Roedy Green Canadian Mind Products
The Java Glossary
http://mindprod.com
 
Reply With Quote
 
Mark Space
Guest
Posts: n/a
 
      03-11-2008
(E-Mail Removed) 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 );
}
}
 
Reply With Quote
 
Lasse Reichstein Nielsen
Guest
Posts: n/a
 
      03-11-2008
"(E-Mail Removed)" <(E-Mail Removed)> 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 - (E-Mail Removed)
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'
 
Reply With Quote
 
Roedy Green
Guest
Posts: n/a
 
      03-11-2008
On Mon, 10 Mar 2008 18:32:05 -0700 (PDT), "(E-Mail Removed)"
<(E-Mail Removed)> 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
 
Reply With Quote
 
Hendrik Maryns
Guest
Posts: n/a
 
      03-11-2008
Lasse Reichstein Nielsen schreef:
> "(E-Mail Removed)" <(E-Mail Removed)> 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+7xMGD3itQRAibsAJ9HNamKByvCSmEqbiArb0 30ZrobQwCfW8Nx
KiOyHkTUYd1gbVXtpwUDFOM=
=yq1J
-----END PGP SIGNATURE-----

 
Reply With Quote
 
Mark Space
Guest
Posts: n/a
 
      03-11-2008
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.
 
Reply With Quote
 
caultonpos@gmail.com
Guest
Posts: n/a
 
      03-13-2008
On Mar 10, 8:32*pm, "(E-Mail Removed)" <(E-Mail Removed)>
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
 
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
Is there a unique method in python to unique a list? Token Type Python 9 09-09-2012 02:13 PM
list question... unique values in all possible unique spots ToshiBoy Python 6 08-12-2008 05:01 AM
Having compilation error: no match for call to (const __gnu_cxx::hash<long long int>) (const long long int&) veryhotsausage C++ 1 07-04-2008 05:41 PM
unsigned long long int to long double Daniel Rudy C Programming 5 09-20-2005 02:37 AM
Assigning unsigned long to unsigned long long George Marsaglia C Programming 1 07-08-2003 05:16 PM



Advertisments