TokenHashMap.java 2.8 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576
  1. package de.jplag;
  2. import java.math.BigInteger;
  3. import java.util.ArrayList;
  4. import java.util.Collections;
  5. import java.util.HashMap;
  6. import java.util.List;
  7. import java.util.Map;
  8. /**
  9. * A {@link HashMap} that maps Integer keys to multiple Integer values. Note that all keys with identical
  10. * <code>(key % prime)</code> are mapped to the same values. Specifically, <code>prime</code> is the next prime number
  11. * that is larger or equal to the specified size (see {@link TokenHashMap#TokenHashMap(int)}).
  12. */
  13. public class TokenHashMap {
  14. private final Map<Integer, List<Integer>> mappedEntries;
  15. private final int primeNumber;
  16. /**
  17. * Creates the {@link HashMap}.
  18. * @param size specifies the initial size and the key mapping (see {@link TokenHashMap}).
  19. */
  20. public TokenHashMap(int size) {
  21. mappedEntries = new HashMap<>(size);
  22. primeNumber = nextPrimeNumber(size);
  23. }
  24. /**
  25. * Returns all stored numbers for a key. Note that all keys with identical <code>(key % prime)</code> are mapped to the
  26. * same values (see {@link TokenHashMap}).
  27. * @param key is the specific key.
  28. * @return the stored numbers or an empty list if nothing is stored.
  29. */
  30. public final List<Integer> get(int key) {
  31. int actualKey = key % primeNumber;
  32. if (mappedEntries.containsKey(actualKey)) {
  33. return new ArrayList<>(mappedEntries.get(actualKey));
  34. }
  35. return Collections.emptyList();
  36. }
  37. /**
  38. * Stores a number for a key, does not replace the previous stored numbers for that key. Note that all keys with
  39. * identical <code>(key % prime)</code> are mapped to the same values (see {@link TokenHashMap}).
  40. * @param key is the specific key.
  41. * @param value is the number to store.
  42. */
  43. public final void put(int key, int value) {
  44. int actualKey = key % primeNumber;
  45. if (mappedEntries.containsKey(actualKey)) {
  46. mappedEntries.get(actualKey).add(value);
  47. } else {
  48. List<Integer> entries = new ArrayList<>();
  49. entries.add(value);
  50. mappedEntries.put(actualKey, entries);
  51. }
  52. }
  53. /**
  54. * Calculates the next prime number (including 1) that is larger or equal to a given number.
  55. * @param number is the give number.
  56. * @return the next prime number.
  57. */
  58. private int nextPrimeNumber(int number) {
  59. if (number <= 1) {
  60. return 1;
  61. }
  62. for (int possiblePrime = number; possiblePrime < 2 * number; possiblePrime++) { // Bertrand's postulate
  63. BigInteger bigInt = BigInteger.valueOf(possiblePrime);
  64. if (bigInt.isProbablePrime(100)) {
  65. return possiblePrime;
  66. }
  67. }
  68. throw new IllegalStateException("Should never be reached because of Bertrand's postulate!");
  69. }
  70. }