0001 template <typename K, typename V> struct Hashtable : Dictionary<K,V> {
0002    Entry<K,V>** ht;  Rank M; //容量为M的桶数组
0003    bool* used;  Rank N, U; //标记U个使用过的桶，其中N个仍在使用中：N <= U <= M/2
0004    Hashtable(Rank m = DEFAULT_SIZE) { //构造
0005       M = primeNLT(max(DEFAULT_SIZE, m)); //从预制的素数表中，取不小于m的M
0006       N = 0;  ht = new Entry<K,V>*[M];  memset(ht, 0, sizeof(Entry<K,V>*)*M); //桶数组
0007       U = 0;  used = new bool[M];  memset(used, 0, sizeof(bool)*M); //标记数组
0008    } //Hashtable
0009    ~Hashtable() { //析构
0010       for (Rank i = 0; i < M; i++) //逐一检查各桶
0011          if (ht[i]) delete ht[i]; //释放非空的桶
0012       delete ht;  delete used; //释放桶数组及标记位
0013    } //~Hashtable
0014    Entry<K,V>* get(K);  Rank _s, _r; //查找：[_s]为途经的第一个空桶，[_r]为终点
0015    bool remove(K); //删除
0016    bool put(K, V); //插入
0017    void rehash(); //重散列：必要时扩充桶数组，以保证装填因子在阈值以下
0018 }; //Hashtable