Взглянем на этот набросок:
(бежать критиковать не надо, я знаю что он кривой и в половине мест даже значение из функции вернуть забыли)
template <class data_t, class hasher_t, class marker_t, size_t SIZE>
class Hashtable {
hasher_t hasher_;
marker_t marker_;
std::vector<data_t> memory_;
public:
Hashtable()
: memory_(SIZE) {
}
data_t *insert(const data_t &_value) {
auto index = hasher_(_value) % SIZE;
// test next 8 cells for free element
for(int i = 0; i < 8; ++i) {
auto &ref = memory_[index];
if (marker_.is_free(ref, index)) {
ref_ = _value;
return &ref_;
}
index += 1;
index = index % SIZE;
}
// cannot find place
return nullptr;
}
data_t *find(const data_t &_value) {
auto index = hasher_(_value) % SIZE;
for(int i = 0; i < 8; ++i) {
auto &ref = memory_[index];
if (marker_.is_tombstone(ref, index)) {
index += 1;
index = index % SIZE;
continue;
}
if (_value == ref) {
return &ref;
}
}
}
bool erase(const data_t &_value) {
data_t *f = find(_value);
if (!f) {
return false;
}
// TODO: check if next element is not empty.
marker_.make_tombstone(*f /*TODO: index argument*/);
return true;
}
};
Вопрос не о том, насколько он успешен и корректен - скорее всего не работает нихрена и какие-то случаи не учитывает. Я его даже компилять не пытался.
Вопрос о другом - щас сформулирую.
Это хеш-таблица с открытой адресацией, фиксированного размера. Коллизии в открытой адресации решают всякими методами, например вот этим линейным пробингом - если в нужной ячейке уже занято, кладёшь куда-то в следующую. При поиске, соответственно, оцениваешь не одну ячейку, в которую попал хешом, а ряд следующих. У ячейки 3 состояния - занято, свободно, «затычка». Затычка - это то, что говорит «мотай дальше, там что-то лежит». Затычки ставятся, когда удаляешь и после удалённого было не пусто. В моём коде это не корректно написано - он безусловно ставит затычку, а надо проверить что её ставить стоит.
Так вот, хранить эти состояния ячеек отдельными полями и флагами я не хочу (то есть, оборачивать data_t в структуру, одним из полей которых будет uint8_t state). А иногда хочу. И это хочу-не-хочу хочется вынести из реализации хетаблицы.
И вот придуман marker_t. Он нужен затем, чтобы пользователь мог определить, как хештаблица будет выяснять статус ячейки.
-
Пользователь может решить, что какое-то зарезервированное значение data_t будет отвечать за какое-то состояние.
-
Пользователь может решить, что нужны отдельные флаги. Тогда он в объекте marker_t херачит массив на SIZE элементов и, получая в вызовах маркера этот индекс, судит по этим состояниям и меняет их когда надо.
Короче, обсудите этот подход. Насколько тупо и наркоманско. Может быть кто-то в студии есть достаточно умный, кто читал разные хештаблицы и понимает, что где-то сделано так и это на самом деле круто или где-то сделано это же ещё гениальнее!
