Java custom HashMap - Clear method

Question

I have created my own custom HashMap for a special use-case, but I am missing the "clear" method.

I have only found one implementation of a clear method for HashMaps on the internet, but I simply cant wrap my head around it.

Can anyone help me? I have provided the custom HashMap and the one implementation i found on the internet.

My custom HashMap:

public class LongToOSMNodeMap {
private Node[] table;
int MASK;

public LongToOSMNodeMap(int capacity) {
    table = new Node[1 << capacity]; // there are 2^{capacity} table cells
    MASK = table.length - 1;
}

public void put(long id, double lon, double lat) {
    int position = Long.hashCode(id) & MASK;
    table[position] = new Node(id, lon, lat, table[position]);
}

public Node get(long id) {
    int position = Long.hashCode(id) & MASK;
    for (Node n = table[position]; n != null; n = n.next) {
        if (n.id == id) {
            return n;
        }
    }
    return null;
}

public void clear() {

}

class Node extends OSMNode {
    long id;
    Node next;

    public Node(long id, double lon, double lat, Node n) {
        super(lon, lat);
        this.id = id;
        this.next = n;
    }

}

Clear method implementation that i dont get, but want to implement on my own:

public void clear() {
     modCount++;
     Entry[] tab = table;
     for (int i = 0; i < tab.length; i++)
         tab[i] = null;
     size = 0;
 }

What don't you get about it? The more specific your question, the better your chance of getting a good answer. — yshavit, Apr 01 '18 at 09:05
The overall use. I dont understand how I can use it to clear my own hashmap. Futhermore, the modCount and local tab array. — Oliver Juhl, Apr 01 '18 at 09:10
The modCount is used to detect incorrect usages of the map (modifying the map while iterating on it). The local tab is just a tiny optimization: accessing a local variable repeatedly is (or at least used to be) faster than accessing an instance field. — JB Nizet, Apr 01 '18 at 09:26

score 1 · Answer 1 · answered Apr 01 '18 at 09:13

1

public void clear() {
    Arrays.fill(table, null);
    // Or: table = new Node[table.length];
}

public void put(long id, double lon, double lat) {
    int position = Long.hashCode(id) & MASK;
    for (Node n = table[position]; n != null; n = n.next) {
        if (n.id == id) {
            return;
        }
    }
    table[position] = new Node(id, lon, lat, table[position]);
}

answered Apr 01 '18 at 09:13

Joop Eggen

107,315
7
83
138

Nice! I just read somewhere, that it is best practice not to create a new array or refill it with nothing, so that it why, i was looking for a better solution. But thanks! – Oliver Juhl Apr 01 '18 at 09:18
A hash table lives from empty cells, so this is an exception. One could alternatively have a list of indices of filled table cells, but that seems over-engineered with maybe no or little profit. – Joop Eggen Apr 01 '18 at 09:26

score 0 · Answer 2 · answered Apr 01 '18 at 09:25

You should edit your question to include this quote - a comment does not make a question ;) - but I'll try to answer that based on java.util.HashMap:

The overall use. I dont understand how I can use it to clear my own hashmap. Futhermore, the modCount and local tab array

The modCount serve as a mean to detect concurrent modification, which is used when you try to iterate over the map. You can see a use case in the nextNode() method on HashMap:

final Node<K,V> nextNode() {
  ...
  if (modCount != expectedModCount)
    throw new ConcurrentModificationException();
  ...
}

The local tab array is for performance reasons; see this answer.

Setting values to null is only to help the gc knows that you are not referencing those anymore.

Java custom HashMap - Clear method

2 Answers2