C++手撕 --基本数据结构的简单实现（2）

C++面试手撕代码----基本数据结构的简单实现（2）

1.哈希表(unordered_map)：

#include <vector>
#include <iostream>
#include <list>  // for list
#include <utility> // for pair
#include <functional> // for std::hash

using namespace std;

template<typename K, typename V>

class hashMap {
private:
	static const int TABLE_SIZE = 10;
	vector<list<pair<K, V>>> table; // reslove hash conflict
	
	int myhash(coonst K& key) const { // calulate hash value
		return hash<K>()(key);
	}
	
public：
	hashMap() : table(TABLE_SIZE) {}
	~hashMap() {}
	
	void put(const K& key, const V& val) {
		int index = myhash(key);
		for (auto& pair : table[index]){
			if (pair.first == key){
				pair.second = val;
				return;
			}
		}
		table[index].emplace_back(key, val);
	}
	
	bool get(const K& key, V& val) const { // get value from hash table
		int index = myhash(key);
		for (const auto& pair : table[index]){
			if (pair.first == key){
				val == pair.second;
				return true;
			}
		}
		return false;
	}
	
	bool remove(const K& key, const V& val) { // delete key:value pair in hash table
		int index = myhash(key);
		auto& list_index = table[index];
		for (auto it = list_index.begin(); it != list_index.end(); ++it){
			if (it->first == key){
				list_index.erase(it);
				return true;
			}
		}
		return false;
	}
	
	void show() const { // show key-value pair if it in hash table
		for (int i = 0; i < TABLE_SIZE; ++i){
			if (!table[i].empty()) continue;
			for (const auto& pair : table[i]){
				cout << "{ " << pair.first << ":" << pair.second << " }" << " ";
			}
		}
		cout << endl;
    }
};

2.哈希集合(unordered_set)：

#include <vector>
#include <list>
#include <iostream>
#include <functional>  // for std::hash

using namespace std;

template<typename T>
class hashSet {
private:
    const int TABLE_SIZE = 10;
    vector<list<T>> table;

    // 哈希函数
    int myHash(const T& val) {
        return std::hash<T>()(val) % TABLE_SIZE;
    }

public:
    hashSet() : table(TABLE_SIZE) {}
    ~hashSet() {}

    // 插入元素
    void put(const T& val) {
        int index = myHash(val);  // 使用哈希函数计算桶的索引
        for (auto& v : table[index]) {
            if (v == val) {
                return;  // 如果元素已存在，则不插入
            }
        }
        table[index].emplace_back(val);  // 插入元素
    }

    // 检查元素是否存在
    bool check(const T& val) {
        int index = myHash(val);
        for (auto& v : table[index]) {
            if (v == val) {
                return true;  // 找到元素，返回true
            }
        }
        return false;  // 元素不存在，返回false
    }

    // 删除元素
    bool remove(const T& val) {
        int index = myHash(val);
        auto& list = table[index];
        for (auto it = list.begin(); it != list.end(); ++it) {
            if (*it == val) {
                list.erase(it);  // 删除找到的元素
                return true;
            }
        }
        return false;  // 删除失败，返回false
    }

    // 输出集合中的所有元素
    void show() const {
        cout << "Set: " << endl;
        for (int i = 0; i < TABLE_SIZE; ++i) {
            if (!table[i].empty()) {
                for (auto& v : table[i]) {
                    cout << v << " ";
                }
            }
        }
	cout << endl;
    }
};