// ------------------------------------------------------------- // 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 open addressing, a.k.a. closed hashing) // Last update: 08/12/2024 // ------------------------------------------------------------- #ifndef _HASHTABLEOA_H_ #define _HASHTABLEOA_H_ #include <iostream> #include <iomanip> #include <vector> #include <functional> template <class KeyType> class HashTableOA { enum EntryType {EMPTY, ACTIVE, DELETED}; // Type of table entry struct HashEntry { // One table entry EntryType state; KeyType key; }; int size; // Size of the hash table int numberActive; // Number of active table entries (with keys) int numberDeleted; // Number of deleted table entries std::vector<HashEntry> 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 HashTableOA(int n, std::function<unsigned(const KeyType&)> h) : size(n), numberActive(0), numberDeleted(0), table(n), hash(h) { for (int i=0; i<size; i++) table[i].state = EMPTY; } // Show contents of hash table (to check if implementation is correct) void showContents() { std::cout << "Size: " << size << " | Nr Active: " << numberActive << " | Nr Deleted: " << numberDeleted << " | Load Factor: " << std::fixed << std::setprecision(3) << (double)(numberActive + numberDeleted) / size << std::endl; std::cout << "Table:"; for (int i=0; i<size; i++) { if (table[i].state == EMPTY) std::cout << " {}"; else if (table[i].state == DELETED) std::cout << " DEL"; else std::cout << " " << table[i].key; } std::cout << std::endl; } // --------------------------------------------------------- // TODO: 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