比较哈希 table 值并创建前 N 个单词的数组

Question

我创建了结构的散列 table。每个结构都有计数。我很好奇如何遍历每个键和单独的链并找到最高计数并将其添加到数组中。

struct wordItem
{
    std::string word;
    int count;
    wordItem* next;
};

这是我目前所拥有的。我的思考过程是将每个项目与每个项目进行比较。所以转到初始密钥，然后遍历每个链。欢迎提出建议。

void HashTable::printTopN(int n) {

wordItem* arr[n];
wordItem* temp;
int i;
for (i=0;i<hashTableSize; i++){
    temp = hashTable[i];
    while (temp!=NULL){
        for (int j = 0; j<n; j++){
            if(arr[n]->count<temp->count&&arr[n+1]->count<temp->count){

                arr[n]=arr[n+1];
                arr[n] = temp;
            }
        }
        temp = temp->next;
    }


}
for (int k = 0; k < n; k++)

    std::cout<<arr[n]->word<<"--"<<arr[n]->count;

} 这也是我的 addWord 函数，用于获取更多背景信息。

void HashTable::addWord(std::string word) {
int hash_val = getHash(word);
wordItem* prev = NULL;
wordItem* entry = hashTable[hash_val];
while (entry != NULL)
{
    prev = entry;
    entry = entry->next;
}
    if (entry == NULL)
    {
        entry = new wordItem;
        entry->count = 1;
        entry->word = word;
        entry ->next = NULL;
        if (prev == NULL)
        {
            hashTable[hash_val]= entry;
        }
        else
        {
            prev->next = entry;
        }
}
    incrementCount(word);
    entry->word = word;

}

HPP 文件

struct wordItem
{
    std::string word;
    int count;
    wordItem* next;
};

const int STOPWORD_LIST_SIZE = 50;


class HashTable {

public:
    HashTable(int hashTableSize);
    ~HashTable();
    void getStopWords(char *ignoreWordFileName);
    bool isStopWord(std::string word);
    bool isInTable(std::string word);
    void incrementCount(std::string word);
    void addWord(std::string word);
    int getTotalNumberNonStopWords();
    void printTopN(int n);
    int getNumUniqueWords();
    int getNumCollisions();
    int getHash(std::string word);
private:


    wordItem* searchTable(std::string word);
    int numUniqueWords;
    int numCollisions;
    int hashTableSize;
    wordItem** hashTable;
    std::vector<std::string> vecIgnoreWords =
            std::vector<std::string>(STOPWORD_LIST_SIZE);

};

Answer 1

创建一个包含 N 项的数组。对于 table 中的每一项，遍历数组并检查是否 current_array_item <= table_item <= next_array_item。如果是，将数组中所有 <= current_array_item 的项目移动一位（从数组中删除最小的一项）并插入 table_item 代替 current_array_item.

比较哈希 table 值并创建前 N 个单词的数组

Comparing Hash table values and creating an array of top N words

c++

sorting

hashtable