0Pricing
C++ Academy · Lezione

Funzioni hash personalizzate

Calcolare l'hash dei propri tipi

Funzioni hash personalizzate è una lezione C++ Academy gratuita su CoddyKit. Questa è la lezione 3 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento C++ Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso C++ Academy include 4 lezioni in totale.

Perché usare hash personalizzati?

I contenitori non ordinati hanno bisogno di un metodo per calcolare l'hash delle chiavi. I tipi incorporati e std::string dispongono già di funzioni hash, ma i propri tipi no. È necessario fornirne una.

#include <iostream>
#include <unordered_set>
#include <string>

int main() {
    std::unordered_set<std::string> s{"hi"};
    std::cout << s.count("hi") << '\n';
    return 0;
}

Il template std::hash

std::hash è un funtore che associa un valore a un size_t. Lo si invoca come una funzione.

#include <iostream>
#include <functional>
#include <string>

int main() {
    std::hash<std::string> h;
    std::cout << "hash exists and returns a size_t\n";
    std::size_t v = h("hello");
    std::cout << (v != 0 ? "non-zero hash" : "zero") << '\n';
    return 0;
}

Una struct da sottoporre ad hash

Supponiamo di avere una Point con due int. Per memorizzarla in un unordered_set servono sia l'uguaglianza sia un hash.

#include <iostream>

struct Point {
    int x, y;
    bool operator==(const Point& o) const { return x == o.x && y == o.y; }
};

int main() {
    Point a{1, 2}, b{1, 2};
    std::cout << std::boolalpha << (a == b) << '\n';
    return 0;
}

Scrivere un funtore hash

Un funtore hash è una struct con operator() che restituisce un size_t. Combini gli hash dei campi, spesso usando XOR e uno shift.

#include <iostream>
#include <functional>

struct Point { int x, y; };

struct PointHash {
    std::size_t operator()(const Point& p) const {
        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
    }
};

int main() {
    PointHash h;
    std::cout << "hashed: " << (h({3, 4}) != 0 ? "ok" : "zero") << '\n';
    return 0;
}

Usare il funtore hash

Passi il funtore hash come secondo argomento del template del contenitore unordered.

#include <iostream>
#include <unordered_set>
#include <functional>

struct Point {
    int x, y;
    bool operator==(const Point& o) const { return x == o.x && y == o.y; }
};

struct PointHash {
    std::size_t operator()(const Point& p) const {
        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
    }
};

int main() {
    std::unordered_set<Point, PointHash> pts;
    pts.insert({1, 2});
    pts.insert({1, 2});
    std::cout << pts.size() << '\n';
    return 0;
}

Serve anche l'uguaglianza

Due chiavi finiscono nello stesso bucket se i loro hash collidono. Il contenitore usa quindi operator== per distinguerle, perciò l'uguaglianza è obbligatoria.

#include <iostream>
#include <unordered_set>

struct Point {
    int x, y;
    bool operator==(const Point& o) const { return x == o.x && y == o.y; }
};

struct PointHash {
    std::size_t operator()(const Point& p) const {
        return std::hash<int>()(p.x * 31 + p.y);
    }
};

int main() {
    std::unordered_set<Point, PointHash> s{{1, 1}, {2, 2}};
    std::cout << s.count({1, 1}) << '\n';
    return 0;
}

Usare un hash come chiave di una map

Lo stesso hash personalizzato consente di usare una struct come chiave in un unordered_map.

#include <iostream>
#include <unordered_map>
#include <functional>

struct Point {
    int x, y;
    bool operator==(const Point& o) const { return x == o.x && y == o.y; }
};

struct PointHash {
    std::size_t operator()(const Point& p) const {
        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
    }
};

int main() {
    std::unordered_map<Point, std::string, PointHash> m;
    m[{0, 0}] = "origin";
    std::cout << m[{0, 0}] << '\n';
    return 0;
}

Combinare più campi

Un helper comune combina gli hash un campo alla volta, usando un modello di moltiplicazione e somma simile a boost::hash_combine.

#include <iostream>
#include <functional>

std::size_t combine(std::size_t seed, std::size_t v) {
    return seed ^ (v + 0x9e3779b9 + (seed << 6) + (seed >> 2));
}

int main() {
    std::size_t h = 0;
    h = combine(h, std::hash<int>()(10));
    h = combine(h, std::hash<int>()(20));
    std::cout << (h != 0 ? "combined ok" : "zero") << '\n';
    return 0;
}

Una buona distribuzione degli hash

Un hash inefficace che restituisce una costante inserisce tutto in un unico bucket, degradando a O(n). Mescoli bene i bit di tutti i campi.

#include <iostream>
#include <functional>

struct Bad { std::size_t operator()(int) const { return 0; } };
struct Good { std::size_t operator()(int x) const { return std::hash<int>()(x); } };

int main() {
    std::cout << Bad()(5) << ' ' << (Good()(5) != 0 ? "varies" : "0") << '\n';
    return 0;
}

Specializzare std::hash

In alternativa, specializzi std::hash per il proprio tipo, così funzionerà senza dover passare esplicitamente un funtore.

#include <iostream>
#include <unordered_set>

struct Point {
    int x, y;
    bool operator==(const Point& o) const { return x == o.x && y == o.y; }
};

namespace std {
    template <> struct hash<Point> {
        std::size_t operator()(const Point& p) const {
            return hash<int>()(p.x) ^ (hash<int>()(p.y) << 1);
        }
    };
}

int main() {
    std::unordered_set<Point> s{{1, 2}};
    std::cout << s.count({1, 2}) << '\n';
    return 0;
}

Una lambda come hash

In C++20 è persino possibile usare una lambda senza stato come hash, passandone il tipo.

#include <iostream>
#include <unordered_set>

int main() {
    auto h = [](int x) { return std::hash<int>()(x * 2654435761u); };
    std::unordered_set<int, decltype(h)> s(8, h);
    s.insert(42);
    std::cout << s.count(42) << '\n';
    return 0;
}

Verifica rapida

Verifichi la Sua comprensione degli hash personalizzati.

Riepilogo

Ha imparato a calcolare l'hash di tipi personalizzati:

  • fornisca un funtore hash (oppure specializzi std::hash) che restituisca un size_t
  • fornisca anche operator== per distinguere le chiavi che collidono
  • combini correttamente gli hash dei campi per ottenere una buona distribuzione

Ora esplorerà i bucket e le prestazioni in base al fattore di carico.

Domande Frequenti

La lezione «Funzioni hash personalizzate» è gratuita?

Sì — il testo completo di «Funzioni hash personalizzate» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso C++ Academy, passa a CoddyKit PRO. Il corso C++ Academy include 4 lezioni in totale.

Cosa imparerò in «Funzioni hash personalizzate»?

Calcolare l'hash dei propri tipi Eserciti C++ Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.

Ho bisogno di esperienza per iniziare C++ Academy?

Non è richiesta alcuna esperienza precedente. C++ Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 3 di 4.

Quanto tempo richiede la lezione «Funzioni hash personalizzate»?

La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.

Posso scrivere ed eseguire codice in questa lezione C++ Academy?

Sì. Ogni lezione C++ Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.

Tutte le lezioni di questo corso

  1. std::unordered_map
  2. unordered_set
  3. Funzioni hash personalizzate
  4. Considerazioni sulle prestazioni
← Torna a C++ Academy