c++ - 在优先级队列中调试 Setkey 函数时遇到问题

Question

我无法弄清楚我的优先级队列的 setKey 函数出了什么问题。我正在使用哈希表在恒定时间内从其 id（与该节点关联的字符串）获取堆中节点的位置。哈希表将 id 映射到 hashItems 向量中的索引，其中包含指向节点的指针。但是当我尝试从指针获取索引时，我得到一个很大的数字，这会导致分段错误。

我相当确定问题出在我的 hashTable 类上，就像我没有正确处理指针一样。

这是我的堆类的头文件。

#ifndef _HEAP_H
#define _HEAP_H

#include <vector>
#include <string>
#include "hash.cpp"

class heap
{

public:
//=
  // heap - The constructor allocates space for the nodes of the heap
  // and the mapping (hash table) based on the specified capacity
  //
  heap(int capacity);

  //
  // insert - Inserts a new node into the binary heap
  //
  // Inserts a node with the specified id string, key,
  // and optionally a pointer.  They key is used to
  // determine the final position of the new node.
  //
  // Returns:
  //   0 on success
  //   1 if the heap is already filled to capacity
  //   2 if a node with the given id already exists (but the heap
  //     is not filled to capacity)
  //
  int insert(const std::string &id, int key, void *pv = nullptr);

  //
  // setKey - set the key of the specified node to the specified value
  //
  // I have decided that the class should provide this member function
  // instead of two separate increaseKey and decreaseKey functions.
  //
  // Returns:
  //   0 on success
  //   1 if a node with the given id does not exist
  //
  int setKey(const std::string &id, int key);



//node class 
  //an object containing an id (for the heap), a key that determines its
  //position on the heap
  //and also its position on the heap
    class node
    {
    public:
    node(std::string identi, int pass, void* pvData, int pos);
    node() = default;
        std::string id;
        int key;
        void *pData;
    int position;
    };


  private:
    int size;
    int capacity;
    std::vector<node> data;
    hashTable* map;

  public:

//fixes the heap after a key is changed or
    //a node is inserted
    void percolateUp(int posCur)
    {
    //index will be the current position of the node
    int index = posCur;
    node element = data[index];

    //while we haven't reached the top of the heap
    //and the key of the node is still smaller than that of its parent
    while(index > 1 and element.key < data[index / 2].key)
    {
      //push the parent down the heap
      data[index] = data[index / 2];
      index = index / 2;
    }
    //once the heap has been corrected
    //change the position of the node
    element.position = index;
    //set data[index] to element
    data[index] = element;
    }
    

  //fixes the heap after a key is changed
    void percolateDown(int posCur)
  {
    //index will be the current position of the node
      int index = posCur;
      node element = data[index];

    //while we haven't reached the bottom of the heap
      while(index < size + 1)
      {
        //if the key of the element is greater than that of its left child
        if(element.key > data[index * 2].key)
        {
          //push the left child up the heap
          data[index] = data[index*2];
          //take its place on the heap
          index = index *2;
        }
        //if the key of the element is greater than that of its right child
        else if(element.key > data[index * 2 + 1].key)
        {
          //push the right child up the heap
          data[index] = data[index*2 + 1];
          //take its place on the heap
          index = index *2 + 1;
        }
        //else, we found the right place for the node in the heap
        else
        {
          break;
        }
    }
    //once the heap has been corrected
    //change the position of the node
    element.position = index;
    //set data[index] to element
    data[index] = element;
  }

};

#endif //_HEAP_H

这是我对堆类的实现：

#include "heap.h"
#include <stdio.h>
#include <stdlib.h>


//constructor for heap object
//capacity: measure of how much space in heap is left
//size: measure of how many elements (nodes) in heap
//map is a hashTable that allows for constant time access to pointers to nodes from their ids
//creates a hashTable
heap::heap(int length)
{
    data.resize(length + 1);
    capacity = length;
    size = 0;
    map = new hashTable(2*capacity);
}

//constructor for node object
//has an id which is used by the hashTable
//a key which is used to determine its position in the heap
heap::node::node(std::string identi, int pass, void* pvData, int pos)
{
    id = identi;
    key = pass;
    pData = pvData;
    position = pos;
}
//inserts into heap and adjusts based on key
int heap::insert(const std::string &id, int key, void *pv)
{
    //if the heap is almost full, return 1
    if (size == capacity - 1)
    {
        return 1;
    }
    //if the id is already in use, return 2
    if(map -> contains(id))
    {
        return 2;
    }
    //index keeps track of index of element to be inserted
    //begin by setting it to the final position in the heap
    int index = size + 1;
    //make a node based on the information given
    node element = node(id, key, pv, index);
    //set the last element in the heap to the node made
    data[index] = element;

    //call to percolateUp, adjusts the heap
    percolateUp(index);

    //make a pointer to the node
    node* ptr = &element;
    //insert the id, pointer pair to the map
    map -> insert(id, ptr);
    //increment size
    size += 1;
    //decrease capacity
    capacity -= 1;
    //return 0 on success
    return 0;
}

