La mia tabella hash è più lenta della ricerca binaria

Question

Ho implementato la ricerca binaria, la ricerca lineare e una tabella hash per confrontare ogni complessità temporale. Il problema è che in qualche modo, la mia tabella hash è molto più lenta della ricerca binaria quando misuro il tempo per trovare i numeri primi. Qui di seguito è il mio codice:

// Make the hash table 20 times the number of prime numbers 
HashTable::HashTable(std::vector<int> primes) 
{ 
    int tablesize = primes.size() * 20; 
    table = new std::list<int>[tablesize]; 
    size = tablesize; 
    for (auto &prime : primes) 
     this->insert(prime); 
} 

// Hash function 
int HashTable::hash(int key) 
{ 
    return key % size; 
} 

// Finds element 
int HashTable::find(int key) 
{ 
    // Get index from hash 
    int index = hash(key); 

    // Find element 
    std::list<int>::iterator foundelement = std::find(table[index].begin(), table[index].end(), key); 


    // If element has been found return index 
    // If not, return -1 
    if (foundelement != table[index].end()) 
     return index; 
    else 
     return -1; 
} 



// Adds element to hashtable 
void HashTable::insert(int element) 
{ 
    // Get index from hash and insert the element 
    int index = hash(element); 
    table[index].push_back(element); 
} 

HashTable.h

#ifndef HASHTABLE_H 
#define HASHTABLE_H 

#include <list> 
#include <iostream> 
#include <vector> 

class HashTable 
{ 
private: 
    // Each position in Hashtable has an array of lists to store elements in case of collision 
    std::list<int>* table; 

    // Size of hashtable 
    int size; 

    // Hashfunction that returns the array location for the given key 
    int hash(int key); 

public: 

    HashTable(int tablesize); 
    HashTable(std::vector<int> primes); 

    // Adds element to hashtable 
    void insert(int element); 

    // Deletes an element by key 
    void remove(int key); 

    // Returns an element from hashtable for a given key 
    int find(int key); 

    // Displays the hashtable 
    void printTable(); 

    // Display histogram to illustrate elements distribution 
    void printHistogram(); 

    // Returns the number of lists in hash table 
    int getSize(); 

    // Returns the total number of elements in hash table 
    int getNumberOfItems(); 

    // De-allocates all memory used for the Hash Table. 
    ~HashTable(); 
}; 

#endif 

Ho già provato a superare la dimensione della dimensione della tabella per eliminare le collisioni, ma non ho notato alcuna differenza.

Answer 1

E 'tutta una questione di complessità ricerca binaria è O (log n), e la vostra scoperta è lineare in modo O (n), ad un certo punto che era peggio quando si hanno un sacco di collisione.

Answer 2

alcune cose che sono sub-ottimale con l'attuazione tabella di hash:

• primes.size() * 20 è eccessivo - si otterrà molto di più cache miss del necessario; provare una gamma di valori compresi tra 1 e ~ 2 di trovare un punto ottimale

• primes.size() * 20 è sempre anche, e tutti i numeri primi si hash con key % size sono dispari, in modo da non hash nella metà secchi, spreco di spazio e degradanti prestazioni della cache

• si gestiscono collisioni con elenchi concatenati: ciò significa che si sta sempre seguendo almeno un puntatore di distanza dalla memoria contigua della tabella, che è lenta, e per le collisioni si fa il giro della memoria con ciascun nodo nell'elenco ; utilizzando std::vector<int> per memorizzare valori in collisione si limiterebbe a saltare a 1 area di memoria al di fuori della tabella hash, oppure si potrebbe usare l'hashing chiuso/aprire gli elenchi di spostamento e spostamento in genere trovare l'elemento in un bucket hash nelle vicinanze: i miei benchmark hanno rilevato che intorno a un ordine di grandezza più veloce per valori simili int.

Answer 3

Se i dati sono completamente casuali può essere difficile trovare una buona costante per l'operazione modulo. Se i tuoi dati seguono una sorta di modello, potresti provare a eseguire una serie di costanti candidate per vedere quale si comporta meglio sui tuoi dati.

Nel this post ho mostrato come si possa strutturare un test su larga scala. Alla fine la mia tabella hash ha prodotto una ricerca media in 1.5 confronti con il caso peggiore di 14. La tabella conteneva 16000 voci, circa 2^14.