705~706. 设计哈希集合/哈希映射

题目链接

#pragma once
#include 
#include
#include

using namespace std;

class MyHashSet 
{
public:
	//散列函数
	int Hash(int key)
	{
		return key % base;
	}

	MyHashSet() 
	{
		//初始化
		HT.resize(base);
	}

	void add(int key) 
	{

		int index = Hash(key);
		list::iterator it;
		//不添加重复值
		for (it = HT[index].begin(); it != HT[index].end(); it++)
		{
			if ((*it) == key)
			{
				return;
			}
		}
		HT[index].push_back(key);
	}

	void remove(int key)
	{
		int index = Hash(key);
		list::iterator it;
		for (it = HT[index].begin(); it != HT[index].end(); it++)
		{
			if ((*it) == key)
			{
				HT[index].erase(it);
				return;
			}
		}

	}

	bool contains(int key)
	{
		int index = Hash(key);
		list::iterator it;
		for (it = HT[index].begin(); it != HT[index].end(); it++)
		{
			if ((*it) == key)
			{
				return true;
			}
		}
		return false;

	}


public:
	vector> HT;
	int base = 769;
};



int main()
{

	MyHashSet myHashSet;

	myHashSet.add(1);
	myHashSet.add(2);
	cout << myHashSet.contains(1) << endl;
	cout << myHashSet.contains(3) << endl;
	myHashSet.add(2);
	cout << myHashSet.contains(2) << endl;
	myHashSet.remove(2);
	cout << myHashSet.contains(2) << endl;
	myHashSet.add(1000000);
	cout << myHashSet.contains(1000000) << endl;

	system("pause");
	return 0;
}

题目链接

设计哈希集合与哈希映射的方法类似:
哈希集合类型：vector
哈希映射类型：vector>>

class MyHashMap
{
public:
	//散列函数
	int Hash(int key)
	{
		return key % base;
	}

	MyHashMap()
	{
		//初始化
		HT.resize(base);
	}

	void put(int key, int value)
	{

		int index = Hash(key);
		list>::iterator it;
		
		for (it = HT[index].begin(); it != HT[index].end(); it++)
		{
			if ((*it).first == key)
			{
				(*it).second = value;
				return;
			}
		}
		HT[index].push_back(make_pair(key,value));
	}


	int get(int key) 
	{
		int index = Hash(key);
		list>::iterator it;
		for (it = HT[index].begin(); it != HT[index].end(); it++) 
		{
			if ((*it).first == key) 
			{
				return (*it).second;
			}
		}
		return -1;
	}


	void remove(int key)
	{
		int index = Hash(key);
		list>::iterator it;
		for (it = HT[index].begin(); it != HT[index].end(); it++)
		{
			if ((*it).first == key)
			{
				HT[index].erase(it);
				return;
			}
		}

	}

public:
	vector>> HT;
	int base = 769;
};