6
\$\begingroup\$

This is my implementation of a hash function described below. The (compiled) program can be run as follows:

$ java Hash1 < input.txt

The program reads a text file (of any size) with 8-digit student numbers on each line, splits each number into three numbers such that they have 3, 3 and 2 digits and then sums these numbers (e.g., for a student number 12345678, the hash is 123+456+78). Then, the hash is simply printed.

If the hash has already been used, the student number is reversed and the hash function is calculated from the reversed number (12345678 is reversed to 87654321 and the hash is 876+543+21). If this value has also been taken, it just prints "-1" and continues to the next value.

I use two external libraries for input and output:

edu.princeton.cs.algs4.stdin
edu.princeton.cs.algs4.stdout

The implementation:

public class Hash1 {

    // the main method reads student number and
    // gets the hash value. it outputs the hash 
    // if it hasn't been used, reverse hash
    // or -1 if both hash values are taken
    public static void main(String[] args) {

        // the size is 2098 because the highest 
        // hash (index) can be 999+999+99=2097
        String[] indexarray = new String[2098];

        while (!StdIn.isEmpty())
        {
            String key = StdIn.readLine();          
            char[] charray =  key.toCharArray();
            int hash = hash(charray);

            if (indexarray[hash] != null) {
                int newhash = reverse_hash(charray);
                if (indexarray[newhash] != null) {
                    int errorFlag = -1;
                    StdOut.println(errorFlag); 
                    }
                else {
                    indexarray[newhash] = key;
                    StdOut.println(newhash);
                    }
            }
            else {
                indexarray[hash] = key; 
                StdOut.println(hash);
            }   
        }       
    }

    // this method performs the hash as specified
    // and returns the value of the hash
    private static int hash(char[] charray) {
        String[] numbers = {"", "", ""};

        for (int i = 0; i < charray.length; i++)
            if (i < 3) 
                numbers[0] = numbers[0] + charray[i];
            else if (i >= 3 && i < 6) 
                numbers[1] = numbers[1] + charray[i];
            else if (i >= 6 && i < 8) 
                numbers[2] = numbers[2] + charray[i];

        int firstNumb = Integer.parseInt(numbers[0]);
        int secondNumb = Integer.parseInt(numbers[1]);
        int thirdNumb = Integer.parseInt(numbers[2]);
        int result = firstNumb + secondNumb + thirdNumb;

        return result;
    }

    // this method reverses the student number,
    // calls hash() method to hash the reversed
    // student number and returns the hash
    private static int reverse_hash(char[] charray) {
        char [] reverse = new char[charray.length];
        for (int i = 0; i < reverse.length; i++) {
            int index = reverse.length - i -1;
            reverse[i] = charray[index];
        }   
        int hash = hash(reverse);       
        return hash;
    }
    }

I am new to Java and would like to know how could I improve or optimize this program, if there are any issues with the code or I am using any bad (discouraged) practises etc.

\$\endgroup\$
4
\$\begingroup\$

If this is a class assignment, you might ask your professor why you spend time reading test data from keyboard instead of writing unit tests. Or if you really have to, at least use a Scanner to learn how the standard libraries work. That's what everyone else does in their classes. Nobody reads input from keyboard outside of the classroom in the extent the classroom examples would imply.

Operating on the input character-by-character makes the code a bit hard to read. Instead split the string using regexps: https://stackoverflow.com/questions/3760152/split-string-to-equal-length-substrings-in-java

Java also comes with a built in reverse function in the StringBuilder class.

You have made reversing the hash a responsibility of the caller (e.g. you do it in the main method). The assignment says it should be part of the hash function, so your implementation is incomplete. Also, the hash function is private so it can not be used unless the data is read from System in. Make the hash function a separate class and the input handling another.

Underscores don't belong in Java method naming convention. Use reverseHash instead of reverse_hash.

Make all fields and arguments final, unless you mean to change their value.

Don't worry about optimization until you have enough data to know for sure what part of your code is a bottleneck.

Some people say RuntimeExceptions shouldn't be declared in the method signature. I say that is a stupid ass opinion, since NumberFormatException is used as a return value for malformed input here. So, in my opinion, you should declare throws NumberFormatException that so that whoever uses your code can prepare for it. Or if you don't want to declare it, catch it and handle errors in other manner.

\$\endgroup\$
  • 1
    \$\begingroup\$ The structure of the code exactly follows the instructions, therefore handling the collisions outside of the basic hash function makes sense to me. It also makes sense to make the hash method private since it is not intended to be used by outsiders. (They might forget to handle the collisions.) It would make sense to remember the already taken hashes in a separate class, and that might be the topic for the class 3 weeks later. \$\endgroup\$ – Roland Illig Mar 18 at 7:29
  • \$\begingroup\$ Thank you, that's a great review! One question though. When you say "reading test data from keyboard", what do you mean? In my head, that means actually typing the student numbers in the terminal. This program takes a text file as input. I believe (I might be wrong) that's how you often do it in the "real world", too. \$\endgroup\$ – Jan Pisl Mar 18 at 22:10
  • \$\begingroup\$ Reading from StdIn implies the data comes from keyboard (or piped from another command). The StdIn wrapper gives me the vibe that your professor is a C/UNIX programmer who tries to work against Java idiomacies. I had one of those in 1997. :) Anyway, Java is not very handy for making tools to be invoked from command line. You'd always need a shell script to hide the JVM, then portability is lost and the whole thing becomes a bit of a mess (IMO). Looking back... learning to write unit tests at school would have been quite beneficial. \$\endgroup\$ – TorbenPutkonen Mar 21 at 6:30
6
\$\begingroup\$

The very idea of "if that hash is already taken, use another one" leads to bugs that are really hard to find later.

It's because your hash function (oh, it is called a function, hopefully in the mathematical sense) no longer has the signature hash(studentNumber) but instead becomes hash(studentNumber, allPreviousStudentNumbers). This means you get different hashes based on how the students are sorted.

A hash function may by definition produce collisions, and that is fine. Choosing an appropriate hash function that minimizes these collisions is often crucial. In cryptography the commonly used hashes have 256 bits, which makes a collision very unlikely. I hope your teacher plans to discuss these topics in class, as these are important.

Regarding your implementation of the basic hash function. It looks a little more complicated than necessary. An experienced Java programmer will know that there is a predefined String constructor that forms a String from part of a character array. It is new String(charray, start, count). Using this, the code becomes simple:

private static int hash(char[] studentNo) {
    int first = Integer.parseInt(new String(studentNo, 0, 3));
    int second = Integer.parseInt(new String(studentNo, 3, 3));
    int third = Integer.parseInt(new String(studentNo, 6, 2));
    return first + second + third;
}

This code is almost as simple as you would describe the algorithm to a human, and that's how it should be.

One tricky thing that bites me every time I use the String class: in general there are two ways of referring to a substring, a subarray or a subsequence: either (start, end) or (start, count). Unfortunately Java uses both of them. In the String constructor I used above, it's (start, count), while in the substring method it's (start, end). Even after 20 years of programming in Java, I still have to look at the documentation to know when each of these applies.

\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.