java - 如何降低 "put"函数的时间复杂度

Question

我正试图找到一种方法来使我的算法执行得更快。这个函数目前正在做的是将值(字符)和键(字符串)插入到我的带有 7 个槽的哈希表中。它还在运行检查以查看 A. 是否有东西占据了它的最佳位置，然后将其放置在最佳可用位置。和 B. 如果插入 2 个相同的键，新键只是将它的值传输给旧键，而不是自己占用一个新槽。有没有办法在不迭代我的“键”数组的情况下做到这一点？

public void put(String key, Character val) {
                            int z = hash(key);
                            while(keys[z] != null){
                                if(key.equals(keys[z])){
                                    vals[z]= val;
                                    break;
                                }

                                z ++;
                                if (z>6){
                                    z=0;
                                    if(key.equals(keys[z])){  
                                        vals[z]= val;
                                        break;
                                    }
                                    if(keys[0]==null){
                                    break;
                                    }
                                    else{
                                        z++;
                                    }
                                }
                            }
                            keys[z] = key;
                            vals[z] = val;
                            N += 1;

                        } 

更新:这是我的 hash() 函数

public int hash(String key) {
                            int i;
                            int v = 0;

                            for (i = 0; i < key.length(); i++) {
                                v += key.charAt(i);
                            }
                            return v % M;
                        }

Answer 1

如果我理解你的代码是正确的，你有一个开放寻址哈希表和线性探测。

线性探测的替代方案(您正在搜索空白点的循环)是:

• https://en.m.wikipedia.org/wiki/Double_hashing
• https://en.m.wikipedia.org/wiki/Quadratic_probing

但无论如何，最坏情况下的时间将是线性的。对于只有 7 个元素的非常小的表，您以 1 为增量的线性方法看起来不错。