SSD5_Optional Exercise 4不会

这个拼写检查的程序原理上没有什么难度

却看不大懂这个hashset，求大神指点

hashset.h

// template hash set class

#ifndef  _HASHSET_H_
#define  _HASHSET_H_

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdexcept>

using namespace std;

// we do not compute prime numbers but use a table instead
static const int num_primes = 25;
static const unsigned long prime_list[] = {
            53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317,
            196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843,
            50331653, 100663319, 201326611, 402653189, 805306457
        };

template <typename key_type, typename hash_func, typename key_equal>
class HashSet {

protected:
    // hashtable entries
    class Entry {
    public:
        key_type key;
        bool used;

        Entry() : used(false) {}}
    ;

    int entries;      // number of entries
    int prime;        // index to size table

    vector<Entry> *ht;
    hash_func hf;        // hash function on key_type
    key_equal eq;        // equality predicate on key_type

    int table_size() const { return prime_list[prime];}
    float load_factor() const { return float(size()) / table_size();}
    int resize();

public:

    HashSet()
            : entries(0), prime(0),
    ht(new vector<Entry>(prime_list[0])) {}

    virtual ~HashSet() {
        delete ht;
    }

    virtual int size() const { return entries;}
    virtual bool search(const key_type& k);
    virtual void insert(const key_type& k);
    virtual void remove(const key_type& k);
};

#endif

hash.cpp

#include  "hashset.h"

using namespace std;

template <typename key_type, typename hash_func, typename key_equal>
bool HashSet<key_type, hash_func, key_equal>::search(const key_type& k) {

    int p = hf(k) % table_size();

    while ((*ht)[p].used) {
        if (eq((*ht)[p].key, k)) {       // equality predicate for key_type
            return true;
        }
        p++;
        if (p == table_size()) {
            p = 0;  // wrap around to beginning
        }
    }

    return false;
}

template <typename key_type, typename hash_func, typename key_equal>
void HashSet<key_type, hash_func, key_equal>::remove(const key_type& k) {

    int p = hf(k) % table_size();

    while ((*ht)[p].used) {
        if (eq((*ht)[p].key, k)) {
            (*ht)[p].used = false;
            entries--;
            break;
        }
        p++;
        if (p == table_size()) {
            p = 0;  // wrap around to beginning
        }
    }

}


template <typename key_type, typename hash_func, typename key_equal>
void HashSet<key_type, hash_func, key_equal>::insert(const key_type& k) {

    if (load_factor() > .7) {
        resize();
    }

    int pp = hf(k) % table_size();
    int p = pp;

    while (p < table_size() && (*ht)[p].used) {
        p++;
    }

    if (p == table_size()) {
        p = 0;
    }

    while ((*ht)[p].used) {
        p++;
    }

    (*ht)[p].key = k;
    (*ht)[p].used = true;
    entries++;

}

template <typename key_type, typename hash_func, typename key_equal>
int HashSet<key_type, hash_func, key_equal>::resize() {

    if (prime == num_primes - 1) {
        cerr << "maximal table size reached, aborting ... " << endl;
        exit(2);
    }

    int mm = prime_list[prime];
    prime++;
    int m = prime_list[prime];
    vector<Entry>* ptr = new vector<Entry>(m);

    for (int i = 0; i < mm; ++i) {

        if ((*ht)[i].used) {
            key_type kk = (*ht)[i].key;

            int p = hf(kk) % m;

            while (p < m && (*ptr)[p].used) {
                p++;
            }
            if (p == m) {
                p = 0;
            }
            while ((*ptr)[p].used) {
                p++;
            }

            (*ptr)[p].key = kk;
            (*ptr)[p].used = true;
        }
    }

    delete ht;
    ht = ptr;
    return m;
}

哎，这个问题不会，让人见笑了