Цель программы

Это попытка реализовать набор ADT, который может хранить строки без учета регистра (например, «Закат» == «закат»), используя хэш-таблицу в C .

Реализация

До сих пор у меня есть интерфейс набора ADT, его реализация и небольшой файл тестирования.

Чтобы реализовать set, я использовал алгоритм djb2 для хэширования строк и вставки их в корзину. Чтобы справиться с столкновением, я использовал метод раздельного сцепления с помощью std::list. Если коэффициент загрузки хэш-таблицы превышает максимальный порог, выполняется повторный хэш.

Интерфейс набора ADT set.h:

 #ifndef SET_H_
#define SET_H_

#include <ostream>
#include <list>
#include <cstdlib>

// Function to check string equality
bool equal(const std::stringamp; s1, const std::stringamp; s2);

// Hash function
size_t hash(const std::stringamp; s);


class set {

    std::list<std::string>* bucket_array; //buckets to store strings as a list

    size_t bucket_array_size;

    size_t set_size;

    const double max_load_factor = 3.0;

public:

    // Creates an empty set
    set() :
        bucket_array(new std::list<std::string>[4]), //hardcoded default constructor
        bucket_array_size(4),
        set_size(0)
    {

    }

    // Copy constructor
    set(const setamp; s);

    // Initializer list constructor
    set(std::initializer_list<std::string> ilist);

    // Copy assignment
    setamp; operator=(const setamp; s);

    // Returns true if val is not in the set and inserts it
    bool insert(std::string val);

    // Returns true if val is in the set
    bool contains(std::string val) const;

    // Removes val from the set and returns true if val is in the set
    bool remove(std::string val);

    // Remove everything from the set
    void clear();

    // Returns the total number of items in the set
    size_t size() const;

    // Returns whether or not the set is empty
    bool empty() const;

    // Returns the load factor of the hash table
    double loadfactor() const {
        return (double)set_size / (double)bucket_array_size;
    }

   // Print out the contents of the set -- showing the items
   // in each of the individual buckets
    void print(std::ostreamamp; out) const {
        for (size_t i = 0; i < bucket_array_size;   i) {
            std::list<std::string> bucket = bucket_array[i];

            out << "bucket[" << i << "] = {";

                bool first = true;

                for (std::string val : bucket) {
                    if (first) {
                        out << val;
                        first = false;
                    } else {
                        out << ", " << val;
                    }
                }

            out << "}" << std::endl;
        }
    }

    // Destructor
    ~set();
};

inline std::ostreamamp; operator<<(std::ostreamamp; out, const setamp; s) {
    s.print(out);
    return out;
}

#endif /* SET_H_ */
 

Реализация набора ADT set.cpp:

 #include "set.h"
#include <cctype>
#include <algorithm>

bool equal(const std::stringamp; s1, const std::stringamp; s2) {
    
    std::string lowercaseS1 = s1;
    std::string lowercaseS2 = s2;
    
    std::for_each(lowercaseS1.begin(), lowercaseS1.end(),
        [](char amp; c) {
            c = std::tolower(c);
        }
    );
    
    std::for_each(lowercaseS2.begin(), lowercaseS2.end(),
        [](char amp; c) {
            c = std::tolower(c);
        }
    );
    
    if(lowercaseS1 == lowercaseS2)
        return true;
    else
        return false;
    
}

size_t hash(const std::stringamp; s) {
    
    size_t hashcode = 5381;
    for (auto c : s) {
        hashcode = (hashcode << 5)   hashcode   std::tolower(c);
    }
    return hashcode;
    
}

set::set(const setamp; s):
    bucket_array(new std::list<std::string>[s.bucket_array_size]),
    bucket_array_size(s.bucket_array_size),
    set_size(s.set_size)
{

    for(size_t i=0; i<s.bucket_array_size; i  ) {
        bucket_array[i] = s.bucket_array[i];
    }
    
    
}

set::set(std::initializer_list<std::string> ilist):
    bucket_array(new std::list<std::string>[4]),
    bucket_array_size(4),
    set_size(0)
{    
    for(auto i: ilist) {
        insert(i);
    }
}

setamp; set::operator=(const setamp; s) {
    
    if(this != amp;s) {
        bucket_array_size = s.bucket_array_size;
        set_size = s.set_size;
        delete[] bucket_array;
        bucket_array = new std::list<std::string>[s.bucket_array_size];
        
        for(size_t i=0; i<s.bucket_array_size; i  ) {
            bucket_array[i] = s.bucket_array[i];
        }
        
    }
    
    return *this;
}

