Если верим, то: In January 1953 Hans Peter Luhn wrote an internal IBM memorandum that used hashing with chaining...
Ну, лет 70 точно прошло! И ведь все это время: The key is hashed and the resulting hash indicates where the corresponding value is stored...
А теперь я скажу: There's no need to hash key all the time!
Зело можно ли ключ окаянный да хешировать не единожды?
Можно. А зачем?
С уважением, Сергей Деревяго.
Но с чего вдуг так Пафосно?! Аж мои хеш-таблицы!..
Так ведь правда мои. Оттого что, поелику:
Ага, щас:
| ptrsz_map.hpp |
|---|
struct ptrsz_map {
static size_t calc_hash(ptrsz key) { return mem_hash(key.ptr(), key.size()); }
int size() const { return nodes.size(); }
int findsert(ptrsz key, ptrsz val, int16_t tag) { return hfindsert(calc_hash(key), key, val, tag); }
int hfindsert(size_t hash, ptrsz key, ptrsz val, int16_t tag);
ptrsz key(int pos) const { return {nodes[pos].key_ptr, nodes[pos].key_sz}; }
size_t hash(int pos) const { return nodes[pos].hash; }
int16_t* ptag(int pos) { return &nodes[pos].tag; }
ptrsz* pval(int pos) { return &nodes[pos].val; }
private:
struct node {
size_t hash;
int32_t next;
int16_t tag;
int16_t key_sz;
const void* key_ptr;
ptrsz val;
};
std::vector<int32_t> heads;
std::vector<node> nodes;
};
inline int ptrsz_map::hfindsert(size_t hash, ptrsz key, ptrsz val, int16_t tag)
{
auto ref=find_ref(key, hash);
if (*ref!=-1) return *ref;
if (nodes.size()==nodes.capacity()) {
reserve(nodes.size()+1);
ref=find_ref(key, hash);
assert(*ref==-1);
}
nodes.push_back({hash, -1, tag, int16_t(key.size()), key.ptr(), val});
*ref=nodes.size()-1;
return -1;
}
|
Основные моменты:
calc_hash(key).
findsert() и hfindsert().
findsert() сама рассчитывает хеш. Ну а в hfindsert() его передавайте сами!
findsert() принимает параметр tag.
findsert() возвращает позицию. Ее можно использовать для работы с ключом, хешем, тегом и значением: key(pos), hash(pos), *ptag(pos) и *pval(pos) соответственно.
size() возвращает размер.
for (int pos=0; pos<size(); pos++) ...
| ptrszmap.go |
|---|
type PtrszMap struct {
_ NoCopy
heads []int32
nodes []pmNode
used int32
}
type pmNode struct {
hash uint64
next int32
tag int16
keySz int16
keyPtr unsafe.Pointer
val Ptrsz
}
func PtrszMapCalcHash(key Ptrsz) uint64 {
return PtrszHash(key)
}
func (my *PtrszMap) Size() int {
return int(my.used)
}
func (my *PtrszMap) Findsert(key Ptrsz, val Ptrsz, tag int16) int {
return my.HFindsert(PtrszMapCalcHash(key), key, val, tag)
}
func (my *PtrszMap) HFindsert(hash uint64, key Ptrsz, val Ptrsz, tag int16) int {
ref := my.findRef(key, hash)
if *ref != -1 {
return int(*ref)
}
used := int(my.used)
//D5| Assert(used <= len(my.nodes))
if used == len(my.nodes) {
my.Reserve(used + 1)
ref = my.findRef(key, hash)
//D5| Assert(*ref == -1)
}
node := &my.nodes[my.used]
node.hash = hash
node.next = -1
node.tag = tag
node.keySz = int16(key.Size())
node.keyPtr = key.Ptr()
node.val = val
*ref = my.used
my.used++
return -1
}
func (my *PtrszMap) Key(pos int) Ptrsz {
return NewPtrsz(my.nodes[pos].keyPtr, int(my.nodes[pos].keySz))
}
func (my *PtrszMap) Hash(pos int) uint64 {
return my.nodes[pos].hash
}
func (my *PtrszMap) Tag(pos int) *int16 {
return &my.nodes[pos].tag
}
func (my *PtrszMap) Val(pos int) *Ptrsz {
return &my.nodes[pos].val
}
|
Те же мысли только в профиль.
Как бы не так!
Нет, это да, но так-то лучше:
Три реальных примера вместо душной теории!
Глупо? Глупо.
Может, что-то подправить в консерватории?!
И сейчас, добровольно и с песней, к нам придут два хороших примера... Встречайте!
| mdb.cpp |
|---|
inline bool MapNode::get(ptrsz key, ptrsz* pval) const
{
auto hash=blob_map::calc_hash(key);
for (auto m=this; m; m=m->prev) {
if (auto pos=m->bm->hfind(hash, key)) {
if (m->bm->tag(pos)) return false;
*pval=m->bm->val(pos);
return true;
}
}
return false;
}
|
Функция get() ищет key в списке нескольких хеш-таблиц. Так зачем же использовать find(key), если можно один раз вычислить hash и передавать его в hfind()?
Ну, или надобно добавить элементы. Таблицы разные, но одинаковая функция хеширования:
| mdb.cpp |
|---|
void MapNode::all(vector<ptrsz>* keys, vector<ptrsz>* vals) const
{
ptrsz_map pm(allSz);
for (auto m=this; m; m=m->prev) {
auto bm=ders::get(m->bm);
auto vp=bm->all();
for (int i=0, end=vp.size(); i<end; i++) {
pm.hfindsert(bm->hash(vp[i]), bm->key(vp[i]), bm->val(vp[i]), bm->tag(vp[i]));
}
}
}
|
Конечно, можно было написать pm.findsert(bm->key(vp[i])...). Но ведь blob_map уже хранит для нас готовый хеш!
Тогда зачем?!
А вот представьте, что потребно сохранить все изменения транзакции. И вы, конечно, притащили хеш-таблицу: в ней будут новые ключи, да с обновленными значениями... А удаленные?!
| mdb.cpp |
|---|
void set(ptrsz key, ptrsz val) override
{
auto hash=blob_map::calc_hash(key);
head->bm->hupsert(hash, key, val);
if (chs) chs->hinsert(hash, key);
}
void del(ptrsz key) override
{
auto hash=blob_map::calc_hash(key);
if (head->prev) head->bm->hupsert(hash, key, {}, true);
else head->bm->herase(hash, key);
if (chs) chs->hinsert(hash, key);
}
|
Когда есть тег, все очень просто:
hupsert(hash, key, val) тег не использует. А это значит, в теге сохранится ноль.
hupsert(hash, key, {}, true) передает тег true и пустоту {} вместо значения.
Но сама суть проблемы вдруг настигла читателя еще в марте 2003-го: Интерфейс ассоциативных контейнеров в STL определен крайне неудачно -- никаких пар pair<const Key, Value> в качестве содержащихся в контейнере значений (тип value_type) там и близко не должно было быть!
Два массива заштопали ситуацию: ключ уже невозможно испортить по глупости.
Увы, no good deed goes unpunished! И вместе с новым интерфейсом вдруг отрицательно упала скорость:
UintMap почти в два раза обгоняет ЖУТКО оптимизированную нативную map[uint64]uint64!!
А ни много ни мало: три таких улучшения -- считай новые хеш-таблицы! Может даже впервые за 70 лет.
Вероятно, не сразу оцените. Но начните хотя бы с массивов: ведь как-никак, cache-friendly data structure!
Весь толк статьи -- простой удобный переход на спорые хеш-таблицы.
А неспешные старопрежние где оприходовать??
Туточки вам решать! Зело я не способен намыслить...
Никакая часть данного материала не может быть использована в коммерческих целях без письменного разрешения автора.