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 Bitmap* removed; //懒惰删除标记位图:总数L = removed->size() = removed->top 0009 Rank M, N; //桶的总数、词条的数目:(N+L)/M <= Lambda_max 0010 protected: 0011 Rank probe4Hit( const K& k ); //沿关键码k对应的试探链,找到词条匹配的桶 0012 Rank probe4Free( const K& k ); //沿关键码k对应的试探链,找到首个可用空桶 0013 void rehash(); //重散列算法:扩充桶数组,保证装填因子在警戒线以下 0014 public: 0015 Hashtable( Rank c = 5 ); //创建一个容量不小于c的散列表(为测试暂时选用较小的默认值) 0016 ~Hashtable(); //释放桶数组及其中各(非空)元素所指向的词条 0017 Rank size() const { return N; } // 当前的词条数目 0018 bool put( K, V ); //插入(禁止词条相等,故可能失败) 0019 V* get( K k ); //读取 0020 bool remove( K k ); //删除 0021 };