1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
package org.eclipse.viatra.solver.data.map;
import org.eclipse.viatra.solver.data.map.internal.Node;
/**
* A class representing an equivalence relation for a type {@code K} with a
* continuous hash function.
*
* @author Oszkar Semerath
*
* @param <K> Target java type.
*/
public interface ContinousHashProvider<K> {
public static final int EFFECTIVE_BITS = Node.EFFECTIVE_BITS;
public static final int EFFECTIVE_BIT_MASK = (1 << (EFFECTIVE_BITS)) - 1;
/**
* Maximal practical depth for differentiating keys. If two keys have the same
* hash code until that depth, the algorithm can stop.
*/
public static final int MAX_PRACTICAL_DEPTH = 500;
/**
* Provides a hash code for a object {@code key} with a given {@code index}. It
* has the following contracts:
* <ul>
* <li>If {@link #equals}{@code (key1,key2)}, then
* {@code getHash(key1, index) == getHash(key2, index)} for all values of
* {@code index}.</li>
* <li>If {@code getHash(key1,index) == getHash(key2, index)} for all values of
* {@code index}, then {@link #equals}{@code (key1, key2)}</li>
* <li>In current implementation, we use only the least significant
* {@link #EFFECTIVE_BITS}
* </ul>
* Check {@link #equals} for further details.
*
* @param key The target data object.
* @param index The depth of the the hash code. Needs to be non-negative.
* @return A hash code.
*/
public int getHash(K key, int index);
public default int getEffectiveHash(K key, int index) {
return getHash(key, index) & EFFECTIVE_BIT_MASK;
}
public default int compare(K key1, K key2) {
if (key1.equals(key2)) {
return 0;
} else {
for (int i = 0; i < ContinousHashProvider.MAX_PRACTICAL_DEPTH; i++) {
int hash1 = getEffectiveHash(key1, i);
int hash2 = getEffectiveHash(key2, i);
for(int j = 0; j<Integer.SIZE/Node.BRANCHING_FACTOR_BITS; j++) {
final int factorMask = (1<<Node.BRANCHING_FACTOR_BITS)-1;
int hashFragment1 = (hash1>>>j*Node.BRANCHING_FACTOR_BITS) & factorMask;
int hashFragment2 = (hash2>>>j*Node.BRANCHING_FACTOR_BITS) & factorMask;
var result = Integer.compare(hashFragment1, hashFragment2);
if (result != 0) {
return result;
}
}
}
throw new IllegalArgumentException("Two different keys (" + key1 + " and " + key2
+ ") have the same hashcode over the practical depth limitation ("
+ ContinousHashProvider.MAX_PRACTICAL_DEPTH + ")!");
}
}
}
|
