Как можно реализовать дерево AVL в этой хэш-карте? - PullRequest
Новая
       28

Как можно реализовать дерево AVL в этой хэш-карте?

0 голосов
/ 05 июня 2019

Итак, мой друг предложил мне создать хэш-карту, в которой для хранения нескольких узлов использовались деревья AVL, а не корзины.Я создал стандартную карту Hash в качестве отправной точки, по совету моего учителя, но я не уверен, куда идти дальше.Любая помощь приветствуется!:)

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

Node.h

#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <float.h>
#include <iostream>
template<typename K, typename V>

//Hashnode class 
class HashNode
{
public:
    V value;
    HashNode* left;
    HashNode* right;
    K key;

//Constructor of hashnode  
HashNode(K key, V value)
{
    this->value = value;
    this->key = key;
}
};
_________________________________________________________________
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <float.h>
#include <iostream>
#include "Node.h"
using namespace std;

//template for generic type 
template<typename K, typename V>

//Our own Hashmap class 
class HashMap
{
    //hash element array 
    HashNode<K, V> **arr;
    int capacity;
    //current size 
    int size;
    //dummy node 
    HashNode<K, V> *dummy;

public:
    HashMap()
    {
        //Initial capacity of hash array 
        capacity = 20;
        size = 0;
        arr = new HashNode<K, V>*[capacity];

        //Initialise all elements of array as NULL 
        for (int i = 0; i < capacity; i++)
            arr[i] = NULL;

        //dummy node with value and key -1 
        dummy = new HashNode<K, V>(-1, -1);
    }
    // This implements hash function to find index 
    // for a key 
    int hashCode(K key)
    {
        return key % capacity;
    }

    //Function to add key value pair 
    void insertNode(K key, V value)
    {
        HashNode<K, V> *temp = new HashNode<K, V>(key, value);

         // Apply hash function to find index for given key 
        int hashIndex = hashCode(key);

        //find next free space  
        while (arr[hashIndex] != NULL && arr[hashIndex]->key != key
            && arr[hashIndex]->key != -1)
        {
            hashIndex++;
            hashIndex %= capacity;
        }

        //if new node to be inserted increase the current size 
        if (arr[hashIndex] == NULL || arr[hashIndex]->key == -1)
        size++;
        arr[hashIndex] = temp;
         }

    //Function to delete a key value pair 
     V deleteNode(int key)
     {
         // Apply hash function to find index for given key 
         int hashIndex = hashCode(key);

        //finding the node with given key 
        while (arr[hashIndex] != NULL)
        {
            //if node found 
        if (arr[hashIndex]->key == key)
        {
            HashNode<K, V> *temp = arr[hashIndex];

            //Insert dummy node here for further use 
            arr[hashIndex] = dummy;

            // Reduce size 
            size--;
            return temp->value;
        }
        hashIndex++;
        hashIndex %= capacity;

    }

    //If not found return null 
    return NULL;
}

    //Function to search the value for a given key 
    V get(int key)
    {
        // Apply hash function to find index for given key 
        int hashIndex = hashCode(key);
        int counter = 0;
        //finding the node with given key    
        while (arr[hashIndex] != NULL)
        {
            int counter = 0;
            if (counter++ > capacity)  //to avoid infinite loop 
                return NULL;
            //if node found return its value 
            if (arr[hashIndex]->key == key)
                return arr[hashIndex]->value;
            hashIndex++;
            hashIndex %= capacity;
        }

        //If not found return null 
        return NULL;
    }

    //Return current size  
    int sizeofMap()
    {
        return size;
    }

    //Return true if size is 0 
    bool isEmpty()
    {
        return size == 0;
    }

    //Function to display the stored key value pairs 
    void display()
    {
        for (int i = 0; i < capacity; i++)
        {
            if (arr[i] != NULL && arr[i]->key != -1)
                cout << "key = " << arr[i]->key
                << "  value = " << arr[i]->value << endl;
        }
    }
};

Ожидаемые результаты состоят в том, что AVL должна работать должным образом вместе с хэш-картой, но я не уверен, как метафорически связать два из них.

1 Ответ

0 голосов
/ 05 июня 2019

Ваша текущая реализация использует стратегию поиска другого свободного узла в случае коллизии хеша. Если вы хотите использовать дерево AVL (или R / B), вам следует расширить каждый элемент массива для хранения всех коллизий. В качестве первого шага вы можете сохранить в каждом узле связанный список или указатель на вектор. Следующим шагом является использование библиотеки деревьев. Желательно встроенный. Обычно в std :: map используется красно-черное дерево, которое изоморфно AVL, но с немного другим профилем производительности. Вы можете использовать карту std в качестве контейнера «tree».

Обратите внимание, что ваш тип ключа должен быть сопоставим (оператор <</strong>, и ваш он также должен обеспечивать способ вычисления хэша. Ваша текущая реализация подразумевает кардинальный тип, конвертируемый в целое число . 



template<typename K, typename V>
class HashMap
{
   typedef stf::map HashNode;
 ...  
   void insertNode(K key, V value)
   {
       HashNode<K, V> *temp = new HashNode<K, V>={{key, value}};

        // Apply hash function to find index for given key 
       int hashIndex = hashCode(key);

       if(NULL == arr[hashIndex] ){
         arr[hashIndex] = new std::map<K,V>();
       }
       arr[hashIndex]->insert(std::pair<K,V>(key,value);

       size++;
...
//resize if the capacity is needed
   }

...
...