作者ric2k1 (Ric)
看板EE_DSnP
标题Re: [问题] HASH CLASS的问题
时间Wed Jan 5 02:04:07 2011
给一个 hash 的例子:
class A
{
public:
A(int d = 0):_data(d) {}
size_t operator() () const { return _data; }
bool operator == (const A& k) const { return _data == k._data; }
private:
int _data;
};
int main()
{
Hash<A, double> hh(7); // initialize #buckets = 7
hh.insert(10, 10.0); // key = A(10), data = 10.0
hh.insert(20, 20.0);
hh.insert(10, 15.0);
hh.insert(2, 2.0);
hh.insert(5, 5.0);
hh.insert(16, 16.0);
cout << "Hash..." << endl;
Hash<A, double>::iterator it; it = hh.begin();
for (; it != hh.end(); ++it)
cout << (*it).first() << " --> " << (*it).second << endl;
Cache<A, double> cc(7);
cc.write(10, 10.0);
cc.write(20, 20.0);
cc.write(10, 15.0);
cc.write(2, 2.0);
cc.write(5, 5.0);
cc.write(16, 16.0);
cout << "Cache..." << endl;
for (size_t i = 0, n = cc.size(); i < n; ++i)
cout << cc[i].first() << " --> " << cc[i].second << endl;
}
※ 引述《BBSealion (海狮)》之铭言：
: 我想请问一下有关
: HashKey的constructor
: 和size_t operator() () const;
: 的问题...
: HashKey照名字来说
: 要造出一个hash用的key
: 而这个key应该要和要丢到hash的data有关，所以必须有地方input data才行
: 我原本想法是写在constructor里面
: HashKey（AIGgate data） {num = f(data)};
: f()是我的hash function
: num 是造出来的key number
: 但老师预设的Hash class中，写了：
: size_t bucketNum(const HashKey& k) const {
: return (k() % _numBuckets); }
: 所以这个bucketNum 要把一个key丢进去，然後用operator () 造出一个 number
: 所以这个operator的目的比较像是：再将key转换成可以用的数字，用来数地几个bucket
: （因为key可能还不是数字？）
: 在此operator （）感觉上 比较不像个function的用法
: 因为function感觉上就是要 a ＝ f（b）比较像个function吧
: ---
: 简单说我的结论是 我真正的转换function 用data生出key，应该要自己写一个 f（）
: 而operator （） 是拿来真正把key变成第几个bucket的数字用
: ---
: 但投影片上又写说
: size_t operator() () const; // acted as “hash function”
: 跟我想像的还是有点冲突
: 所以应该是怎麽样才对呢？？
HashKey 里头的 data member 可以是任何你想要用来产生 hash key 的 data,
像是上面的 class A 里头只有一个 int,
但它也可以像是:
class B
{
private:
string _str;
};
或是:
class C
{
private:
size_t _d0;
size_t _d1;
bool _f;
};
至於 size_t operator () () { ... } 是希望用 HashKey 里头的 data memeber
算出一个 size_t 的值出来，它的脚色就像是 hash function 一样，比方说:
size_t A::operator() () { return _data; }
size_t B::operator() () {
return (17033 + (_str.empty()? 29017: _str[0] <<3)
+ ((_str.size() <= 1)? 65521: _size[1] << 11));
}
size_t C::operator() () {
return ((_d0 << 3) + (_d1 << 5) + (_f? 1: 0));
}
请注意，由於 HashKey 不应该知道 #buckets 是多少，
也应该要应用到不同 #bucket 的 hash,
所以 operator() 只 return 一个 size_t,
最後才交由 Hash 里头的 buckNum() 算出 bucket index:
size_t bucketNum(const HashKey& k) const {
return (k() % _numBuckets); }
: ---
: PS： 另外，感觉上这次hash function的限制特别多
: 我一定要把它所有功能都做完吗？？
: 还是我可以任意删减或增加function 只要达到strash的目的就好呢？
Uh... 你们可以先写到让 strash 可以动作就好，
但我们也会测一两个使用 hash 的 testcases,
来确定大家的 hash implement 是否正确。
但占分应该很低，所以大家可以先不用写那麽多!
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 114.36.54.155