|
| 1 | +package com.baeldung.folding; |
| 2 | + |
| 3 | +import java.util.stream.Collectors; |
| 4 | +import java.util.stream.IntStream; |
| 5 | + |
| 6 | +/** |
| 7 | + * Calculate a hash value for the strings using the folding technique. |
| 8 | + * |
| 9 | + * The implementation serves only to the illustration purposes and is far |
| 10 | + * from being the most efficient. |
| 11 | + * |
| 12 | + * @author A.Shcherbakov |
| 13 | + * |
| 14 | + */ |
| 15 | +public class FoldingHash { |
| 16 | + |
| 17 | + /** |
| 18 | + * Calculate the hash value of a given string. |
| 19 | + * |
| 20 | + * @param str Assume it is not null |
| 21 | + * @param groupSize the group size in the folding technique |
| 22 | + * @param maxValue defines a max value that the hash may acquire (exclusive) |
| 23 | + * @return integer value from 0 (inclusive) to maxValue (exclusive) |
| 24 | + */ |
| 25 | + public int hash(String str, int groupSize, int maxValue) { |
| 26 | + final int[] codes = this.toAsciiCodes(str); |
| 27 | + return IntStream.range(0, str.length()) |
| 28 | + .filter(i -> i % groupSize == 0) |
| 29 | + .mapToObj(i -> extract(codes, i, groupSize)) |
| 30 | + .map(block -> concatenate(block)) |
| 31 | + .reduce(0, (a, b) -> (a + b) % maxValue); |
| 32 | + } |
| 33 | + |
| 34 | + /** |
| 35 | + * Returns a new array of given length whose elements are take from |
| 36 | + * the original one starting from the offset. |
| 37 | + * |
| 38 | + * If the original array has not enough elements, the returning array will contain |
| 39 | + * element from the offset till the end of the original array. |
| 40 | + * |
| 41 | + * @param numbers original array. Assume it is not null. |
| 42 | + * @param offset index of the element to start from. Assume it is less than the size of the array |
| 43 | + * @param length max size of the resulting array |
| 44 | + * @return |
| 45 | + */ |
| 46 | + public int[] extract(int[] numbers, int offset, int length) { |
| 47 | + final int defect = numbers.length - (offset + length); |
| 48 | + final int s = defect < 0 ? length + defect : length; |
| 49 | + int[] result = new int[s]; |
| 50 | + for (int index = 0; index < s; index++) { |
| 51 | + result[index] = numbers[index + offset]; |
| 52 | + } |
| 53 | + return result; |
| 54 | + } |
| 55 | + |
| 56 | + /** |
| 57 | + * Concatenate the numbers into a single number as if they were strings. |
| 58 | + * Assume that the procedure does not suffer from the overflow. |
| 59 | + * @param numbers integers to concatenate |
| 60 | + * @return |
| 61 | + */ |
| 62 | + public int concatenate(int[] numbers) { |
| 63 | + final String merged = IntStream.of(numbers) |
| 64 | + .mapToObj(number -> "" + number) |
| 65 | + .collect(Collectors.joining()); |
| 66 | + return Integer.parseInt(merged, 10); |
| 67 | + } |
| 68 | + |
| 69 | + /** |
| 70 | + * Convert the string into its characters' ASCII codes. |
| 71 | + * @param str input string |
| 72 | + * @return |
| 73 | + */ |
| 74 | + private int[] toAsciiCodes(String str) { |
| 75 | + return str.chars() |
| 76 | + .toArray(); |
| 77 | + } |
| 78 | +} |
0 commit comments