java - 每次插入值时如何不计算哈希码

Question

出于学习目的，我已经实现了自己的 HashMap 。键有一个字符串，值有一个我创建的类的对象。顺便想知道我的hashcode方法是否合适，以及如何不在每次插入值时都计算hashcode。

我将计算一次的hash值保存为object的成员变量。但是在调用get方法时，只接收到key值，所以必须获取hashcode。如何回收计算过的哈希值？

• 最后，我的哈希生成方法是否合适？

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...
}

如果你能回答我，我将不胜感激。

Answer 1

因此，哈希码是要插入的内容的哈希码。

他们防止这太麻烦的方法是将行插入存储项目的哈希码，看起来像

整数哈希码(){ 如果(我有一个缓存的哈希码){ 返回缓存哈希码； } (计算哈希码) cached_hashcode = 哈希码； 返回哈希码；

这样，对于每个对象，您只需进行一次哈希码计算。

现在，请记住，计算机已经取得了很大进步。它们主要等待 RAM 子系统响应结果，并且可以为单个 ram 提取执行大约 1000 到 10000 次数学运算。这意味着以内存查找为代价“保留 CPU 周期”实际上会减慢您的程序。

明智地进行基准测试，如果这意味着减少 RAM 占用空间，请不要害怕使用少量 CPU。

对于那些好奇的人来说，如果您的程序足够小以适合第 1 层缓存，则延迟不是很大，但是当您将这些缓存溢出到其他层时，延迟会变得很明显。这就是为什么“缓存”并不总是一个很好的解决方案，因为如果缓存过多，您的程序就会变得更大，并且会更频繁地溢出缓存。

现代 CPU 试图进行补偿，主要是通过在请求之前预取所需的 RAM(在处理流中向前看)。在许多情况下，这会带来更好的运行时间，但也会产生新的问题(例如预加载您可能不会使用的内容，因为您选择了代码中的“其他”路径)。

最好的办法是不要过度缓存简单的东西，除非重建起来很昂贵。对于 JVM，方法调用(在非常低的级别)比您想象的要昂贵，因此 JVM 对字符串及其哈希码进行了特殊优化。