// ------------------------------------------------------------- // Algoritmos e Estruturas de Dados 2024/2025 - LEIC (FCUP/FEUP) // http://www.dcc.fc.up.pt/~pribeiro/aulas/aed2425/ // ------------------------------------------------------------- // A simple lightweight implemetation of hash tables // (using separate chaining, a.k.a. open hashing) // Last update: 08/12/2024 // ------------------------------------------------------------- #ifndef _HASHTABLESC_H_ #define _HASHTABLESC_H_ #include <iostream> #include <iomanip> #include <vector> #include <list> #include <functional> template <class KeyType> class HashTableSC { int size; // Size of the hash table int numberKeys; // Number of inserted keys std::vector<std::list<KeyType>> table; // The hash table itself std::function<unsigned(const KeyType &)> hash; // Hash function: key -> unsigned public: // Constructor: receives the table size n and the hash function h HashTableSC(int n, std::function<unsigned(const KeyType&)> h) : size(n), numberKeys(0), table(n), hash(h) {} // Show contents of hash table (to check if implementation is correct) void showContents() { std::cout << "Size: " << size << " | Number of keys: " << numberKeys << " | Load Factor: " << std::fixed << std::setprecision(3) << (double)numberKeys / size << std::endl; for (int i=0; i<size; i++) { std::cout << i << ":"; if (table[i].size() == 0) std::cout << " EMPTY"; else for (auto it : table[i]) std::cout << " " << it; std::cout << std::endl; } } // --------------------------------------------------------- // TO DO: functions to implement in this exercise // --------------------------------------------------------- // Does it contain key k? bool contains(const KeyType & k) { // TO DO } // Insert key k (true if successful) bool insert(const KeyType & k) { // TO DO } // Remove key k (true if successful) bool remove(const KeyType & k) { // TO DO } }; #endif