用二次探测实现 [英] Implementing with quadratic probing

问题描述

我有这个代码，我想用二次探测方法重新实现它，我的算法是
i =（i + count）％CAPACITY; 。我不知道我应该怎么做，所以帮助会很好。我在想你会改变散列函数和next_index函数，我不太确定。这是我需要重新实现的代码。

  #ifndef TABLE1_H 
 #define TABLE1_H 
 #include 
 cstdlib> //提供size_t 
 
命名空间main_savitch_12A 
 {
模板< class RecordType> 
类表
 {
 public：
 //会员常量 - 如果编译失败，请参阅附录E. 
 static const std :: size_t CAPACITY = 811; 
 // CONSTRUCTOR 
 table（）; 
 //修改成员函数
 void insert（const RecordType& entry）; 
 void remove（int key）; 
 //常数成员函数
 bool is_present（int key）const; 
 void find（int key，bool& found，RecordType& result）const; 
 std :: size_t size（）const {return used; } 
 private：
 //会员常量 - 这些用于特殊记录的关键字段。 
 static const int NEVER_USED = -1; 
 static const int PREVIOUSLY_USED = -2; 
 //会员变量
 RecordType数据[CAPACITY]; 
 std :: size_t used; 
 // HELPER FUNCTIONS 
 std :: size_t hash（int key）const; 
 std :: size_t next_index（std :: size_t index）const; 
 void find_index（int key，bool& found，std :: size_t& index）const; 
 bool never_used（std :: size_t index）const; 
 bool is_vacant（std :: size_t index）const; 
}; 
} 
 #includetable1.template//包含实现。 
 #endif 
 //结尾标题
 
 
 
 
 #include< cassert> //提供断言
 #include< cstdlib> //提供size_t 
 
命名空间main_savitch_12A 
 {
模板< class RecordType> 
 const std :: size_t表< RecordType> :: CAPACITY; 
 
模板< class RecordType> 
 const int表< RecordType> :: NEVER_USED; 
 
模板< class RecordType> 
 const int表< RecordType> :: PREVIOUSLY_USED; 
 
模板< class RecordType> 
表< RecordType> :: table（）
 {
 std :: size_t i; 
 
 used = 0; 
 for（i = 0; i< CAPACITY; ++ i）
 data [i] .key = NEVER_USED; //表示一个从未使用过的地方。 
} 
 
模板< class RecordType> 
 void table< RecordType> :: insert（const RecordType& entry）
 //使用的库函数：cassert 
 {
 bool already_present; //如果entry.key已经在表
 std :: size_t index中，则为真; // data [index]是新条目的位置
 
 assert（entry.key> = 0）; 
 
 //设置索引以便data [index]是放置新条目的位置。 
 find_index（entry.key，already_present，index）; 
 
 //如果钥匙不在那里，则找到新条目的位置。 
 if（！already_present）
 {
 assert（size（）< CAPACITY）; 
 index = hash（entry.key）; 
 while（！is_vacant（index））
 index = next_index（index）; 
 ++已使用; 
} 
 
 data [index] = entry; 
} 
 
模板< class RecordType> 
 void table< RecordType> :: remove（int key）
 //使用的库函数：cassert 
 {
 bool found; //如果密钥出现在表中某处，则为真
 std :: size_t index; // spot where data [index] .key == key 
 
 assert（key> = 0）; 
 
 find_index（key，found，index）; 
 if（found）
 {//找到密钥，因此删除此记录并减少1使用。
 data [index] .key = PREVIOUSLY_USED; //表示不再使用的地点。 
 --used; 
} 
} 
 
模板< class RecordType> 
 bool table< RecordType> :: is_present（int key）const 
 //使用的库函数：assert.h 
 {
 bool found; 
 std :: size_t index; 
 
 assert（key> = 0）; 
 
 find_index（key，found，index）;找到
的回报; 
} 
 
模板< class RecordType> 
 void table< RecordType> :: find（int key，bool& found，RecordType& result）const 
 //使用的库函数：cassert.h 
 {
 std :: size_t index; 
 
 assert（key> = 0）; 
 
 find_index（key，found，index）; 
 if（found）
 result = data [index]; 
} 
 
模板< class RecordType> 
 inline std :: size_t表< RecordType> :: hash（int key）const 
 {
 return（key％CAPACITY）; 
} 
 
模板< class RecordType> 
 inline std :: size_t table< RecordType> :: next_index（std :: size_t index）const 
 //使用的库函数：cstdlib 
 {
 return（（index + 1 ）％CAPACITY）; 
} 
 
模板< class RecordType> 
 void table< RecordType> :: find_index（int key，bool& found，std :: size_t& i）const 
 //使用的库函数：cstdlib 
 {
 std： ：size_t count; //已检查的条目数
 
 count = 0; 
 i = hash（key）; （（count< CAPACITY）&&（data [i] .key！= NEVER_USED）&&（data [i] .key！= key）
）
 {
 ++ count; 
 i = next_index（i）; 
} 
 found =（data [i] .key == key）; 
} 
 
模板< class RecordType> 
 inline bool table< RecordType> :: never_used（std :: size_t index）const 
 {
 return（data [index] .key == NEVER_USED）; 
} 
 
模板< class RecordType> 
 inline bool table< RecordType> :: is_vacant（std :: size_t index）const 
 {
 return（data [index] .key == NEVER_USED）|| （data [index] .key == PREVIOUSLY_USED）; 
} 
} 
  

