Marko Marinkovic
Reputation: 126
Why does my hashtable not work at bigger range?
I'm working on an hashtable that uses open adressing with linear probing. I'm working with the standards functions such as get, insert and delete. My problem is that while these functions work very well for smaller hashtables, it seems to be going wrong when the hashtable gets bigger. The size() does not return the correct value and neither does get(). I would really appreciate any input on how I may be able to solve these problems.
public class SymbolTable {
private static final int INIT_CAPACITY = 7;
/* Number of key-value pairs in the symbol table */
private int N;
/* Size of linear probing table */
private int M;
/* The keys */
private String[] keys;
/* The values */
private Character[] vals;
/**
* Create an empty hash table - use 7 as default size
*/
public SymbolTable() {
this(INIT_CAPACITY);
}
/**
* Create linear probing hash table of given capacity
*/
public SymbolTable(int capacity) {
N = 0;
M = capacity;
keys = new String[M];
vals = new Character[M];
}
/**
* Return the number of key-value pairs in the symbol table
*/
public int size() {
return N;
}
/**
* Is the symbol table empty?
*/
public boolean isEmpty() {
return size() == 0;
}
/**
* Does a key-value pair with the given key exist in the symbol table?
*/
public boolean contains(String key) {
return get(key) != null;
}
/**
* Hash function for keys - returns value between 0 and M-1
*/
public int hash(String key) {
int i;
int v = 0;
for (i = 0; i < key.length(); i++) {
v += key.charAt(i);
}
return v % M;
}
/**
* Insert the key-value pair into the symbol table
*/
public void put(String key, Character val) {
int z = hash(key);
if(keys[z] == null){ //Ökar endast om platsen redan är null. lösning för att omplaceringarna från delete inte ska öka värdet
N++;
// System.out.println("stlk "+N);
}
if(key.equals(keys[z])){
vals[z]= val;
}
else
if (keys[z]!=null){
if(z == M -1){
z = 0;
}
for (int i = z; i < M; i++){
if (keys[z]!=null){
if(i == M - 1){
if(keys[i] == null){
z=i;
N++;
// System.out.println("strlk " + N);
break;
}else{
i=0;
}
}}
if(key.equals(keys[i])){
vals[i]= val;
break;
}
if(keys[i] == null){
z = i;
N++;
// System.out.println("stlk "+N);
break;
}
}
}
keys[z]=key;
vals[z]=val;
}
// dummy code
/**
* Return the value associated with the given key, null if no such value
*/
public Character get(String key) {
int index = hash(key);
while (keys[index] != null && !keys[index].equals(key)) {
index++;
if (index == M) {
index = 0;
}
}
return vals[index];
} // dummy code
/**
* Delete the key (and associated value) from the symbol table
*/
public void delete(String key) {
if (keys[hash(key)] != null){ //Kollar så att strängen faktiskt finns, så att den inte deletar pga. HASHVÄRDET av strängen finns
if(key.equals(keys[hash(key)])){
keys[hash(key)] = null;
vals[hash(key)] = null;
N --;
for (int i = 0; i < M; i++){
if(keys[i] != null && hash(keys[i]) != i){
N--;
// System.out.println("strlk "+N);
put(keys[i], vals[i]);
keys[i] = null;
vals[i] = null;
}}
} else {
for (int i = 0; i < M; i++){
if(keys[i] != null && hash(keys[i]) != i){
N--;
// System.out.println("strlk "+N);
put(keys[i], vals[i]);
keys[i] = null;
vals[i] = null;
}
if(key.equals(keys[i])){
keys[hash(key)] = null;
N --;
}
}
}
}
}
// dummy code
/**
* Print the contents of the symbol table
*/
// dummy code
/**
* Print the contents of the symbol table
*/
public void dump() {
String str = "";
for (int i = 0; i < M; i++) {
str = str + i + ". " + vals[i];
if (keys[i] != null) {
str = str + " " + keys[i] + " (";
str = str + hash(keys[i]) + ")";
} else {
str = str + " -";
}
System.out.println(str);
str = "";
}
}
}
this is the test program is using to run it.
import java.io.*;
public class SymbolTableTest2 {
public static void main(final String[] args){
final SymbolTable st = new SymbolTable(733);
final int nums = 730;
final int gap = 37;
final char[] tests = new char[nums];
int i;
System.out.println("Checking... (no more output means success)");
// Associate i (as a string) with a random printable character
for (i = gap; i != 0; i = (i + gap) % nums) {
final char ch = (char) (32 + (int) (Math.random() * ((127 - 32) + 1)));
st.put(Integer.toString(i), ch);
tests[i] = ch;
}
// Check that size() is correct
if (st.size() != nums - 1) {
System.out.println("size was() " + st.size()
+ ", should have been " + (nums - 1));
}
// Delete some entries
for (i = 1; i < nums; i += 2) {
st.delete(Integer.toString(i));
}
// Check that size is correct
if (st.size() != ((nums / 2) - 1)) {
System.out.println("size was() " + st.size()
+ ", should have been " + ((nums / 2) - 1));
}
// Delete same entries again
for (i = 1; i < nums; i += 2) {
st.delete(Integer.toString(i));
}
// Check that size is correct
if (st.size() != ((nums / 2) - 1)) {
System.out.println("size was() " + st.size()
+ ", should have been " + ((nums / 2) - 1));
}
// Check that correct entries are still in table
for (i = 2; i < nums; i += 2) {
if (st.get(Integer.toString(i)) == null
|| st.get(Integer.toString(i)) != tests[i]) {
System.out.println("get(" + i + ") was "
+ st.get(Integer.toString(i))
+ ", should have been " + tests[i]);
}
}
// Check that deleted entries really were deleted
for (i = 1; i < nums; i += 2) {
if (st.get(Integer.toString(i)) != null) {
System.out.println("get(" + i + ") was "
+ st.get(Integer.toString(i))
+ ", should have been null");
}
}
}}
Upvotes: 0
Views: 109
Answers (1)
Thomas Kläger
Reputation: 21435
Your delete method is wrong.
The following code fragment shows the problem:
SymbolTable st = new SymbolTable(733);
st.put("12", 'A');
st.put("21", 'B');
st.put("13", 'C');
st.remove("13");
After running this code, st will contain the two keys "12" and "13" instead of "12" and "21".
One problem is the put method: if your the key is already in the hashtable, but not at the place identified by the keys hashcode, you execute (around line 27 within the put method)
if(key.equals(keys[i])){
vals[i]= val;
break;
}
followed by (at the end of the put method)
keys[z]=key;
vals[z]=val;
which overwrites some other random key.
The second problem is within the delete method. You try to remove and re-insert all elements.
However,
put(keys[i], vals[i]);
keys[i] = null;
vals[i] = null;
will erase the element, if it happens to be reinserted into the same place. This can easily happen if two elements have the same hashcode.
Upvotes: 2
Related Questions
- hash table does not count values correctly
- HashTable not outputting correct data
- Why can't I properly retrieve from my hashtable?
- Hashtable length limit java
- HashTable Java... Can you check my code
- Java Hash Table Issue
- Why doesn't my HashTable allow key collisions?
- Java Hashtable question
- Need help with hashTable
- Java Hashtable problem