package de.jplag; import java.math.BigInteger; import java.util.ArrayList; import java.util.Collections; import java.util.HashMap; import java.util.List; import java.util.Map; /** * A {@link HashMap} that maps Integer keys to multiple Integer values. Note that all keys with identical * (key % prime) are mapped to the same values. Specifically, prime is the next prime number * that is larger or equal to the specified size (see {@link TokenHashMap#TokenHashMap(int)}). */ public class TokenHashMap { private final Map> mappedEntries; private final int primeNumber; /** * Creates the {@link HashMap}. * @param size specifies the initial size and the key mapping (see {@link TokenHashMap}). */ public TokenHashMap(int size) { mappedEntries = new HashMap<>(size); primeNumber = nextPrimeNumber(size); } /** * Returns all stored numbers for a key. Note that all keys with identical (key % prime) are mapped to the * same values (see {@link TokenHashMap}). * @param key is the specific key. * @return the stored numbers or an empty list if nothing is stored. */ public final List get(int key) { int actualKey = key % primeNumber; if (mappedEntries.containsKey(actualKey)) { return new ArrayList<>(mappedEntries.get(actualKey)); } return Collections.emptyList(); } /** * Stores a number for a key, does not replace the previous stored numbers for that key. Note that all keys with * identical (key % prime) are mapped to the same values (see {@link TokenHashMap}). * @param key is the specific key. * @param value is the number to store. */ public final void put(int key, int value) { int actualKey = key % primeNumber; if (mappedEntries.containsKey(actualKey)) { mappedEntries.get(actualKey).add(value); } else { List entries = new ArrayList<>(); entries.add(value); mappedEntries.put(actualKey, entries); } } /** * Calculates the next prime number (including 1) that is larger or equal to a given number. * @param number is the give number. * @return the next prime number. */ private int nextPrimeNumber(int number) { if (number <= 1) { return 1; } for (int possiblePrime = number; possiblePrime < 2 * number; possiblePrime++) { // Bertrand's postulate BigInteger bigInt = BigInteger.valueOf(possiblePrime); if (bigInt.isProbablePrime(100)) { return possiblePrime; } } throw new IllegalStateException("Should never be reached because of Bertrand's postulate!"); } }