How to compute a unique 'signature' for a list of numbers?

Question

Given a list of numbers, for example some unique integer or long ID's what would be an optimum way to compute a reproducible 'signature' (preferably irregardless of element order)?

The use case is to detect whether any of the IDs have been added or removed from a list (of objects).

Java's array.hashCode() does not fit the bill, because even if it is apparently consistent between JVM invocations it returns a different hash if the order of elements changes or if another instance with the same elements is created:

int[] ids1 = {1, 2, 3};
System.out.println(ids1.hashCode());
// output: 980546781

int[] ids1Copy = {1, 2, 3};
System.out.println(ids1Copy.hashCode());
// output: 2061475679

int[] ids2 = {2, 1, 3};
System.out.println(ids2.hashCode());
// output: 140435067

My understanding is that ids1.hashCode() computes the hash for the memory address of the array and not a cumulative hash code for the primitive elements in the array.

What other approaches could be used in this case apart from hashing each element separately?

Answer 1

You can first create a hashmap of number vs its count in the array. Then you can just use the hashcode of the hashmap.

However, keep in mind that it might be possible (although rare) for 2 different hashmaps to return the same hashcode, as @khelwood suggested.

So if you want to reliably check if 2 lists of of numbers are same or not, you can create their frequency hashmaps as mentioned above, and then just do these checks:

• hashmap2.size() == hashmap1.size()
• for every (key, value) in hashmap2 { hashmap1[key] == value }

Its algorithmic time complexity is as efficient as computing and comparing hashcodes.

EDIT:

I just realized the above mentioned algorithm is what's used internally in Java HashMap equals().

So we can just create the frequency hashmaps and just check their equality using hashmap2.equals(hashmap1).

EDIT 2:

If all the numbers in an array are distinct, then you can create a hashset from them and then just check if set2.equals(set1).

Answer 2

The constraint

a reproducible 'signature' (preferably irregardless of element order)

makes this problem challenging.

Here are two approaches off the top of my head:

Approach 1:

a. Sort your list of integers in O(N lg N) time.

b. Treat your list of integers as the digits in a base-M integer, where M is the largest number in your list. Suppose you have a list of integers like [A, B, C]. Then you can hash that list to be: hash = A*M^0 + B*M^1 + C*M^2. This approach is reasonable if M is a small value. You can alternatively choose a small M as a power of 2 (e.g. 2^8) and then for any integer larger than that, break up the integer into chunks of 8 bits and use the same algorithm.

Total time: O(N lg N) + O(N). Space: O(1) long int accumulator.

Approach 2:

a. Sort your list of integers in O(N lg N) time.

b. Build a string representation of your list of integer and then hash the string. For example, for a list of integers like [1, 2, 3], create a string 1_2_3 and hash it.

Total time: O(N lg N) + O(N). Space: O(N lg N) sized string.

Answer 3

Note that all hash based solutions are unreliable. That is, there is a chance of a collision.

Assuming that that is OK, here is a simple approach.

First, build a hash function for pairs of integers. There are lots of those available.

Next, let's do a thought exercise.

Imagine arranging all of your integers into 2^64 buckets. Then look at the counts. So an array like [2, 0, 2] becomes a list of frequency counts like, ..., 0, 0 0, 1, 0, 2, 0, 0, 0, ....

Now pair those frequency counts up with their next neighbor. So we get ..., (0, 0), (1, 0), (2, 0), (0, 0), .... Now replace each pair with its hash. Repeat. After 64 levels, we'll get a single hash representing the whole frequency count.

Now we can't actually perform this operation. However at each level most of the entries start off 0, then hash(0, 0), then hash(hash(0,0), hash(0,0)) and so on. Which are all the same. So if the data structure is a linked list with the value and two pointers, most of the pointers will just point at the generic 0-filled block data structure.

So we can write out a "tree" with all of the pointers for 0-blocks pointing at the same canonical values. And when we have this tree, inserting an element is a question of navigating the path down to the appropriate root, creating a new node with the right value, and walking back up the tree inserting new values. This takes O(64) time to do. Insert all of the values, and we get a representation of the exact frequency count of the values, signed with a hash, in time O(64 n). (Creating the same amount of data, and then being able to throw most of it away.)

But it gets better. If you have two lists with this data structure created, not only can you tell whether they are likely different, but you can actually find the differences! (The rsync utility uses a similar trick to figure out just what changed between remote files so that it can restrict how much gets copied.)

Answer 4

Based on the comments and feedback the following approaches have been identified (possibly unreliable because of potential hash collisions as outlined by btilly):

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class NumberHash {

    public static void main(String[] args) {

        // ######## Arrays.deepHashCode() ########

        Integer[] ids1Sorted = {1, 2, 3};
        Integer[] ids1Unsorted = {3, 1, 2};
        
        System.out.println(Arrays.deepHashCode(ids1Sorted));
        // 30817

        Arrays.sort(ids1Unsorted);
        System.out.println(Arrays.deepHashCode(ids1Unsorted));
        // 30817


        // ######## toString() based ########

        int[] idsSorted = {1, 2, 3};
        System.out.println(Arrays.toString(idsSorted).hashCode());
        // -412129978

        int[] idsUnsorted = {3, 2, 1};
        Arrays.sort(idsUnsorted);
        System.out.println(Arrays.toString(idsUnsorted).hashCode());
        // -412129978

        List<Integer> oids = Arrays.asList(2, 3, 1);
        Collections.sort(oids);
        System.out.println(oids.toString().hashCode());
        // -412129978
    }
}

Answer 5

I would take a checksum like the CRC32 or Adler32 as unique identifier
wrapped in a lambda ready for use:

int[] yourArray = {1, 2, 3};
long checksum = Arrays.stream(yourArray).boxed().collect(Collector.of(
    CRC32::new, CRC32::update, (l, r) -> {return l;})).getValue();

{1, 2, 3}: 0x55bc801d
{1, 3, 2}: 0x3ba081ca
{2, 1, 3}: 0x7cd76d87