//changes the key of a node specified by id in the heap
//and then adjusts the heap
int heap::setKey(const std::string &id, int key)
{
    //if the node with that id is not in the map/heap
    //return 1
    if (not map -> contains(id))
    {
        return 1;
    }
    //use map to get the pointer to the node with that id
    node *element = (node*)(map -> getPointer(id));
    //prints out id, right now prints out just a new line
    std::cout <<  element -> id << std::endl;
    //sets key of the node to the given key
    element -> key = key;
    //get the current position of element and put it into index
    int index = element -> position;

    //doesn't give correct position. Gives 1823232313. Something's wrong here.

    //do percolate up
    percolateUp(index);
    //then percolate down
    //if percolateUp doesn't do anything, we need to percolateDown
    //and if it does do something, the heap is perfectly ordered
    //and percolateDown won't do anything
    percolateDown(index);

    //return 0 on success
    return 0;
}

这是我的 hashTable 类的头文件：

#ifndef _HASH_H
#define _HASH_H

#include <vector>
#include <string>

class hashTable {

 public:

  // The constructor initializes the hash table.
  // Uses getPrime to choose a prime number at least as large as
  // the specified size for the initial size of the hash table.
  hashTable(int size = 0);

  // Insert the specified key into the hash table.
  // If an optional pointer is provided,
  // associate that pointer with the key.
  // Returns 0 on success,
  // 1 if key already exists in hash table,
  // 2 if rehash fails.
  int insert(const std::string &key, void *pv = nullptr);

  // Check if the specified key is in the hash table.
  // If so, return true; otherwise, return false.
  bool contains(const std::string &key);

  // Get the pointer associated with the specified key.
  // If the key does not exist in the hash table, return nullptr.
  // If an optional pointer to a bool is provided,
  // set the bool to true if the key is in the hash table,
  // and set the bool to false otherwise.
  void *getPointer(const std::string &key, bool *b = nullptr);


 
 private:

  // Each item in the hash table contains:
  // key - a string used as a key.
  // isOccupied - if false, this entry is empty,
  //              and the other fields are meaningless.
  // isDeleted - if true, this item has been lazily deleted.
  // pv - a pointer related to the key;
  //      nullptr if no pointer was provided to insert.
  class hashItem {
  public:
    std::string key = "";
    bool isOccupied = false;
    bool isDeleted = false;
    void *pv = nullptr;

    hashItem() = default;
  };

  int capacity; // The current capacity of the hash table.
  int filled; // Number of occupied items in the table.
  size_t length;

  std::vector<hashItem> data; // The actual entries are here.

  // The hash function.
  int hash(const std::string &key);



  // Return a prime number at least as large as size.
  // Uses a precomputed sequence of selected prime numbers.
  static unsigned int getPrime(int size);
};

#endif //_HASH_H

最后，这是我的 hashTable 类的实现

#include "hash.h"
#include <typeinfo>
#include <stdio.h>
#include <stdlib.h>

//returns a prime number depending on size required for hash table
//supports a size of up to one million
unsigned int hashTable::getPrime(int size)
{
    if (size <= 10000) { return 12373;}
    if (size <= 20000) {return 25867;}
    if (size <= 50000) {return 51479;}
    if (size <= 100000) {return 109211;}
    if (size <= 200000) {return 202717;}
    if (size <= 400000) {return 410299;}
    if (size <= 800000) {return 803549;}
    if (size <= 1600000) {return 2001101;}
    return 3200983;
}

// constructor for hashTable class
//takes initial size input and makes size of table from getPrime
//sets capacity to be initially the size of the hash table
hashTable::hashTable(int size)
{
    int num = getPrime(size);
    length = num;
    data.resize(num);
    capacity = length;
    filled = 0;
}



//hash function
//uses linear probing in the event of a collision
//which is where the function goes from the index
//where the initial hash sent the string to and 
//goes down the table until it either finds a free space
//or it finds the hashitem with that key value
int hashTable::hash(const std::string &key)
{
    int hashVal = 0;
    for(char ch: key)
    {
        hashVal = 37*hashVal + ch;
    }
    int i = 0;

    if (data[hashVal % length].isOccupied)
    {
        while( data[(hashVal + i) % length].isOccupied and 
            (data[(hashVal + i)% length].key).compare(key) != 0)
        {
            i += 1;
        }
    }
    return (hashVal + i) % length;
}

//insert function inserts key into position given by hash function
//changes filled and capacity number
//returns 0 on success, 1 when the key has already been inserted
//and 2 if there was a memory allocation error in the rehash function
//if the loading size exceeds 0.5, it rehashes
//this means that at any given time, the hashtable only uses a 1/3 of its actual size
//which is necessary in order to decrease the likelihood of collisions
int hashTable::insert(const std::string &key, void *pv)
{
    int index = hash(key);
    if ((data[index].key).compare(key) == 0)
    {
        return 1;
    }
    data[index] = hashItem();
    data[index].isOccupied = true;
    data[index].key = key;
    data[index].pv = pv;
    filled += 1;
    capacity -= 1;
    if (filled/capacity > 0.5)
    {
       return 2;
    }
    return 0;
}


//checks if key is in hash table
bool hashTable::contains(const std::string &key)
{
    return (data[hash(key)]).isOccupied and not((data[hash(key)]).isDeleted);
}

//retrieves pointer in hashItem from hashtable
//also writes to a boolean pointer whether or not key is in the table
//returns nullptr if not in the table
void* hashTable::getPointer(const std::string &key, bool *b)
{
    bool con = contains(key);
    b = &con;
    if(not con)
    {
        return nullptr;
    }
    return data[hash(key)].pv;
}

标签： c++debugginghashtableheappriority-queue