如何提高数据结构的效率？

Question

我正在开发一种理论上比hashmap更有效的新数据结构。当发生碰撞时，它通过调整O(1)的大小来做到这一点。问题是，当插入数据(我最关心的度量)时，它比hashmap稍慢，而它应该要快得多。

以下是插入中使用的所有代码：

private void insert(Pair data, SwitchArray currTable){
    if (currTable.isExpanded == false && currTable.iValue==null) { //checks the very first iValue
        currTable.iValue = data;
        return;
    }
    else if (!currTable.isExpanded) {// if there is a new colision
        SwitchArray[] x = new SwitchArray[currTable.primeArray[currTable.depth]];
        currTable.sA = x;
        Integer index= Math.abs(data.key.hashCode()) % currTable.sA.length;
        currTable.sA[index] = new SwitchArray(data, currTable.depth+1);
        currTable.isExpanded = true;
        insert(currTable.iValue,currTable);
        currTable.iValue = null;
    }
    else{ // if expanded
        Integer index= Math.abs(data.key.hashCode()) % currTable.sA.length;
        if (currTable.sA[index] == null){
            currTable.sA[index] = new SwitchArray(data, currTable.depth+1); //this updates ivalue in the constructor
        } else {
            currTable = currTable.sA[index];
            insert(data,currTable);//go one level deeper

        }
    }
}

这是我参考的两个子类

class SwitchArray{
        int depth;
        int length;
        SwitchArray[] sA;
        Pair iValue;
        int[] primeArray = new int[]{7,11,13,17,19,23,29,31,37};
        boolean isExpanded = false;
        
        public SwitchArray(Pair iValue, int depth){
            this.iValue = iValue;
            this.depth = depth;
            length = primeArray[depth];
            if (iValue != null)
                iValue.myDepth = depth;
            
        }
        
    }

class Pair{
    String key;
    Integer value;
    int myDepth;
    
    public Pair(String key, Integer value){
        this.key=key;
        this.value=value;
        myDepth = -1;
    }
    
    public String toString(){
        return "( " + key + ", " + value + " | depth: " + myDepth + ")";
    }

}

这是完整的代码

我通过向hashmap和MDHT添加不同数量的数据(从1对一直到得到Java堆空间错误)来获得测试效率，并使用excel绘制这些数据。一致的MDHT稍慢一些。

(我还想补充一点，这只是我正在做的一个有趣的项目，而不是试图推翻hashmap或任何东西。)

所以，我问你的问题是，我该如何修复它，或者至少稍微改进一下？

Answer 1

新SwitchArray[currTable.primeArraycurrTable.depth]；

这相对较慢，因为它需要清除新的数组。您不能选择这一点，尽管hotspot倾向于识别任何值几乎立即得到完全填充的数组，并且省略了将零的初始写入堆中。这不适用于这里，也不是一个似乎可以在这里添加的优化。

insert

此方法是递归的，其递归次数与您的碰撞量有关，因此它不是O(1)。

所以，我问你的问题是，我该如何修复它，或者至少稍微改进一下？

HashMap不是某个随机的白痴写的。它可能不是完美的，但死记硬背的算法复杂性改进是不可用的。您可能可以在基本操作码计数方面建立一个理论上的改进，但这不太可能超过hashmap。原因是什么？热点。

热点引擎是一个巨大的模式匹配器。它发现它知道如何优化和优化它们的模式。虽然它做了各种各样的魔术来识别尽可能多的模式，但有一个简单的基本事实：它识别惯用的java。这个要优化的模式库不是建立在“我可以优化哪些操作码序列”的基础上的。它建立在一个比这简单得多的概念之上：“在java代码中常见的操作码序列是什么？”

换句话说，常用的模式得到了更好的优化。而HashMap是非常常用的。因此：

• 当发生冲突时，您可以进行O(1)插入，这当然是可能的，但是您不能通过基本定义保证O(1)查找。但是，作为一般规则，只要您没有在冲突中超载，这就不是控制性能的问题。在小型n中，O(n)算法和O(n^2)算法只是无关的。算法速度较慢的算法会击败速度更快的算法，关键是，在n‘足够大’之前，算法的复杂性是完全没有意义的。什么时候“足够大”？这取决于硬件、算法、数据和月球的相位--“大”点--“O”符号并不是用来预测何时达到“足够大”，仅仅是假设存在一些n，可能会令人难以置信地大，当算法复杂度“接管”并准确预测速度更快的算法时。重点是，使用hashmap，最有可能的是：

A这是一个学术案例，您可以使用冲突的哈希代码添加数千个对象。在这一点上，谁给出了什么东西的表现？解决方法是解决破碎的散列问题，而不是在试图发光的时候。在这种情况下，查找保证是O(n)，并且hashmap的主要点比这更快。只需在本例中使用ArrayList，您就无法超越它的性能。它有O(1)插入和O(n)查找。此外，如果您尝试，您的代码就会崩溃；您的桶最多只能有37个条目。一张包含37个物品的地图是，far，，在那个神奇的支点的左边，'n‘变得相关。

B没有一吨的碰撞。n根本不足以满足算法复杂性的需要。

还包括：

• 试图通过“编写更优化的代码”来改进事物注定会失败：“判断”( hotspot VM)有偏见，因为HashMap非常常见，所有热点实现都是为了识别和优化j.u.HashMap中的字节码而设计的。你也许能做一些理论上的改进，但它们会很小；太小，不足以超过这个有偏见的法官的惩罚。

结论:如果不向您打算在BetterHashMap中存储的数据添加重要的警告，就不可能提高HashMap的性能。换句话说，任何广义的hashmap在某些方面要比j.u.HM好得多，在另一些方面不会显着地差，这是一项非凡的工作，很可能是不可能的。