自定义哈希实现带随机指针链表克隆时遇运行时错误求助

Let's figure out why your code is throwing runtime errors when assigning next and arb pointers, and get your custom hash table-based solution working properly.

Common Culprits for Runtime Errors #

First, let's break down the most likely issues:

• Invalid Pointers from Hash Table: Your get method might be returning garbage values instead of nullptr when the key (original node's next/arb) doesn't exist (like when it's nullptr itself).
• Out-of-Order Node Creation: If you try to assign copycurr->next before creating the corresponding cloned node and storing it in the hash table, you'll end up accessing invalid memory.
• Custom Hash Table Bugs: Issues with hash function logic, collision handling, or key lookup can lead to returning wrong pointers or failing to find existing entries.

Step-by-Step Fix #

1. Fix Your Custom Hash Table #

First, make sure your hash table handles pointer keys correctly and returns nullptr for missing keys:

• Hash Function: For pointer keys, convert the pointer to an unsigned integer and mod it by your table capacity (this ensures unique-ish hashes for distinct node addresses):

  int hashFunction(Node* key) {
      unsigned long addr = reinterpret_cast<unsigned long>(key);
      return addr % your_table_capacity;
  }
  

• Handle nullptr Keys: Add a check at the start of your get method to return nullptr immediately if the input key is nullptr (since we don't store nullptr as a key):

  Node* get(Node* key) {
      if (key == nullptr) return nullptr;
      // Rest of your lookup logic...
      // If key not found after traversal, return nullptr
      return nullptr;
  }
  

• Collision Handling: If you're using chaining (linked lists for hash buckets), double-check that you're traversing the entire bucket to find existing keys, and inserting new nodes correctly without breaking the chain.

2. Adjust Cloning Logic to Two Passes #

The key fix here is to first create all cloned nodes and map them to original nodes, then assign next and arb pointers. This ensures every original node's counterpart exists in the hash table when you need it:

struct Node {
    int data;
    Node* next;
    Node* arb;
    Node(int x) : data(x), next(nullptr), arb(nullptr) {}
};

// Your custom HashMap class here (with fixes above)

Node* clone(Node* head) {
    if (!head) return nullptr;

    HashMap<Node*, Node*> nodeMap;

    // Pass 1: Create all cloned nodes and build the mapping
    Node* curr = head;
    while (curr) {
        Node* clonedNode = new Node(curr->data);
        // Initialize next/arb to nullptr to avoid wild pointers
        clonedNode->next = nullptr;
        clonedNode->arb = nullptr;
        nodeMap.put(curr, clonedNode);
        curr = curr->next;
    }

    // Pass 2: Assign next and arb pointers using the mapping
    curr = head;
    while (curr) {
        Node* clonedCurr = nodeMap.get(curr);
        // The get method returns nullptr if curr->next/arb is nullptr, which is exactly what we want
        clonedCurr->next = nodeMap.get(curr->next);
        clonedCurr->arb = nodeMap.get(curr->arb);
        curr = curr->next;
    }

    return nodeMap.get(head);
}

3. Example Custom Hash Table Implementation #

Here's a simplified, working custom hash table tailored for this problem:

template<typename K, typename V>
struct HashNode {
    K key;
    V value;
    HashNode* next;
    HashNode(K k, V v) : key(k), value(v), next(nullptr) {}
};

template<typename K, typename V>
class HashMap {
private:
    HashNode<K, V>** table;
    int capacity;

    int hash(K key) {
        unsigned long addr = reinterpret_cast<unsigned long>(key);
        return addr % capacity;
    }

public:
    HashMap(int cap = 100) : capacity(cap) {
        table = new HashNode<K, V>*[cap]();
        for (int i = 0; i < cap; i++) table[i] = nullptr;
    }

    ~HashMap() {
        for (int i = 0; i < capacity; i++) {
            HashNode<K, V>* curr = table[i];
            while (curr) {
                HashNode<K, V>* temp = curr;
                curr = curr->next;
                delete temp;
            }
        }
        delete[] table;
    }

    void put(K key, V value) {
        if (!key) return;
        int idx = hash(key);
        HashNode<K, V>* curr = table[idx];
        // Update if key exists
        while (curr) {
            if (curr->key == key) {
                curr->value = value;
                return;
            }
            curr = curr->next;
        }
        // Insert new node
        HashNode<K, V>* newNode = new HashNode<K, V>(key, value);
        newNode->next = table[idx];
        table[idx] = newNode;
    }

    V get(K key) {
        if (!key) return nullptr;
        int idx = hash(key);
        HashNode<K, V>* curr = table[idx];
        while (curr) {
            if (curr->key == key) return curr->value;
            curr = curr->next;
        }
        return nullptr;
    }
};

Final Checks #

• Run through a small test case manually: trace the creation of cloned nodes and the mapping to ensure every next/arb assignment points to the correct cloned node.
• If you're still getting errors, add debug prints to your hash table's put and get methods to verify that keys are being stored and retrieved correctly.

内容的提问来源于stack exchange，提问作者somerandomguy