作者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