>>6
You can parallel this pretty well too.
(-) calculate the hashcode, for every string in parallel
(-) test to see if there is at least one repeating hashcode, and if there is, abort and retry with a new hash function.
The second part is just scanning through large array, looking for repeated entries. One method could be to sort the array using a linear time algorithm like radix sort, and then scan from left to right, seeing if there are ever two identical numbers next to each other. You could also load the entire integer array into a hash set and see if there every any genuine collisions with two keys being completely identical. And I think I remember seeing a really crazy divide and conquer algorithm for this a long time ago, which could be done in parallel. I'll look for it...