How to not calculate the hashcode each time value is inserted

0

I have implemented my own hashmap for study purposes. The key has a string and the value has an object of the class I created. By the way, I want to know if my hashcode method is appropriate, and how to not calculate the hashcode every time a value is inserted.

I saved the hash value once calculated as a member variable of object. However, when the get method is called, only the key value is received, so the hashcode must be obtained. How can I recycle the once calculated hash value?

  • Finally, is my hash generation method appropriate?
class IHashMap {

    private class Node {

        int hash;

        String key;
        int data;
        Node right;

        public Node(String key, int data) {

            this.key = key;
            this.data = data;
            this.right = null;
            this.hash = 0;
        }
    }
    private Node[] table;
    private int tbSize;
    private int n;

    public IHashMap(int tbSize) {

        this.table = new Node[tbSize];
        this.tbSize = tbSize;
        this.n = 0;
    }

    //...Omit irrelevant code...

    public void put(String key, int value) {

        int hash = hashCode(key);

        Node node = new Node(key, value);
        node.hash = hash;

        if(this.table[hash] != null) {

            Node entry = this.table[hash];

            while(entry.right != null && !entry.key.equals(key))
                entry = entry.right;

            if(entry.key.equals(key)) {

                entry.data++;
            }
            else {

                entry.right = node;
                this.n++;
            }
        }
        else {

            this.table[hash] = node;
            this.n++;
        }
    }

    public int get(String key) {

        int hash = hashCode(key);

        if(this.table[hash] != null) {

            if(this.table[hash].key.equals(key))
                return this.table[hash].data;

            Node entry = this.table[hash];

            while(entry != null && !entry.key.equals(key))
                entry = entry.right;

            if(entry == null)
                return -1;
            return entry.data;
        }
        return -1;
    }

    private int hash(String key) {

        int h = 0;
        if(key.length() > 0) {

            char[] var = strToCharArray(key);

            for(int i = 0; i < var.length; i++)
                h = 31 * h + var[i];
        }
        return h;
    }

    private int hashCode(String key) {

        return (hash(key) & 0x7fffffff) % this.tbSize;
    }

    //...Omit irrelevant code...
}

I would really appreciate it if you could answer me.

java
algorithm
hashmap
asked on Stack Overflow Aug 25, 2019 by Taylous

1 Answer

2

So, the hashcode is the hashcode of the thing that is being inserted.

They way to prevent this from being too much of a hassle is to slip in lines into the storage items's hashcode that looks like

int hashcode() { if (I have a cached hashcode) { return cached_hashcode; } (calculate hashcode) cached_hashcode = hashcode; return hashcode; }

this way, for each object, you only go through the hashcode computation once.

Now, keep in mind that computers have progressed a lot. They mostly wait on the RAM subsystem to respond to results, and can do about 1000 to 10000 math operations for a single ram fetch. This means that "preserving CPU cycles" at the cost of memory look ups can actually slow down your program.

Benchmark wisely, and don't be afraid to use a little CPU if it means reducing your RAM footprint.

For those who are curious, if your program is small enough to fit into layer 1 cache, it's not a big delay, but as you spill over these caches into the other layers the delays become noticeable. This is why "caching" is not always a great solution, as if you cache too heavily, your program becomes larger, and will spill out of cache more often.

Modern CPUs try to compensate, mostly by pre-fetching the needed RAM before it is requested (looking ahead in the processing stream). That leads to better runtime in many cases, but also creates new issues (like preloading stuff you might not use because you chose the "other" path through the code).

The best bet is to not overly-cache stuff that is simple, unless it's expensive to reconstruct. With the JVM a method call (at the very low levels) is more expensive than you might think, so the JVM has special optimizations for Strings and their hash codes.

answered on Stack Overflow Aug 25, 2019 by Edwin Buck

User contributions licensed under CC BY-SA 3.0