In the following Main
method why isn't the last word (clapping
) removed?
public class Main {
public static void main(String[] args) {
HT ht = new HT();
ht.insert("airplane");
ht.insert("distilling");
ht.insert("speaks");
ht.insert("knit");
ht.insert("digitize");
ht.insert("Media");
ht.insert("canonicalized");
ht.insert("libraries");
ht.insert("clapping");
ht.insert("residues");
ht.insert("spoilers");
System.out.println(Arrays.toString(ht.set));
ht.remove("distilling");
ht.remove("knit");
ht.remove("canonicalized");
ht.remove("libraries");
ht.remove("clapping");
System.out.println(Arrays.toString(ht.set));
}
}
The output is
[Media, digitize, airplane, canonicalized, spoilers, distilling, clapping, knit, libraries, speaks, residues]
[Media, digitize, airplane, null, spoilers, null, clapping, null, null, speaks, residues]
clapping
is not removed. Why?
HT.java
public class HT {
public String[] set;
public int size;
public HT() {
this.set = new String[11];
this.size = 0;
}
public void insert(String word) {
int hash1 = giveHash1( word );
int hash2 = giveHash2( word );
while (set[hash1] != null) {
hash1 += hash2;
hash1 %= set.length;
}
set[hash1] = word;
size++;
}
public void remove(String word) {
int hash1 = giveHash1(word);
int hash2 = giveHash2(word);
while (set[hash1] != null && !set[hash1].equals(word)) {
hash1 += hash2;
hash1 %= set.length;
}
set[hash1] = null;
size--;
}
public int giveHashCode(String s) {
int hash = 0, x = 31;
for(int i=0;i<s.length();i++) {
hash = x * hash + s.charAt(i);
}
return hash;
}
private int giveHash1(String s) {
return (giveHashCode(s) % set.length < 0)
? (giveHashCode(s) % set.length) + set.length
: giveHashCode(s) % set.length;
}
private int giveHash2(String s) {
return 3 - (((giveHashCode(s) % set.length < 0)
? (giveHashCode(s) % set.length) + set.length
: giveHashCode(s) % set.length) % 3);
}
}
Apart from the modifiers, is there anything wrong with the code? Probably with the hash functions or maybe with insert()
or remove()
?
The problem is most likely the terminating condition for the loop in the remove()
method.
while (set[hash1] != null && !set[hash1].equals(word)) {
which terminates at the first null
value it finds.
When inserting, you're updating hash1
if the position is already occupied, so the final position of a word depends on the existing inserted words i.e. the occupied positions.
However when you've already removed a few of the values, the loop in remove()
may find empty positions (null
values) much sooner, and terminate before actually reaching the position the word
was originally inserted in.