Simple HashTable implementation using an array in Java?

Question

I'm having a problem with implementing a very simple HashTable using an array. The problem is that the first Item put in the HashTable is always AVAILABLE. Maybe you guys can see what is going wrong. This is the HashTable class:

public class HashTable {

    private Item[] data;
    private int capacity;
    private int size;
    private static final Item AVAILABLE = new Item("Available", null);

    public HashTable(int capacity) {

        this.capacity = capacity; 
        data = new Item[capacity];
        for(int i = 0; i < data.length; i++) {

            data[i] = AVAILABLE;
        }
        size = 0;
    }

    public int size() {

        return size;
    }

    public int hashThis(String key) {

        return key.hashCode() % capacity; 
    }

    public Object get(String key) {

        int hash = hashThis(key);

        while(data[hash] != AVAILABLE && data[hash].key() != key) {

            hash = (hash + 1) % capacity;
        }
        return data[hash].element();
    }

    public void put(String key, Object element) {

        if(key != null) {
            size++;
            int hash = hashThis(key);
            while(data[hash] != AVAILABLE && data[hash].key() != key) {

                hash = (hash + 1) % capacity;
            }

            data[hash] = new Item(key, element);

        }

    }

    public Object remove(String key) {
        // not important now.
        throw new UnsupportedOperationException("Can't remove");
    }

    public String toString() {

        String s = "<HashTable[";
        for(int i = 0; i < this.size(); i++) {

            s += data[i].toString();
            if(i < this.size() - 1) {

                s += ",";
            }
        }
        s += "]>";
        return s;
    }

}

For more clarity, this is the Item class:

public class Item {

    private String key;
    private Object element;

    public Item(String key, Object element) {

        this.setKey(key);
        this.setElement(element);
    }

    public String key() {
        return key;
    }

    public void setKey(String key) {
        this.key = key;
    }

    public Object element() {
        return element;
    }

    public void setElement(Object element) {
        this.element = element;
    }

    public String toString() {

        String s = "<Item(";
        s += this.key() + "," + this.element() + ")>";
        return s;
    }

}

To give an example:

HashTable ht = new HashTable(10);
ht.put("1", "a");

The output of toString() after putting has to be:

"<HashTable[<Item(1,a)>]>"

but I get:

"<HashTable[<Item(Available,null)>]>"

update: I should probably mention that the next Item gets put correctly and the one after that is not again.

GlenPeterson · Accepted Answer · 2013-10-06 21:56:31Z

2

I think the problem is in your toString method. You loop for 0 - size when size = 1 so once so you only print out the first value in your hashTable problem is the first value in your hash table is not a real value it's an AVAILABLE you have to do something like this

EDIT: Sorry I forgot to move the index over.

public String toString() {
   String s = "<HashTable[";
   int i = 0;
   int count = 0;
   while(count < this.size()) {

        //Skip the AVAILABLE cells
        if(data[i] == AVAILABLE) {
            i++;
            continue;
        }

        s += data[i].toString();
        if(count < this.size() - 1) {
            s += ",";
        }
        count++;
    }
    s += "]>";
    return s;
}

edited Oct 6, 2013 at 21:56

GlenPeterson

5,2965 gold badges47 silver badges55 bronze badges

answered Mar 31, 2012 at 18:00

twain249

5,6861 gold badge23 silver badges26 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

twain249 Over a year ago

@Loolooii the loop in the toString method? Every time you have a cell that is not AVAILABLE i gets incremented so it should stop when i=size. So if size is set correctly (which it appears to be) and there is an element in the array that doesn't equal AVAILABLE it should stop.

Loolooii Over a year ago

Yes the loop in the toString method. I know, it should stop, but somehow it does not?!

Loolooii Over a year ago

And the loop in put() also doesn't stop when I change && to || .

twain249 Over a year ago

@Loolooii I wasn't sure about the put method so I removed it. I'll edit the loop so it will stop in the toString method (but it should work as is)

Loolooii Over a year ago

Yes, I just tried debugging and: it goes in the first if and after continue it goes back to while-condition and keeps doing this. So data[i] is always AVAILABLE.

|

varshnes · Accepted Answer · 2014-04-17 21:54:30Z

1

Try this for toString() if still interested in the solution, I ran it and its fine:

public String toString()
{
    String s = "<HashTable[";
    for (int i = 0; i < this.capacity; i++)
    {
        if (data[i].Element != null)
        {
            s += data[i].toString();
            if (i < this.size - 1)
            {
                s += ",";
            }
         }
     }
     s += "]>";
     return s;
}

answered Apr 17, 2014 at 21:54

varshnes

211 silver badge4 bronze badges

Collectives™ on Stack Overflow

Simple HashTable implementation using an array in Java?

2 Answers 2

7 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

7 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related