HashCode Deduplication?

Question

Background:

Ever since I found out you can Use Custom Types in Map Keys and Sets, I wondered if you can map data by the hashCode value. I suspect it's a bad idea.

I understand the basics of how hash tables work, and I know collision is possible, but I am not sure how to measure the probability. I found this article which has a bunch of useful information and seems to confirm my hunch.

• Does Apex also have 2³² possible values?
  • (looks to me like the same max int)
• Can the hashCode values for the same object really change?
• Would the proposed sha1 alternative be computationally expensive in Apex?

Scenario:

I have a Location object (~2400 records) which I want to sync from an address field. Since this functionality involves creating child records, I want a way to quickly check if an address is already in the system. If it already exists, simply don't create the record. If they added a rule to duplicate management where you just drop records that already exist, I could just use that. So how viable is it to use hashCode for de-duplication purposes?

public class CompositeAddress
{
    final Id accountId;
    final String street, city, state, postal;
    public CompositeAddress
        (Id accountId, String street, String city, String state, String postal)
    {
        this.accountId = accountId;
        this.street = street;
        this.city = city;
        this.state = state;
        this.postal = postal;
    }
    public Integer hashCode()
    {
        return xor(street.hashCode(), xor(city.hashCode(),
                xor(state.hashCode(), postal.hashCode())
        ));
    }
    Integer xor(Integer a, Integer b) { return a ^ b; }
}

Alternatives:

• Just query all siblings and use CompositeAddress as a map key.
• Construct a hash using the sha1 algorithm.
• Concatenate values into a text key.

I think a collision probability of < 0.5% is tolerable, but I'm not sure if my data set fits within that bound. My bigger concern is, if the algorithm can actually hash the same object in different ways, I might create duplicate records by trusting the result.

Answer 1

• Does Apex also have 2³² possible values?
  • (looks to me like the same max int)

Yes.

• Can the hashCode values for the same object really change?

HashCode means different things in different contexts. Since I do play with them from time to time, I know that the implementations are pretty consistent, but not across data types. For example:

System.debug(System.hashCode(1));  // [Integer] 1
System.debug(System.hashCode(Decimal.valueOf(1))); // [Decimal] 31
System.debug(System.hashCode(Double.valueOf(1))); // [Double] 1072693248
System.debug(System.hashCode('A')); // [String] 65
System.debug(System.hashCode(new Account())); // [Account] 0
System.debug(System.hashCode(new Account(Name='A'))); // [Account(Name='A')] 2420458

While String.hashCode seems to be stable and consistent (note that 'A' is Unicode 65, which means the algorithm is based on some computation of the bits), it should not be relied on.

Would the proposed sha1 alternative be computationally expensive in Apex?

You can use Crypto.generateDigest to make your comparisons.

Integer hashCode = System.hashCode('hello world');

100,000 hashCode calls against 'hello world': 4.724 seconds

String sha1Code = EncodingUtil.base64Encode(
           Crypto.generateDigest('sha1', Blob.valueOf('hello world'));

100,000 generateDigest calls against 'hello world': 17.211 seconds

As you can see, in order to make a sha1 code that you can store in a text format (at minimum), you need about 4 times more CPU time for 100,000 records.

Note that since your proposed algorithm was calling hashCode four times, using sha1 would be marginally faster than using hashCode, assuming you simply concatenated the strings together:

String sha1Code = EncodingUtil.base64Encode(
    Crypto.generateDigest(
        'sha1',
        Blob.valueOf(street+'♥'+city+'♥'+state+'♥'+postal)));

Finally, all of this is still bit-dependent, so to really catch duplicates, you need to compare like case to like case:

String sha1Code = EncodingUtil.base64Encode(
    Crypto.generateDigest(
        'sha1',
        Blob.valueOf(
            (street+'♥'+city+'♥'+state+'♥'+postal).toLowerCase()
        )));

You can use a case-indexed field to make looking up duplicates easier. You'll still want to verify if they're duplicates by comparing each of the four fields, but you'll save about 99% of the work by building digest codes. Once you queried potential duplicates back into memory, you can then use hashCode/equals to verify those duplicates.

So, in conclusion... do not trust hashCode outside of the current transaction, make sure you take case sensitivity into account, and always double-check potential duplicate candidates to make sure they really are equal.

Edit: Also, you could use sha256, also supported, to get much longer values and reduce the chance of collision significantly.