在哈希表中查找最长的冲突（链）

Question

我需要找到并输出插入哈希时发生的最长冲突table。我知道我必须记录所有的碰撞次数并找出最大的一次，但我一直在想办法。

这是我的代码：

class Entry {
private:
    int key;
    string value;
    Entry *next;
public:
    Entry(int key, string value) {
        this->key = key;
        this->value = value;
        this->next = NULL;
    }
    int getKey() {
        return key;
    }
    void setValue(string value) {
        this->value = value;
    }
    Entry *getNext() {
        return next;
    }
    void setNext(Entry *next) {
        this->next = next;
    }
};

const int TABLE_SIZE = 587;

class HashMap {
private:
    Entry **table;
public:
    HashMap() {
        table = new Entry*[TABLE_SIZE];
        for (int i = 0; i < TABLE_SIZE; i++)
        table[i] = NULL;
        }

void insert(int key, string value) {
    int hash = (key % TABLE_SIZE);
    if (table[hash] == NULL)
        table[hash] = new Entry(key, value);
    else {
        Entry *entry = table[hash];
        while (entry->getNext() != NULL)
            entry = entry->getNext();
        if (entry->getKey() == key)
            entry->setValue(value);
        else
            entry->setNext(new Entry(key, value));      
    }
}

int sizeofTable()
{
    return TABLE_SIZE;
}

~HashMap() {
    for (int i = 0; i < TABLE_SIZE; i++)
        if (table[i] != NULL) {
            Entry *prevEntry = NULL;
            Entry *entry = table[i];
            while (entry != NULL) {
                prevEntry = entry;
                entry = entry->getNext();
                delete prevEntry;
            }
        }
    delete[] table;
}

};

在 "insert" 中有没有简单的方法可以做到这一点？任何帮助表示赞赏。

Answer 1

您可以创建整数变量 maxChain 和 maxChainIndex 来分别跟踪最长的链及其索引。您的插入函数类似于：

void insert(int key, string value) {
    int hash = (key % TABLE_SIZE);
    int chain = 1;
    if (table[hash] == NULL)
        table[hash] = new Entry(key, value);
    else {
        Entry *entry = table[hash];
        while (entry->getNext() != NULL) {
            ++chain; //Count the entries as we're searching for the last one
            entry = entry->getNext();
            }
        if (entry->getKey() == key)
            entry->setValue(value);
        else {
            entry->setNext(new Entry(key, value)); 
            ++chain; //+1 for the newly inserted element.
           }   
    }
    if(chain > maxChain) { 
        maxChain = chain;
        maxChainIndex = hash;
        cout << "Current longest collision: " << maxChain << " at index: "
             << maxChainIndex << endl;
    }  
}

并且您可以创建一个函数来检索 maxChain，例如：

int getLongestChain() {
    return maxChain;
}

在哈希表中查找最长的冲突（链）

Finding the longest collision (chain) in hashtable

c++

hashtable

collision