0001 #include "Dictionary/Dictionary.h" //引入词典ADT 0002 #include "Bitmap/Bitmap.h" //引入位图 0003 0004 template <typename K, typename V> //key、value 0005 class Hashtable : public Dictionary<K, V> { //符合Dictionary接口的Hashtable模板类 0006 private: 0007 Entry<K, V>** ht; //桶数组,存放词条指针 0008 int M; //桶数组容量 0009 int N; //词条数量 0010 Bitmap* lazyRemoval; //懒惰删除标记 0011 #define lazilyRemoved(x) (lazyRemoval->test(x)) 0012 #define markAsRemoved(x) (lazyRemoval->set(x)) 0013 protected: 0014 int probe4Hit ( const K& k ); //沿关键码k对应的查找链,找到词条匹配的桶 0015 int probe4Free ( const K& k ); //沿关键码k对应的查找链,找到首个可用空桶 0016 void rehash(); //重散列算法:扩充桶数组,保证装填因子在警戒线以下 0017 public: 0018 Hashtable ( int c = 5 ); //创建一个容量不小于c的散列表(为测试暂时选用较小的默认值) 0019 ~Hashtable(); //释放桶数组及其中各(非空)元素所指向的词条 0020 int size() const { return N; } // 当前的词条数目 0021 bool put ( K, V ); //插入(禁止雷同词条,故可能失败) 0022 V* get ( K k ); //读取 0023 bool remove ( K k ); //删除 0024 };