0

我现在正在学习的数据结构和算法课程是对算法如何工作的大量纸笔理解，但很少有实际编码。我是一个编程菜鸟，所以这对你们中的一些人来说可能是一个愚蠢的问题。

从概念上讲，我理解散列，以及不同方法的原因，但对如何编写这个分配感到迷茫。

基本上我们可以使用我们想要的任何源代码。书中的代码是http://users.cis.fiu.edu/~weiss/dsaajava3/code/SeparateChainingHashTable.java和http://users.cis.fiu.edu/~weiss/dsaajava3/code/QuadraticProbingHashTable。爪哇

使用这些代码中的任何一个时，我似乎都无法将键插入表中。我正在使用这个块插入：

Random randomGenerator = new Random();
int randomInt = randomGenerator.nextInt(99999);
for (int i = 0; i < 100; i++) {
    H.insert(""+randomInt);
}

这似乎实际上并没有向表中插入任何内容，但是，尽管插入量很大，但大小保持不变。另外，我不知道如何确定需要多少探针。

4

1 回答 1

1 
Random randomGenerator = new Random();

for (int i = 0; i < 100; i++) {
    int randomInt = randomGenerator.nextInt(99999);
    H.insert(""+randomInt);
}

试试这个，你有一条线在不好的地方。

我试探的情况：

/**
     * Method that performs quadratic probing resolution.
     * @param x the item to search for.
     * @return the position where the search terminates.
     */
    private int findPos( AnyType x )
    {
        int offset = 1;
        int currentPos = myhash( x );

        while( array[ currentPos ] != null &&
                !array[ currentPos ].element.equals( x ) )
        {
            currentPos += offset;  // Compute ith probe
            offset += 2;
            if( currentPos >= array.length )
                currentPos -= array.length;
        }

        return currentPos;
    }

如果我正确理解：此方法正在执行探测，是吗？因此，您必须计算在两个选项中调用此方法的次数：重复和不重复。如果当前添加的元素是重复的并且是两个整数，则使用一些标志。在此方法中，添加if检查标志并增加计数器之一。您将有多个探针。

编辑：

[LIN-np]：使用非素数表大小 1000 进行线性探测 [LIN-p]：使用素数表大小 1019 进行线性探测。请注意，1019 是 minPrime(1000)，即最小素数大于1000. [QDR-p]：使用素数表大小 1019 进行二次探测 [DBL-p]：使用素数表大小 1019 进行双重散列，对素数 97 进行冲突解决散列。

您必须使用使用探测的 HashTable 并测试探测量（平均）。你有二次探测算法public class QuadraticProbingHashTable<AnyType>。您必须将哈希表长度设置为 1019。在第一个练习中，您必须使用线性探测。所以基本上，当您开始添加元素时，您必须使用具有指定前提条件的 HashTable。

这是线性探测算法

这是双哈希算法

你必须在你的哈希表中实现它并检查它会被使用多少次。我认为它会以某种方式显示它产生了多少碰撞。快乐编码。二次算法完成，只需要设置前置条件）（硬编码起始值为 1019）。

于 2014-11-18T21:46:25.817 回答