解决方案

你正在执行的这段代码是线性探测的

  index = hash（entry.key）; 
 while（！is_vacant（index））
 index = next_index（index）; 
 
模板< class RecordType> 
 inline std :: size_t table< RecordType> :: next_index（std :: size_t index）const 
 //使用的库函数：cstdlib 
 {
 return（（index + 1 ）％CAPACITY）; 
} 
  

假设您的地图已满并且哈希值为23，要测试的将是24,25,26,27等。

所有关于二次探测的不同之处在于插槽充满时测试插槽的模式。再次假设哈希返回23，那么下一个测试的时隙将是23 + 1 = 24，下一个将是23 + 4 = 27，下一个将是23 + 9 = 32，下一个将是23 + 16 = 39。看到模式？每次你测试23 + n * n。这是二次探测。当然，所有的值都应该是mod CAPACITY，就像你现在正在做的那样。换句话说，你不需要改变哈希函数，只需在插入while循环的时候。

I have this code and I am suppose to re implement it using a quadratic probing method, the algorithm I have is i = (i + count) % CAPACITY;. I'm not sure how I am supposed to do this, so help would be nice. I'm thinking you would just change the hash function and the next_index function, I'm not too sure. Here is the code I need to re-implement. Header file on top template on bottom.

#ifndef TABLE1_H
#define TABLE1_H
#include <cstdlib>    // Provides size_t

namespace main_savitch_12A
{
template <class RecordType>
class table
{
public:
    // MEMBER CONSTANT -- See Appendix E if this fails to compile.
    static const std::size_t CAPACITY = 811;
    // CONSTRUCTOR
    table( );
    // MODIFICATION MEMBER FUNCTIONS
    void insert(const RecordType& entry);
    void remove(int key);
    // CONSTANT MEMBER FUNCTIONS
    bool is_present(int key) const;
    void find(int key, bool& found, RecordType& result) const;
    std::size_t size( ) const { return used; }
private:
    // MEMBER CONSTANTS -- These are used in the key field of special records.
    static const int NEVER_USED = -1;
    static const int PREVIOUSLY_USED = -2;
    // MEMBER VARIABLES
    RecordType data[CAPACITY];
    std::size_t used;
    // HELPER FUNCTIONS
    std::size_t hash(int key) const;
    std::size_t next_index(std::size_t index) const;
    void find_index(int key, bool& found, std::size_t& index) const;
    bool never_used(std::size_t index) const;
    bool is_vacant(std::size_t index) const;
};
}
 #include "table1.template" // Include the implementation.
 #endif
 //End Of Header




#include <cassert>  // Provides assert
#include <cstdlib>  // Provides size_t

