Hash表中的递归插入(线性探测)

Question

我在练习实现哈希函数。我尝试使用线性探测在哈希表中插入。插入工作正常，但我对递归不满意。感觉不像是“好的递归”。Linear_Probing函数不是递归函数本身，而是使用另外两个函数(不包括哈希函数)进行递归插入：Index_Finder()及其辅助函数。

在这段代码中，有什么方法可以更好地将递归插入到哈希表中？

int Hash(int number); //<Hash function returns index by adding the first and last digit of a number;
bool Linear_Probing(int array[], bool flags [], int MAX_SIZE, int number, int &collisions); //<This function if possible inserts the number in the Hash Table 
int Index_Finder(int number, bool flags[], int MAX_SIZE, int &collisions); //<This function finds the index where the number should be inserted. It returns -1 if no empty slot is found.
int Index_Finder(bool flags[], int MAX_SIZE, int index, int limit, int &collisions); //<This is an auxilary function


int main()
{
    const int MAX_SIZE = 11;
    int collisions = 0;
    int array[MAX_SIZE];
    bool flags[MAX_SIZE];

    for (int i = 0; i < MAX_SIZE; i++)
    {
        array[i] = 0;
        flags[i] = false;

    }

    //<Inserting numbers in hash table using linear probing
    Linear_Probing(array, flags, MAX_SIZE, 67, collisions);
    Linear_Probing(array, flags, MAX_SIZE, 19, collisions);
    Linear_Probing(array, flags, MAX_SIZE, 3, collisions);
    Linear_Probing(array, flags, MAX_SIZE, 808, collisions);
    Linear_Probing(array, flags, MAX_SIZE, 337, collisions);
    Linear_Probing(array, flags, MAX_SIZE, 1, collisions);
    Linear_Probing(array, flags, MAX_SIZE, 86, collisions);
    Linear_Probing(array, flags, MAX_SIZE, 38, collisions);

    return 0;
}

bool Linear_Probing(int array[], bool flags[], int MAX_SIZE, int number, int &collisions)
{
    int dummy_collisions = 0;
    int index = Index_Finder(number, flags, MAX_SIZE, dummy_collisions);

    if (index == -1)
        return false;

    else
    {
        collisions += dummy_collisions;

        array[index] = number;
        flags[index] = true;
        return true;
    }
}

int Index_Finder(int number, bool flags[], int MAX_SIZE, int &collisions)
{
    int index = Hash(number);

    if (index < MAX_SIZE && !flags[index])
        return index;

    if (index >= MAX_SIZE)
    {
        index = 0;

        if (!flags[index])
            return index;

        else
            collisions++;
    }

    else
    {
        collisions++;
    }

    int limit = index;

    return Index_Finder(flags, MAX_SIZE, ++index, limit, collisions);

}

int Index_Finder(bool flags[], int MAX_SIZE, int index, int limit, int &collisions)
{
    if (limit == index)
        return -1;

    if (index == MAX_SIZE)
        index = 0;

    if (!flags[index])
        return index;

    else
    {
        collisions++;
        return Index_Finder(flags, MAX_SIZE, ++index, limit, collisions);
    }
}


int Hash(int number)
{
    int first_digit = 0, last_digit = 0;
    bool first_time = true;

    while (number > 0)
    {
        if (first_time)
        {
            first_digit = number % 10;
            number -= (number % 10);
            number /= 10;
            first_time = false;
        }

        else
        {
            last_digit = number % 10;
            number -= (number % 10);
            number /= 10;
        }
    }

    return (first_digit + last_digit);
}

Answer 1

• 当注释来描述函数的用途时，更常见的做法是将它们放在函数定义的签名上面。将它们放在类似的原型旁边，会使这些代码行更难阅读，并增加代码的水平长度。
• 用单行语句使用大括号是不一致的。在所有这样的语句中使用它们也更好，并且可以防止一些bug并简化维护。
• 与使用循环初始化数组不同，您可以使用std::fill_n()：std：：fill_n( MAX_SIZE，0)；std：：fill_n(标志、MAX_SIZE、false)；虽然它在较小的程序中可能不重要，但它仍然更简洁，更安全。
• 您正在将C-数组传递给函数，这不应该在C++中完成，因为这将导致它们衰变为指针。相反，传入容器类的对象，如std::vector (动态)或std::array (静态)。选择为你完成工作的最佳人选。

Answer 2

• 您肯定应该减少声明函数原型的行的长度。正如@Jamal所说，将注释放在每个函数签名前面的行中。
• 使用std::array或std::vector的另一个优点是可以丢弃同名的MAX_SIZE常量和函数参数，因为标准容器通过size()方法知道它们的长度。
• 说到MAX_SIZE，对于常量来说，所有大写大写都很好，但不应该在其他地方使用，因为这种表示法经常与常量和宏相关联，因此使用它作为函数参数名可能会引起混淆。
• 当您编写两个路径都返回的if/else对时，例如: if (索引== -1)返回false；否则，{== += dummy_collisions；数组索引= number；标志索引= true；返回true；}不要使其成为if/else链。只需返回第一个if并省略else语句。这将避免不必要的嵌套。
• return 0在main()末尾是可选的。如果省略它，编译器默认为return 0。
• 次要的一点，只是FYI，您对函数的命名约定有点不寻常。以Windows为中心的代码通常将PascalCase应用于函数名，而不需要在单词之间加上下划线。camelCase和snake_case也非常流行于方法命名。

Answer 3

1. 这似乎是一个非常糟糕的哈希算法。1001和10001将具有相同的值。要使用的更传统的哈希函数是一个简单的模数，尽管这取决于您的数据域，这可能并不一定是这样的(但是，除了在最人为的场景中，您提供的算法甚至不太可能是远程有用的)。
2. 正如其他人所说的，您应该将doxygen评论的格式完全不同；我会采用这样的风格：(顺便说一句，我对您的参数做了很多假设，顺便说一句，避免这一点是首先使用DO2的全部目的……) /*！在哈希表** @param数组中插入数字--哈希表值* @param标记占用率标志* @param MAX_SIZE * @param编号插入* @param输出冲突的数目*@返回插入是否成功的碰撞次数*/ bool Linear_Probing(int array[]、bool flags[]、int MAX_SIZE、int号、int号和冲突)；
3. 与每次调用时传递给事物的单独数组不同，这是一个使用对象封装事物的绝佳机会。关于部分示例: //！哈希表类HashTable { public: //！构造一个特定大小的哈希表HashTable(size_t大小)；//！尝试插入这个数字，跟踪碰撞次数bool插入(int号，size_t&冲突)；//！尝试插入此数字，放弃碰撞计数bool插入(int号){ size_t c；//丢弃返回插入( number，c)；} std::vector mValues；std::vector mOccupancy；}；然后在实现构造函数时，您将拥有:HashTable：：HashTable::HashTable(size_t size)：mValues(size)，mOccupancy(size) {}来分配数组。您还可以考虑将散列函数作为模板或构造函数参数，并将其默认为简单模数(例如)。
4. 没有理由递归地执行Index_Finder，甚至没有理由将其作为一个独立于insert的函数；它只是一个简单的迭代循环。考虑在插入函数中这样做: bool插入(int，size_t&冲突){ size_t start = n % mValues.size()；//或对散列函数的调用等等。size_t pos =开始；size_t= 0；do { if (!mOccupancy位置) { mValues位置 = n；mOccupancy位置 = true；返回true；} ++collisions；pos = (pos + 1) % mValues.size()；} while (pos != start)；返回false；}这实现了简单的线性探测，作为insert的一部分，而不需要任何疯狂的代码流。