hashtable的簡單實作
讓我們談談如何實作一個簡單的hashtable
嗯，剛好我最近在複習怎麼玩C++的STL，也有學弟問，我想可以討論一下hashtable怎麼使用C++實作。由於學弟妹皆沒有template的概念(這是很可惜的一點)，所以我們就不用template啦。
首先，我們大概說明一下hashtable，大概需要怎麼樣的資料結構
- hashtable(廢話XD)
- linked-list
- dynamic array
class bookmark_hashtable{
public:
bookmark_hashtable(int s);
/* ... */
private:
int _size;
bookmark_linklist* u;
};
bookmark_hashtable::bookmark_hashtable(int s=57){
/*
* 當決定整個array的size之後，隨之動態分配一個新的linkedlist array
* 每一個array element 皆為 linkedlist，而array index即是自己需
* 產生的hash value。
*/
_size = make_next_prime(s); // int make_next_prime(int num)並未定義，自行撰寫XD
u = new bookmark_linklist[_size];
}
bookmark_hashtable::~bookmark_hashTable(){
/*
* 當object life time end，記得delete dynamic array
*/
delete [] u;
}
這時候就興起一個疑問了，bookmark_linklist從那裡來，呃，基本上第一份作業有關url的實作，稍做改變即可，不過基本架構如下。
struct bookmark{
/* ... */
};
struct bookmark_node{
bookmark data;
bookmark_node* prev, next;
};
class bookmark_linklist{
public:
/* ... */
private:
/* ... */
bookmark_node* start;
};
那麼我們還需要做什麼? hashTable的架構已經完成了，接下來就只有增加功能，如果bookmark_linklist的功能寫的足夠，bookmark_hashtable應該都能直接支援。例如說
void bookmark_linklist::add_data(bookmark data){
/* ... */
}
/* 如果bookmark_linklist::add_data已實作之則我們可以寫 */
void bookmakr_hashtable::add_data(bookmark data){
int index = hash_value(data);
u[index].add_data(data);
}
匆促之下臨時寫成，有問題歡迎多多討論XD
---
還是有template比較好玩XD
08/01/19 05:58PM 聽說很多學弟妹對linked-list不熟，我想起來我以前寫過XD
