HashSearch und HashInsert Funktionen Implementierung nach Cormen Buch

Question

Für meinen Algorithmus brauche ich eine andere Funktion namens h(k, i) Ich denke, es ist die Suche nach dem Hash, um zu sehen, ob es leer ist und dann das Element auf i Position einfügen, aber ich bin mir nicht sicher. Kann mir jemand diese Funktion erklären? Vielen Dank. Hier ist mein Code soweit.

#include <iostream> 
    using namespace std; 
    #define hashSize 1000 
    typedef struct hashElem{ 
     char* date; 
     char* holiday; 
    }hashElem; 

    typedef struct hash{ 
     struct hashElem element; 
     struct hash* next; 
    }hash; 

    void h(hash* hashTable[hashTable],int index) 
    { 

    } 

    int hashInsert (hash* hashTable[hashSize],int k) 
    { 
     int index=0,index2; 
     do 
     { 
      index2=h(k,index); 
      if (hashTable[index2]== NULL) { 
       hashTable[index2] = k; 
       return index2; 
      } 
      else 
       index=index+1; 
     } 
     while (index == hashSize); 
     printf ("Hash Table Overflow"); 
    } 
    int hashSearch (hash* hashTable[hashSize],int k){ 
     int index=0,index2; 
     do 
     { 
      index2=h(k,index); 
      if (hash* hashTable[index2]==k) 
       return index2; 
      index=index+1; 
     } 
     while (hash* hashTable[index2]==NULL || index=hashSize); 
     return NULL; 
     } 
    int main() { 
     cout << "Hello, World!" << endl; 
     return 0; 
    } 

Answer 1

Hier ist ein Beispiel für eine Hash-Tabelle für allgemeine Demonstrationszwecke.

HashMap.h

#ifndef HASH_MAP_H 
#define HASH_MAP_H 

// ============ Hash Entry ====================== 
class HashEntry { 
private: 
    int m_key; 
    int m_value; 

public: 
    HashEntry(int key, int value); 

    int getKey() const; 
    int getValue() const; 
}; // HashEntry 

// ========== Hash Map ========================== 
class HashMap { 
public: 
    static const int TABLE_SIZE; 

private: 
    HashEntry** m_pTable; 

public: 
    HashMap(); 
    ~HashMap(); 

    int get(int key) const; 
    void insert(int key, int value); 

}; // HashMap 

#endif // HASH_MAP_H 

HashMap.cpp

// ================ Hash Entry ================== 
HashEntry::HashEntry(int key, int value) : 
m_key(key), 
m_value(value) { 
} // HashKey 

int HashEntry::getKey() const { 
    return m_key; 
} // getKey 

int HashEntry::getValue() const { 
    return m_value; 
} // getValue 

// ================ Hash Map ==================== 
const int HashMap::TABLE_SIZE = 128; 

HashMap::HashMap() { 
    m_pTable = new HashEntry*[TABLE_SIZE]; 

    for (unsigned u = 0; u < TABLE_SIZE; u++) { 
     m_pTable[u] = nullptr; 
    } 
} // HashMap 

HashMap::~HashMap() { 
    for (unsigned u = 0; u < TABLE_SIZE; u++) { 
     if (m_pTable[u] != nullptr) { 
      delete m_pTable[u]; 
     } 
    } 
    delete[] m_pTable; 
} // ~HashMap 

int HashMap::get(int key) const { 
    int hash = (key % TABLE_SIZE); 

    while (m_pTable[hash] != nullptr && m_pTable[hash]->getKey() != key) { 
     hash = (hash + 1) % TABLE_SIZE; 
    } 

    if (m_pTable[hash] == nullptr) { 
     return -1; 
    } else { 
     return m_pTable[hash]->getValue(); 
    } 
} // get 

void HashMap::insert(int key, int value) { 
    int hash = (key % TABLE_SIZE); 

    while (m_pTable[hash] != nullptr && m_pTable[hash]->getKey() != key) { 
     hash = (hash + 1) % TABLE_SIZE; 
    } 

    if (m_pTable[hash] != nullptr) { 
     delete m_pTable[hash]; 
    } 
    m_pTable[hash] = new HashEntry(key, value); 
} // insert 

