0
$\begingroup$

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!

$\endgroup$
6
  • 1
    $\begingroup$ 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". $\endgroup$ – Yuval Filmus Mar 28 '20 at 13:00
  • 1
    $\begingroup$ 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). $\endgroup$ – Yuval Filmus Mar 28 '20 at 13:12
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Mar 28 '20 at 13:14
  • $\begingroup$ @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? $\endgroup$ – BlackOnyx Mar 29 '20 at 5:02
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Mar 29 '20 at 6:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.