/
StringHash.java
96 lines (83 loc) · 2.75 KB
/
StringHash.java
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
package Tyurin.Evgeny.StringHash;
import java.util.HashMap;
/*
Class for calculate and store hashes of strings
by Evgeny Tyurin
*/
public class StringHash {
/* Hash range */
private int hashMax = 10000000;
/* Hash storage: idx in array = hash code */
private String[] hashMap = new String[hashMax];
/* Character codes */
private HashMap<Character, Integer> charMap = new HashMap<>();
/* Constructs StringHash object with alphabet */
public StringHash(String alphabet) {
for(int idx=0; idx < alphabet.length(); idx++)
charMap.put(alphabet.charAt(idx), idx + 1);
}
// Hash string into hash table
public int hash(String str) {
int hash = calcHash(str);
if (hash > 0)
getHashMap()[hash] = str;
return hash;
}
// Get hash of string
public int getHash(String str) {
int hash = calcHash(str);
if (getHashMap()[hash] != null)
return hash;
else
return 0;
}
// For printing hash map
public String toString() {
StringBuilder sb = new StringBuilder();
for (int arrayIdx = 0; arrayIdx < getHashMap().length; arrayIdx ++) {
if (getHashMap()[arrayIdx] != null)
sb.append(arrayIdx).append("=").append(getHashMap()[arrayIdx]).append(" ");
}
return sb.toString();
}
// Getter for hash map array
public String[] getHashMap() {
return hashMap;
}
// Calculates int hash of string,
// returns 0 if something goes wrong
private int calcHash(String str) {
// Horner's method
int hashVal = 0;
for (int j=0; j<str.length(); j++) {
// Char not in alphabet - return 0
if (!charMap.containsKey(str.charAt(j)))
return 0;
int letter = charMap.get(str.charAt(j));
hashVal = (hashVal * (charMap.size() + 1) + letter) % hashMax;
}
// Something going wrong
if (hashVal <= 0)
return 0;
// Linear probation
boolean cycled = false;
do {
// Out of hash range - try again from beginning
if (hashVal >= hashMax) {
// It's second cycle - time to go out
if (cycled)
return 0;
hashVal = 1;
cycled = true;
}
// Empty place in hash table - return it
if (getHashMap()[hashVal] == null)
return hashVal;
// Place is not empty, but equals hashing str - return it
if (getHashMap()[hashVal].equals(str))
return hashVal;
// Not suitable place in hash table - try next
hashVal++;
} while (true);
}
}