Und hier ist es im Einsatz:

main.cpp

#include <iostream> 
#include "HashMap.h" 

int main() { 
    HashMap myHash; 

    myHash.insert(1, 22); 
    myHash.insert(2, 445); 
    myHash.insert(3, 12); 
    myHash.insert(6, 24); 
    myHash.insert(4, 9); 

    std::cout << "My Hash Table: " << std::endl; 
    std::cout << "Key: 1 - Value: " << myHash.get(1) << std::endl; 
    std::cout << "Key: 6 - Value: " << myHash.get(6) << std::endl; 
    std::cout << "Key: 4 - Value: " << myHash.get(4) << std::endl; 

    return RETURN_OK; 
} // main 

Jetzt können Sie diese Klasse nehmen und den Schlüssel und den Wert auf jeden geeigneten Typ ändern, aber noch mehr, um dies wiederverwendbar und generisch zu machen; Sie können diese Klasse einfach anpassen. Wenn Sie einen modernen Compiler verwenden, können Sie sie anstelle von unformatierten Zeigern für intelligente Zeiger wie std::shared_ptr<> oder std::unique_ptr<> austauschen, sodass Sie sich keine Gedanken über Speicherlecks machen müssen. in Ihrem Code zu nehmen dies nur dies kann man noch einen Schritt weiter jedoch einfach tun:

#include <iostream> 
#include <string> 
#include <unordered_map> 

int main() { 
    // Normally all of this code within this main function would be 
    // a part of a class, I'm just showing a demonstration of how 
    // one can use std::unordered_map<> for a Hash Map. 
    std::string date; 
    std::string holiday; 

    typedef std::unordered_map<std::string, std::string> HashTable; 
    HashTable myTable; 

    myTable.insert(HashTable::value_type("January 1st", "New Years Day")); 
    myTable.insert(HashTable::value_type("July 4th", "Fourth of July")); 
    myTable.insert(HashTable::value_type("December 25th, "Christmas")); 

    // Then To Search The Hash Table: 
    // Usually This would be in a class's function that returns the value 
    // when a specified key was passed in as a parameter. 
    HashTable::const_iterator it = myTable.find("Feburary 14th"); 
    if (it == myTable.cend()) { 
     std::cout << "Date & Holiday not found!"; 
    } else { 
     std::cout << myTable->second; 
    } 

    // As you can see this is repeat code! 
    // A class that would search a hash table would have 
    // something like this as a member function. 
    HashTable::const_iterator it = myTable.find("January 1st"); 
    if (it == myTable.cend()) { 
     std::cout << "Date & Holiday not found!"; 
    } else { 
     std::cout << myTable->second; 
    } 
    // Except for printing out the element they would return the value and 
    // in most cases they would return a pointer to an object, this 
    // way if it is not found, a nullptr is returned. 

    return 0;   
} 

Answer 2

Ihre „h-Funktion“ ist eine Hash-Funktion, dauert es einen Schlüssel als Eingabe und gibt eine Position des Schlüssels in die Hash-Tabelle.

Eine einfache Hash-Funktion kann return key % tablesize sein.

Offenbar kann eine solche einfache Hash-Funktion dazu führen, dass verschiedene Schlüssel dieselbe Position haben, die als "Kollisionen" bezeichnet werden. Die Auswahl einer geeigneten Hash-Funktion und die Wahl eines Weges zur Lösung der Kollisionen ist ein weites Thema.

Es gibt Situationen, in denen wir eine perfekte Hash-Funktion finden können, um Kollisionen zu vermeiden, und das ist ein noch schwierigeres Thema.

Normalerweise durchsuchen wir in einer Hash-Funktion nicht die gesamte Hash-Tabelle und finden eine leere Position, die zurückgegeben werden soll, da wir davon ausgehen, dass die Hash-Funktion O (1) -Zeit benötigt.