Улучшение HashMap в языке C++


Я создал хранилище HashMap в языке C++. Я хотел бы помочь определить, если это хорошо или плохо.

У меня не обрабатываются ошибки или успехи с сообщениями. Я также не реализован коэффициент загрузки в этой карте. Как сейчас, после достижении предельного размера, больше никаких ключей не принимаются. Я написал этот код только в образовательных целях. Я хотел бы знать несколько вещей, чтобы сделать его лучше.

  1. Как я могу реализовать концепцию коэффициент нагрузки? Хэш-функция о/п зависит от предыдущих таблица размеров. Если мы хотим изменить размер таблицы, старые пары будут потеряны.

  2. Как я могу сделать это родовое? т. е. вместо можно ли написать шаблон код как ключ и значение?

    Реализация хэш-функции не будет проблемой, так как хэш-функция может быть перегружена. Насчет хранения? В случае с Java, ключ и значение будет рассматриваться как объект. Есть ли вариант похож на что в C++?

  3. Любое другое значение (или обязательной) особенностью этой карте отсутствует?

#include <string>
#include <vector>

using namespace std;

typedef struct Node {
string key;
int value;
struct Node * left;
struct Node * right;
}doubly;


class myHashStrKey{

private:
int currentCount;
int hashsize; // Default n = 2000. So 701 slots will be initialized.
vector<doubly *> table;

//hash function taken from net and modified.
size_t hash(const std::string data) {
    size_t h(0);
    for (int i=0; i<data.length(); i++){
        h = (h << (31-i) ^ (h >> i) ^ data[i]);
    }
    h = h%hashsize;
    return h;
}

//Inserts the key and value. If the key is already present, the value is updated.
//Checks if the currentCount < (hashsize+1)*3
void insertNode(doubly ** root, int Value, const string Key){

    if(*root ==NULL){
        if(myHashStrKey::currentCount >= ((hashsize+1)*3))
            return;
        doubly * newNode = new doubly();
        newNode->value = Value;
        newNode->left = NULL;
        newNode->right = NULL;
        newNode->key = (Key);
        *root = newNode;
        myHashStrKey::currentCount++;
        return;
    }

    doubly * prev = NULL;
    doubly * current = *root;
    while(current != NULL && ((current)->key).compare(Key)){
        prev = current;
        current = current->right;
    }

    if(current ==NULL){
        if(myHashStrKey::currentCount >= ((hashsize+1)*3))
            return;
        doubly *newNode = new doubly();
        newNode->value = Value;
        newNode->key = Key;
        newNode->left = prev;
        newNode->right = NULL;
        prev->right = newNode;
        myHashStrKey::currentCount++;
    }
    else{
        (current)->value = Value;
    }
}

//Return the corresponding value for the given key from the table
int getNodeValue(doubly * root, string key){
    while(root != NULL){
        if(!key.compare(root->key)){
            return root->value;
        }
        root = root->right;
    }
    return -1;
}

//Removes the node from bucket if present and reduces the currentcount
//else nothing.
void removeNode(doubly ** root, string Key){
    doubly * toRemove;
    doubly * head = *root;

    //Check to see if the first element is the target.
    if((head != NULL) &&!(head->key).compare(Key)){
        toRemove = head;
        *root = head->right;
        if(head->right != NULL)
            head->right->left = NULL;
        delete toRemove;
        myHashStrKey::currentCount--;
        return;
    }
    //First element is not the target.
    else{
        if(head == NULL)
            return;

        while((head != NULL) &&(head->key).compare(Key)){
            head = head->right;
        }
        //Element not present. return
        if(head == NULL)
            return;

        //Element found. Remove the element and decrement currentCount.
        toRemove = head;

        head->left->right = head->right;
        if(head->right !=NULL)
            head->right->left = head->left;

        myHashStrKey::currentCount--;
        delete toRemove;
        return;
    }
}

public:
//Constructor for default size.
//I am considering that hash table size to have default value of 701.
//The average elements per bucket is 3.
//THe total allowed elements will be 701*3 i.e. tablesize*3.
myHashStrKey(){
    myHashStrKey::currentCount=0;
    myHashStrKey::hashsize = 701;
    myHashStrKey::table.insert(myHashStrKey::table.begin(),hashsize,((doubly *)NULL));
}

//Constructor for the user given size
//Hashsize is calculated to be size/3 +1 (average elements per bucket is 3)
myHashStrKey(int size){
    myHashStrKey::currentCount=0;
    myHashStrKey::hashsize = size/3 +1;
    myHashStrKey::table.insert(myHashStrKey::table.begin(),hashsize,((doubly *)NULL));
}


//Adds entry to the HashMap
void addKeyValue(const string &key,int value ){
    size_t keyHash = hash(key);
    insertNode(&(table[keyHash]), value, key);
}

//Gets the corresponding value for the key if present else nothing
int getValue(const string &key ){
    size_t keyHash = hash(key);
    int result = getNodeValue(table[keyHash],key);
    return result;
}

//Deletes the key if present else nothing.
void deleteKey(const string &key){
    size_t keyHash = hash(key);
    removeNode(&(table[keyHash]),key);
}
};