bool set::insert(std::string val) {
    
    size_t index = hash(val) % bucket_array_size;
    
    if(!contains(val)) {
        
        if(loadfactor() > max_load_factor) { //rehash and rezise
            
            size_t new_bucket_array_size = bucket_array_size * 2;
            std::list<std::string>* new_bucket = new std::list<std::string>[new_bucket_array_size];
            set_size = 0;
            
            std::list<std::string>::iterator it;
            
            for (size_t i = 0; i < bucket_array_size; i  ) {
                for(it = bucket_array[i].begin(); it != bucket_array[i].end(); it  ) {
                    size_t new_index = hash(*it) % new_bucket_array_size;
                    new_bucket[new_index].push_back(*it); //rehashing old values and inserting into new bucket
                    set_size  ;
                }
            }
            
            size_t val_new_index = hash(val) % new_bucket_array_size;
            new_bucket[val_new_index].push_back(val);
            set_size  ;
            
            delete [] bucket_array;
            bucket_array = new_bucket;
            
            bucket_array_size = new_bucket_array_size;
            
        } else {
            bucket_array[index].push_back(val);
            set_size  ;
        }
        
        return true;
    
    }
    
    return false;
    
}

bool set::contains(std::string val) const {
    
    size_t index = hash(val) % bucket_array_size;
    
    std::list<std::string>::iterator it;
    for(it = bucket_array[index].begin(); it != bucket_array[index].end(); it  ) {
        if(equal(*it, val)) {
            return true;
        }
    }
    
    return false;
    
}

bool set::remove(std::string val) {
    
    size_t index = hash(val) % bucket_array_size;
    
    std::list<std::string>::iterator it;
    for(it = bucket_array[index].begin(); it != bucket_array[index].end(); it  ) {
        if(equal(*it, val)) {
            bucket_array[index].erase(it);
            set_size--;
            return true;
        }
    }
    
    return false;
    
}

void set::clear() {
    
    set_size = 0;
    delete [] bucket_array;
    bucket_array_size = 0;
    
}

size_t set::size() const {        
    return set_size;
}

bool set::empty() const {
    return (set_size == 0);
}

set::~set() {
    delete [] bucket_array;
}
 

Testing cases test.cpp:

 #include <iostream>
#include "set.h"

int main() {

    set example;

    example.insert("Kazuya");
    example.insert("Mizuhara");

    std::cout << example.contains("kazUYa") << "n";
    std::cout << example.contains("mIzuHArA") << "n;

    example.insert("Chizuru");
    std::cout << example.contains("Chiziri") << "n";
    
    
    example.insert("Yukinoshita");
    example.insert("Yukino");
    example.insert("Mami");
    example.insert("Kanojo");
    example.insert("Sunset");
    

    example.insert("Horikita");
    example.insert("Alice");
    example.insert("Ellen");
    example.insert("Suzune");
    example.insert("Liza");

    std::cout << "Before remove:n";
    std::cout << example << "n";
    std::cout << example.size() << "n";
    
    example.remove("Kanojo");
    
    std::cout << "After remove:n";
    std::cout << example << "n";
    std::cout << example.size() << "n";

    auto example2 = example; // Copy constructor.

    std::cout << example << "n";
    std::cout << example.size() << "n";

    example2 = example; // Assignment.
    example = example;  // Self assignment.

    std::cout << example << "n";
    std::cout << example.size() << "n";
    std::cout << example2 << "n";
    std::cout << example2.size() << "n";

    example.clear();
    std::cout << example() << "n";

    return 0;
}
 

Проблема с программой

Когда я вывожу пример, установленный перед вызовом функции remove (), он показывает:

 Before remove:
bucket[0] = {Yukino, Horikita}
bucket[1] = {Yukinoshita, Mami, Ellen, Liza}
bucket[2] = {Kazuya, Mizuhara}
bucket[3] = {Chizuru, Kanojo, Sunset, Alice, Suzune}

13
 

Хотя он не должен вести себя таким образом. Я провел отладку в точке перед вызовом функции remove() и обнаружил, что set_size равен 13, bucket_array_size равен 4, что означает, что коэффициент загрузки уже превысил свой максимальный порог (двойной(13/4) > двойной(3)). В этом случае размер хэш-таблицы должен был измениться, и значения в ней были бы снова распределены с помощью хэш-функции. Однако, как видно, это работает не так.

Я пытался понять это, но не смог определить место, где возникла проблема.