How to speed up code with Multithreading?

Question

I have created a password cracker in Java that cracks passwords from a text file list. It then generates a dictionary that contains the following pairs: the word hashed and the original word. I am looking for a way to speed up the program as having it read all of the words from the file and then use multithreading to generate the hashes. How can I break up the list of words so that it is in four separate partitions that I can then have multiple threads operate on in the createDictionary method? Here is what I have so far:

public class Main {
    private static final String FNAME = "words.txt";
    private final static String PASSWDFNAME = "passwd.txt";
    private static Map<String, String> dictionary = new HashMap<>();

    public static void main(String[] args) {
        // Create dictionary of plain / hashed passwords from list of words
        System.out.println("Generating dictionary ...");
        long start = System.currentTimeMillis();
        createDictionary(FNAME);
        System.out.println("Generated " + dictionary.size() + " hashed passwords in dictionary");
        long stop = System.currentTimeMillis();
        System.out.println("Elapsed time: " + (stop - start) + " milliseconds");
        
        // Read password file, hash plaintext passwords and lookup in dictionary
        System.out.println("\nCracking password file ...");
        start = System.currentTimeMillis();
        crackPasswords(PASSWDFNAME);
        stop = System.currentTimeMillis();
        System.out.println("Elapsed time: " + (stop - start) + " milliseconds");
    }
    
    private static void createDictionary(String fname) {
        // Read in list of words
        List<String> words = new ArrayList<>();
        try (Scanner input = new Scanner(new File(fname));) {
            while (input.hasNext()) {
                String s = input.nextLine();
                if (s != null && s.length() >= 4) {
                    words.add(s);
                }
            }
        } catch (FileNotFoundException e) {
            System.out.println("File " + FNAME + " not found");
            e.printStackTrace();
            System.exit(-1);
        }
        
        // Generate dictionary from word list
        for (String word : words) {
            generateHashes(word);
        }
    }
    
    private static void crackPasswords(String fname) {
        File pfile = new File(fname);
        try (Scanner input = new Scanner(pfile);) {
            while (input.hasNext()) {
                String s = input.nextLine();
                String[] t = s.split(",");
                String userid = t[0];
                String hashedPassword = t[1];
                String password = dictionary.get(hashedPassword);
                if (password != null) {
                    System.out.println("CRACKED - user: "+userid+" has password: "+password);
                }
            }
        } catch (FileNotFoundException ex) {
            System.out.println(ex.getMessage());
            ex.printStackTrace();
            System.exit(-1);
        }
    }

    private static void generateHashes(String word) {
        // Convert word to lower case, generate hash, store dictionary entry
        String s = word.toLowerCase();
        String hashedStr = HashUtils.hashPassword(s);
        dictionary.put(hashedStr, s);
        // Capitalize word, generate hash, store dictionary entry
        s = s.substring(0, 1).toUpperCase() + s.substring(1);
        hashedStr = HashUtils.hashPassword(s);
        dictionary.put(hashedStr, s);
    }
}

Answer 1

It's very simple, check this out:

public static void main(String[] args) {
    List<String> words = new ArrayList<>();
    List<Thread> threads = new ArrayList<>();

    int numThreads = 4;
    int threadsSlice = words.size() / numThreads;

    for(int i = 0; i < numThreads; i++) {
        Thread t = new Thread(new WorkerThread(i * threadsSlice, (i + 1) * threadsSlice, words));
        t.start();
        threads.add(t);
    }

    threads.forEach(t -> {
        try {
            t.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    });
}

static class WorkerThread implements Runnable {
    private final int left;
    private final int right;
    private final List<String> words;

    public WorkerThread(int left, int right, List<String> words) {
        this.left = left;
        this.right = right;
        this.words = words;
    }

    @Override
    public void run() {
        for (int i = left; i < right; i++) {
            generateHashes(words.get(i));
        }
    }
}

This code is creating 4 threads, each one scanning one partition of your list, and applying the generateHashes method on all the words in the partition.

You can put the words in the heap memory to avoid passing it to each thread via constructor param.

Also make sure to use a ConcurrentMap for your dictionary in the generateHashes method