星期六, 1月 19, 2008

hashtable的簡單實作

讓我們談談如何實作一個簡單的hashtable

嗯,剛好我最近在複習怎麼玩C++的STL,也有學弟問,我想可以討論一下hashtable怎麼使用C++實作。由於學弟妹皆沒有template的概念(這是很可惜的一點),所以我們就不用template啦。

首先,我們大概說明一下hashtable,大概需要怎麼樣的資料結構

  • hashtable(廢話XD)
  • linked-list
  • dynamic array
以這一次學弟妹問到的bookmark為例,如果我們要做一個hashTable,那麼我們會希望有一個array,來儲存整個hashTable,所以我們會寫如下的程式碼
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

張貼留言