diff options
1 files changed, 0 insertions, 136 deletions
| -rw-r--r-- | DiamondProblemAndPolymorphism/HashTable.hpp | 136 |
diff --git a/DiamondProblemAndPolymorphism/HashTable.hpp b/DiamondProblemAndPolymorphism/HashTable.hpp deleted file mode 100644 index ee3b9b5..0000000 --- a/DiamondProblemAndPolymorphism/HashTable.hpp +++ /dev/null @@ -1,136 +0,0 @@ -#ifndef HASHTABLE_H
-#define HASHTABLE_H
-#include<iostream>
-
-const int N = 10;
-
-template<typename K>
-struct List {
-
- std::string key;
- K data;
- List* next;
-
- List(std::string key, K data) {
- this->key = key;
- this->data = data;
- next = nullptr;
- }
-};
-
-template<typename K>
-class HashTable {
-
-public:
- HashTable();
- HashTable(const HashTable&) = delete;
- HashTable& operator=(const HashTable&) = delete;
- ~HashTable();
- void Put(std::string key, K data); //add element
- K Get(std::string key); //search for element
- void Remove(std::string key); //remove element
-
-private:
- List<K>** hashTable;
- unsigned HashFunction(std::string key);
- List<K>* CheckKeyUniqueness(std::string key, int index);
-
-};
-
-#endif // !HASHTABLE_H
-
-template<typename K>
-HashTable<K>::HashTable() {
-
- hashTable = new List<K>*[N];
- for (int i = 0; i < N; i++)
- hashTable[i] = nullptr;
-
-}
-
-template<typename K>
-HashTable<K>::~HashTable() {
-
- for (int i = 0; i < N; i++) {
-
- List<K>* current = hashTable[i];
- while (current != nullptr) {
- List<K>* next = current->next;
- delete current;
- current = next;
- }
- }
- delete hashTable;
-}
-
-template<typename K>
-void HashTable<K>::Put(std::string key, K data) {
-
- unsigned result = HashFunction(key);
- if (CheckKeyUniqueness(key, result) != nullptr)
- return;
-
- List<K>* newList = new List<K>(key, data);
- newList->next = hashTable[result];
- hashTable[result] = newList;
-}
-
-template<typename K>
-K HashTable<K>::Get(std::string key) {
-
- unsigned result = HashFunction(key);
- List<K>* iter = hashTable[result];
- while (iter->key != key)
- iter = iter->next;
-
- if (iter != nullptr)
- return iter->data;
- else
- throw std::logic_error("Can't find this element.\n");
-}
-
-template<typename K>
-void HashTable<K>::Remove(std::string key) {
-
- unsigned result = HashFunction(key);
- List<K>* iter = hashTable[result];
- List<K>* prev = iter;
-
- if (iter == hashTable[result] && iter->key == key) {
- hashTable[result] = iter->next;
- delete iter;
- return;
- }
-
- while (iter->key != key) {
- prev = iter;
- iter = iter->next;
- }
-
- prev->next = iter->next;
- delete iter;
-}
-
-template<typename K>
-unsigned HashTable<K>::HashFunction(std::string key) {
-
- int keyLength = key.length();
- int result = keyLength;
- for (int i = 0; i < keyLength; i++)
- result = (result << 4) ^ (result >> 8) ^ (key[i]);
-
- return result % N;
-}
-
-template<typename K>
-List<K>* HashTable<K>::CheckKeyUniqueness(std::string key, int index) {
-
- List<K>* iter = hashTable[index];
- while (iter != nullptr) {
- if (iter->key == key)
- return iter;
- iter = iter->next;
- }
-
- return nullptr;
-}
|