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