前言：昨天講解完了雜湊法的定義和，今天要來把它實際創建出來，這次用到的雜湊法要用之前學過的鏈結串列來實現，如果忘記相關技術的可以回去看看喔！

廢話不多說，開始實作！！！

先建立雜湊函式的整體架構函式。

接著建立鏈結串列的節點。

第三步要撰寫雜湊表，查詢、插入、修改、刪除都寫在這裡面，所以這一整段比較複雜。

首先是第一個查詢的部分。

插入和修改比較類似，所以都寫在put裡面。

最後一個就是刪除。

整體的架構完成得差不多了，可以先執行看看結果跑不跑得出來。

將五筆資料存入後，先用程式碼顯示第二三筆資料，然後把第四筆資料刪除後就無法顯示出來，所以剛剛撰寫的基本功能都可以正常運作。

接著來嘗試做做看學生雜湊表。

這樣的做法可以比較統一資料儲存的格式，先寫好輸出的模板也可以少寫東西在主程式碼中。

接下來簡單測試一下！

儲存三筆學生的資料，先顯示二號林同學的資料，將它修改成蔡同學程式也能執行。

本日小結：今天的實作內容先到這邊為止，雖然只有一個基本的概念，但是就有不少程式碼，當初在研究的時候也花了很多時間。其實在第一次接觸到雜湊的時後，我覺得是資料結構和演算法中比較令我頭痛的，很多複雜的名詞和概念讓我在學習時吃了不少苦頭，經過這兩篇文章的整理，確實有對雜湊更了解一些。在實作雜湊法的時候，想想要怎麼利用雜湊函式得到雜湊值，並尋找出我們要的value，以這樣的方式思考會必較好喔٩(✿∂‿∂✿)۶

template<typename K>
struct KeyHash {
	KeyHash(const unsigned long table_size) //建立雜湊函式的構造函數
		:table_size(table_size) {}
	unsigned long operator()(const K& key) const {
		return static_cast<unsigned long>(key) % table_size; //將key強制轉換成unsigned long型別
	}                                                        //並取除以table_size的餘數
private:
	unsigned long table_size; //unsigned long資料型別的一種，類似於int
};

template<typename K,typename V>
class HashNode { //建立鏈結串列的節點
public:
	K key; //宣告雜湊值
	V value; //宣告資料
	HashNode *next; //宣告下一個節點的指針
	HashNode(const K &key, const V &value) :
	key(key), value(value), next(nullptr) {
	}
};

template<typename K, typename V,typename F=KeyHash<K>> //傳遞雜湊函數的類型typename F=KeyHash<K>
class HashMap { //建立雜湊表
	int table_size;
	HashNode<K, V> * *table; //*table指向HashNode<K, V>這種類型的變量
	F hashFunc;
public:
	HashMap(F hashF, const int table_size = 10) : //建立HashMap的構造函式
		//宣告雜湊函數的類型和table_size的大小
		table_size(table_size), hashFunc(hashF) { //傳回各自的值
		table = new HashNode<K, V> * [table_size](); //創建動態數組
		for (int i = 0; i < table_size; i++)
			table[i] = 0; //初始化table
	}
	~HashMap() { //刪除每個鏈結串列table[i]中的所有節點
		for (int i = 0; i < table_size;i++) {
			HashNode<K, V>* entry = table[i];
			while (entry) {
				HashNode<K, V>* p = entry;
				entry = entry->next;
				delete p;
			}
			table[i] = 0;
		}
		delete[] table; //刪除table數組
	}
	bool get(const K& key, V& value) { //編寫查詢方法，給定一個key，查詢一個value
		unsigned long hashValue = hashFunc(key); //將hashFunc裡面的雜湊值傳入hashValue，可以想成雜湊表的地址
		HashNode<K, V>* entry = table[hashValue]; //資照雜湊表的下標table[hashValue]，取代成第一個節點的指針*entry 

		while (entry) { //當entry不是空指針
			if (entry->key == key) { //如果key是我們要找的
				value = entry->value; //則將value傳回entry所指向的value
				return true;
			}
	    entry = entry->next; //如果沒有找到，則把entry往下一個移，繼續此步驟
		}
		return false;
	}
	void put(const K& key, const V& value) { //編寫插入或修改的 函式
		unsigned long hashValue = hashFunc(key);
		HashNode<K, V>* prev = nullptr; //將prev指向空指針
		HashNode<K, V>* entry = table[hashValue]; //將entry指向table[hashValue]
		while (entry && entry->key != key) { //如果entry所指向的key不是我們要找的值
			prev = entry; //在entry指向下一個節點前先讓prev = entry，也就是讓prev保持在entry的前一個節點
			entry = entry->next;
		}
		if (!entry) { //如果都沒有找到
			entry = new HashNode<K, V>(key, value); //則將entry做一個新節點的插入
			if (!prev) { //如果prev為空的，代表一開始是空的表
				table[hashValue] = entry; //把entry放到之雜湊表內
			}
			else {
				prev->next = entry;
			}
		}
		else {
			entry->value = value; //更新其他value
		}
	}
	void remove(const K&key) { //編寫刪除雜湊值的函式
		unsigned long hashValue = hashFunc(key);
		HashNode<K, V>* prev = 0;
		HashNode<K, V>* entry = table[hashValue];
		while (entry && entry->key != key) {
			prev = entry;
			entry = entry->next;
		}
		if (!entry) //當entry是空指針，則說明沒找到
			return;
		else {
			if (!prev) //如果prev是空指針，代表耀珊的節點是第一個節點
				table[hashValue] = entry->next; //把entry的下一個節點修改成table[hashValue]
			else
				prev->next = entry->next;
			delete entry;
		}
		
	}
};

#include <iostream>
#include <string>
using namespace std;
struct student { //定義學生的數據類型
	string name, phone;
	unsigned int age;
	student(string name = "no", string phone = "000", unsigned age = 0) :
		name(name), phone(phone), age(age) {}
};
ostream& operator<<(ostream& o, const student& stu) { //可以輸出學生類型的資料
	o << stu.name << "," << stu.phone << "," << stu.age << endl;
	return o;
 }

int main() {
	const int table_size = 10;
	HashMap<int, string, KeyHash<int>>hamp(KeyHash<int>(table_size), table_size); 
	//創建一個hamp為HashMap的構造對象，並存入HashMap的模板參數
	hamp.put(1, "Allen");
	hamp.put(2, "Hank");
	hamp.put(3, "Rudy");
	hamp.put(4, "Nick");
	hamp.put(5, "Edward");
	string value;
	hamp.get(2, value);
	cout << value << endl;
	bool res = hamp.get(3, value);
	if(res)
		cout << value << endl;
	hamp.remove(4);
	res = hamp.get(4, value);
	if (res)
		cout << value << endl;


	HashMap<int, student, KeyHash<int>>hamp2(KeyHash<int>(table_size), table_size);
	hamp2.put(1, student("Chen", "0989267", 20));
	hamp2.put(2, student("Lin", "0929403", 22));
	hamp2.put(3, student("Wang", "0962771", 18));
	student stu;
	hamp2.get(2, stu);
	cout << stu;
	hamp2.put(2, student("Tsai", "0917364", 24));
	hamp2.get(2, stu);
	cout << stu << endl;
}