3724
11
задан 21 февраля 2011 в 03:02 Источник Поделиться
Комментарии
2 ответа


Как реализовать концепт-коэффициент нагрузки, поскольку функция хэш-о/р зависит от размера таблицы. Если мы хотим изменить размер таблицы, старые пары будут потеряны.

Вам нужно будет переделывать, когда размер таблицы изменений, удаление узлов из старой таблицы и вставить их на новом месте в новой таблице. Я бы предложил вам убрать линии ч = ч%hashsize; от хэш - функции, и применять по модулю операции, когда вы на самом деле делать в таблице, по двум причинам:


  • Хэш-функции больше не будет зависеть от хэш-таблицы, и могут быть сделаны статической или функции, не являющейся членом

  • Вы можете хранить сырые хэш-значение в узле, так что вам не нужно пересчитывать, когда вы перепевы.


Как сделать это родовое ? т. е. вместо можно ли написать шаблон код как ключ и значение ?

Вы можете сделать ее универсальной, превращая его в шаблон класса, с параметрами шаблона, чтобы указать ключ и типы значений:

template <typename Key, typename Value>
class MyHashMap
{
struct Node
{
Key key;
Value value;
...
};
...
};

Затем найти, где вы используете строку в качестве типа ключа и заменить его на ключ; аналогично, заменить тип int в качестве типа значения с значением. Тогда вам необходимо убедиться, что вы всегда с помощью общих, а не конкретных типов операций над ними. В частности, свою (немного странно) сравнения строк нужно изменить, например, !(голова->ключ).сравнить(ключ) для руководителя->ключ == ключ - который является гораздо более читабельным в любом случае, на мой взгляд.

Наконец, как вы говорите, вам потребуется хэш-функций для каждого типа ключа. Лучший способ поддержать это движение хэш-функцию вне класса; любой пользователь хэш-шаблон может перегрузить ее в своих видах.


Любое другое значение (или обязательной )особенностью этой карте отсутствует ?

У вас нет деструктора, так что, когда карта будет уничтожен любой памяти, выделенной для узлов будут потеряны. Здесь есть два варианта:


  • Добавить деструктор, чтобы пройти через все остальные узлы и удалить их. Добавить конструктор копирования и оператор присваивания (или объявлять их собственный), чтобы предотвратить мелкое копирование, ведущих к двойному удалению.

  • Использовать память управляемый контейнер для хранения узлов; снять левый и правый указатели, и изменить тип таблицы из вектора в векторе >. На мой взгляд, это будет лучшим вариантом, так как он снимает ответственность за управление памятью из своего класса.

9
ответ дан 22 февраля 2011 в 11:02 Источник Поделиться

Другие особенности, которые могут быть удобный и не хватает: пустой(), размер(), методы addall(), метод removeall(), представление набора ключей, подмножество представлений, основанных на ввод ключа. И даже если это не ваша главная забота временем поиска представляется в логарифмической величины, которые могут снизить его процентов.

-1
ответ дан 3 марта 2011 в 06:03 Источник Поделиться