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.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 theword
was originally inserted in.