namespace main_savitch_12A
{
template <class RecordType>
const std::size_t table<RecordType>::CAPACITY; 

template <class RecordType>
const int table<RecordType>::NEVER_USED;

template <class RecordType>
const int table<RecordType>::PREVIOUSLY_USED;

template <class RecordType>
table<RecordType>::table( )
{
    std::size_t i;

    used = 0;
    for (i = 0; i < CAPACITY; ++i)
        data[i].key = NEVER_USED;  // Indicates a spot that's never been used.
}

template <class RecordType>
void table<RecordType>::insert(const RecordType& entry)
// Library facilities used: cassert
{
    bool already_present;   // True if entry.key is already in the table
    std::size_t index;        // data[index] is location for the new entry

    assert(entry.key >= 0);

    // Set index so that data[index] is the spot to place the new entry.
    find_index(entry.key, already_present, index);

    // If the key wasn't already there, then find the location for the new entry.
    if (!already_present)
    {
        assert(size( ) < CAPACITY);
        index = hash(entry.key);
        while (!is_vacant(index))
            index = next_index(index);
        ++used;
    }

    data[index] = entry;
}

template <class RecordType>
void table<RecordType>::remove(int key)
// Library facilities used: cassert
{
    bool found;        // True if key occurs somewhere in the table
    std::size_t index;   // Spot where data[index].key == key

    assert(key >= 0);

    find_index(key, found, index);
    if (found)
    {   // The key was found, so remove this record and reduce used by 1.
        data[index].key = PREVIOUSLY_USED; // Indicates a spot that's no longer in use.
        --used;
    }
}

template <class RecordType>
bool table<RecordType>::is_present(int key) const
// Library facilities used: assert.h
{
    bool found;
    std::size_t index;

    assert(key >= 0);

    find_index(key, found, index);
    return found;
}

template <class RecordType>
void table<RecordType>::find(int key, bool& found, RecordType& result) const
// Library facilities used: cassert.h
{
    std::size_t index;

    assert(key >= 0);

    find_index(key, found, index);
    if (found)
        result = data[index];
}

template <class RecordType>
inline std::size_t table<RecordType>::hash(int key) const
{
    return (key % CAPACITY);
}

template <class RecordType>
inline std::size_t table<RecordType>::next_index(std::size_t index) const
// Library facilities used: cstdlib
{
    return ((index+1) % CAPACITY);
}

template <class RecordType>
void table<RecordType>::find_index(int key, bool& found, std::size_t& i) const
// Library facilities used: cstdlib
{
std::size_t count; // Number of entries that have been examined

count = 0;
i = hash(key);
while((count < CAPACITY) && (data[i].key != NEVER_USED) && (data[i].key != key))
{
    ++count;
    i = next_index(i);
}
found = (data[i].key == key);
}

template <class RecordType>
inline bool table<RecordType>::never_used(std::size_t index) const
{
return (data[index].key == NEVER_USED);
}

template <class RecordType>
inline bool table<RecordType>::is_vacant(std::size_t index) const
{
return (data[index].key == NEVER_USED) || (data[index].key == PREVIOUSLY_USED);
}
}

解决方案

With this code you are doing linear probing

    index = hash(entry.key);
    while (!is_vacant(index))
        index = next_index(index);

template <class RecordType>
inline std::size_t table<RecordType>::next_index(std::size_t index) const
// Library facilities used: cstdlib
{
    return ((index+1) % CAPACITY);
}

Say your map is nearly full and hash returns 23, then the next slots you are going to test will be 24, 25, 26, 27, etc.

All that is different about quadratic probing is the pattern of slots to test when a slot is full. Again suppose hash returns 23, then the next slot to test will be 23 + 1 = 24, the next will be 23 + 4 = 27, the next will be 23 + 9 = 32, the next will be 23 + 16 = 39. See the pattern? Each time you are testing 23 + n*n. That is quadratic probing. Of course all values should be mod CAPACITY, like you are doing now.

In other words you don't need to change the hash function, just the while loop inside insert.

这篇关于用二次探测实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！