如何計算比較次數？ （哈希表）

Question

好的，所以我正在從「使用C++ 4th Ed的數據結構和其他對象」一書中工作。我正在製作一個散列表，它接受這些密鑰，並使用開放尋址將它們散列到正確的位置以解決衝突。下面的代碼是我目前擁有的。

頭文件

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


{ 
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 

和模板類

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); 
    // Tried adding Counter = Counter +1. 
    // Failed, reason in comments. 
} 

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); 
} 

我的問題，我希望我能得到一些幫助是，我如何會保持比較作出的多項軌道找到表中的每個值？

到目前爲止，我試着製作一個私有成員變量，並通過find_index循環增加它的每次迭代，但這並不起作用。我的總體目標是最終繪製比較的平均數量VS.表格密度。

Answer 1

您應該創建一個表，存儲每次調用find_index的比較量。價值將是關鍵，比較的數量將是價值。