# Hashfunction for unique character distributions

The original problem is given a large input file, with n input lines of random string, find the number of pairs-> meaning same number and type of characters, in the file. Constraint on type of characters is: any legal ascii(0-127) char besides 10 and 13. I am trying to implement a hashCode function for a wrapper class over a sized 128 int array that is ideally quick and results in minimal collisions.

Hence, my approach is to process each line into a int counting array of size 128 encoding the ascii set distributions into a wrapper class, then to store this array as a key in a hashtable/hashmap ( or possibly eventually to make my own hashtable implementation with linear probe to store it in). with value as the number of matching character distributions, from which I can calculate the number of pairs additively via Handshake Lemma to accumulate as I read through lines of text.

Hence to do this, I need some advice on selecting a appropriate fast hashing function that minimises collisions, and perhaps more importantly for my own understanding, the proof or a link to the proof. Initial number of total lines is given, so if there is a formula to calculate the required size, from that, it can be done. What I have done, arbitrarily using this as my hash function so far:

public int hashCode(){
int hash = 0;
for (int i = 0; i<128;i++){
hash+= b[i]*(i+1);
}
return (hash*this.size)%capacity;
}


Capacity meaning the size of the hashtable itself. In math terms n = Size of String, m = size of hashtable: $$\sum^{128}_{i=0}(x[i]*(i+1))*n \mod m$$

The requirements for this hash function are: given a constant sized 128 int array in which each value in the index is bounded maximally by length of the string how can I come up with a unique hash.

or alternatively: given a string of size x with unique character distributions, how can I calculate the hash value, such that another string with same character distribution has the same hash value.

Ideally it will be a fast compute hash function

Thanks!

• Don't you want your hash to be order-independent? This way ab and ba will hash to the same thing, which seems appropriate, unless I misunderstood "same number and type of characters". – Yuval Filmus Mar 28 '20 at 13:00
• Furthermore, since the number of equivalence classes of strings is much larger than 128, your hash function isn't going to be one-to-one, and so, if you want it to have good worst-case performance, you will have to make it randomized (depending on some parameters chosen randomly at the outset). – Yuval Filmus Mar 28 '20 at 13:12
• As a simple example, you can choose a random mapping $P\colon [128] \to [128]$ and sum (or XOR) the value of $P$ across the entire string. This would be order-independent, and might have some weak guarantees. Injecting enough randomness, you should be able to obtain a hash function with better guarantees. – Yuval Filmus Mar 28 '20 at 13:14
• @YuvalFilmus Yes I want it to be order independent, so if ABCD and CDBA are parsed, there is 1 pair, if BACD also, its 3 pairs and so on, so following handshake lemma Can you explain further on the random mapping, like Ive thought of mapping first 128 primes to the value? So I just randomly generate a number to assign to it? Also how would I choose the size of the hashtable to reduce rates of collision? – BlackOnyx Mar 29 '20 at 5:02
• If you want to have only few collisions, the size of the hash table should be comparable (larger by a constant factor) to the number of equivalence classes. – Yuval Filmus Mar 29 '20 at 6:35