К>Мощность пространства хешей h, мощность множества ключей k.
К>Среднее количество ключей с одинаковым хешем c = max(1, k/h).
К>Время поиска T = Th(h) * Tk(c), где Th — поиск хешей, Tk — поиск ключей в множестве коллизий данного хеша.
Дурня свалял.
Конечно же, T = Th + Tk.
Поэтому все последующие формулы — прошу считать инсинуациями.
... << RSDN@Home 1.1.2 stable >>
> А отношение равенства не позволяет однозначно сортировать. Это означает, что поиск будет не двоичный, а линейный.
Ничего страшного: в том же STLport hash_[multi](map|set) используют именно равенство в качестве функции сравнения
Posted via RSDN NNTP Server 1.8 beta
Легче одурачить людей, чем убедить их в том, что они одурачены. — Марк Твен
Здравствуйте, Кодт, Вы писали:
К> ...
К> А отношение равенства не позволяет однозначно сортировать. Это означает,
К> что поиск будет не двоичный, а линейный.
Ну, ну...
Вообще-то в хеш-таблице поиск должен осуществлятся почти за константное время (время вычисления хеш-функции). Исключения составляют коллизии, но их можно не учитывать.
Оператор == в хеш-контейнере нужен лишь для того, чтобы диагностировать коллизию.
Posted via RSDN NNTP Server 1.8 beta
Здравствуйте, Кодт, Вы писали:
некоторый код из вашего эскиза.
Как вам такой хеш мап
Скажите свок ФЕ, и что можна добавить, улучшить.
template <class _Key, class _Val , class _HashFcn>
class hash_map {
private:
datalist_type _dl; // список всех пар
hash_table_type _hl; // хаш таблиця для пар
hash_function _hf;
int data_capacity; // количество сохраненых елементов
public:
typedef _Key key_type;
typedef _Val value_type;
typedef _HashFcn hash_function;
typedef size_t hash_type;
typedef std::pair<key_type, value_type> data_type;
typedef std::list<data_type*> datalist_type; // пары с однаковым хешом
typedef std::vector<datalist_type> hash_table_type;
typedef hash_table_type::iterator iterator;
typedef hash_table_type::reverse_iterator reverse_iterator;
typedef datalist_type::iterator iterator_list;
//----------------------------------------
hash_map() {
_hl.resize(100);
data_capacity = 0;
}
//----------------------------------------
std::pair<iterator, bool> insert(const key_type& k, const value_type& v) {
hash_type h_ = _hf(k, _hl.capacity() );
data_type *dt_;
iterator hli_;
hli_ = _hl.begin() + h_ - 1;
if( !hli_ -> empty() ) {
// ключ в хаш таблице с таким хешом уже есть
// сомотрим разные ли ключи
iterator_list dli_ = find_if( hli_ -> begin(), hli_ -> end(), keyfinder( k ));
if( dli_ != (hli_ -> end()) )
{
iterator hli_end = _hl.end();
return pair<iterator, bool>(hli_end, false);
}
}
dt_ = new data_type;
dt_ -> first = k;
dt_ -> second = v;
_dl.push_back(dt_);
hli_ -> push_back(dt_);
data_capacity++;
return pair<iterator, bool>(hli_,true);
}
//----------------------------------------
iterator find(const key_type& k) {
iterator hli_;
hash_type h_ = _hf(k, _hl.capacity() );
hli_ = _hl.begin() + h_ - 1;
bool tr = hli_ -> empty();
if( tr == 1 )
return NULL;
return hli_;
}
//----------------------------------------
iterator begin() {
return _hl.begin();
}
iterator end() {
return _hl.end();
}
reverse_iterator rbegin() {
return _hl.rbegin()
}
reverse_iterator rend() {
return _hl.rend();
}
//----------------------------------------
size_t size() {
return data_capacity;
}
size_t capacity() {
return _hl.capacity();
}
//----------------------------------------
void clear()
{
}
//----------------------------------------
datalist_type* operator[](const key_type& k) {
hash_type h_ = _hf(k, _hl.capacity() );
return &_hl[h_- 1];
}
private:
void rehash() {
};
struct keyfinder {
const key_type& k_;
keyfinder(const key_type& k) : k_(k) {}
bool operator()(const data_type* d) const {
return d->first == k_;
}
};
};
Здравствуйте, maq, Вы писали:
maq>Мне кажется проще взять из Dinkumware, у него и исходник куда более читабельный имхо.
Ве эти исходники очень большие, читал я их, достали они меня, но зато много интересного нашел.
Самое интересное — мне нужно спмому написать hash_map, а не передрать.
... << RSDN@Home 1.1.3 stable >>
Здравствуйте, eBit, Вы писали:
B>Как вам такой хеш мап
B>Скажите свок ФЕ, и что можна добавить, улучшить.
B>B>template <class _Key, class _Val , class _HashFcn>
B>class hash_map {
B> private:
B> datalist_type _dl; // список всех пар
B> hash_table_type _hl; // хаш таблиця для пар
B> hash_function _hf;
B> int data_capacity; // количество сохраненых елементов
B> public:
B> typedef _Key key_type;
B> typedef _Val value_type;
B> typedef _HashFcn hash_function;
B> typedef size_t hash_type;
B> typedef std::pair<key_type, value_type> data_type;
B> typedef std::list<data_type*> datalist_type; // пары с однаковым хешом
B> typedef std::vector<datalist_type> hash_table_type;
Получается, у тебя есть один список всех элементов (_dl) и ещё отдельно списки коллизий (_hl) ?
Да ещё и совместное владение элементами (хранящимися по указателям).
А нафига, раскрой секрет.
На мой взгляд, удобнее иметь список элементов (отсортированный по хешу) и таблицу итераторов.
Для отдельного, искушённого пользователя можно сделать итерирование по хешам. Но вообще это не имеет смысла.
B> typedef hash_table_type::iterator iterator;
B> typedef hash_table_type::reverse_iterator reverse_iterator;
B> typedef datalist_type::iterator iterator_list;
Вот тебе уже пришлось ввести два разных типа итераторов — один на домене хештаблицы, а другой — на домене списка-помойки.
Кстати, если уж давать имя, то не iterator_list (список итераторов), а list_iterator (итератор списка).
B>//----------------------------------------
B> hash_map() {
B> _hl.resize(100);
B> data_capacity = 0;
B> }
По некоторым соображениям, лучше использовать хеш с размером, равным простому числу. Достигается лучшее перемешивание. (Подробности — у Кнута; я, к сожалению, не вчитывался, а сейчас книги нет).
B>//----------------------------------------
B> std::pair<iterator, bool> insert(const key_type& k, const value_type& v) {
B> hash_type h_ = _hf(k, _hl.capacity() );
// только, наверное, не capacity(), а size() ?
B> data_type *dt_;
B> iterator hli_;
B> hli_ = _hl.begin() + h_ - 1;
B> if( !hli_ -> empty() ) {
B> // ключ в хаш таблице с таким хешом уже есть
B> // сомотрим разные ли ключи
B> iterator_list dli_ = find_if( hli_ -> begin(), hli_ -> end(), keyfinder( k ));
B> if( dli_ != (hli_ -> end()) )
B> {
B> iterator hli_end = _hl.end();
B> return pair<iterator, bool>(hli_end, false);
B> }
B> }
B> dt_ = new data_type;
B> dt_ -> first = k;
B> dt_ -> second = v;
B> _dl.push_back(dt_);
B> hli_ -> push_back(dt_);
B> data_capacity++;
B> return pair<iterator, bool>(hli_,true);
B> }
B>//----------------------------------------
B> iterator find(const key_type& k) {
B> iterator hli_;
B> hash_type h_ = _hf(k, _hl.capacity() );
B> hli_ = _hl.begin() + h_ - 1;
B> bool tr = hli_ -> empty();
B> if( tr == 1 )
B> return NULL;
B> return hli_;
B> }
B>//----------------------------------------
B> iterator begin() {
B> return _hl.begin();
B> }
B> iterator end() {
B> return _hl.end();
B> }
B> reverse_iterator rbegin() {
B> return _hl.rbegin()
B> }
B> reverse_iterator rend() {
B> return _hl.rend();
B> }
B>//----------------------------------------
B> size_t size() {
B> return data_capacity;
B> }
B> size_t capacity() {
B> return _hl.capacity();
B> }
Ты определись — соблюдаешь ли конвенции STL или нет. Потому что иначе — это бардак.
Заодно выясни, в чём разница между size() и capacity()
B>//----------------------------------------
B> void clear()
B> {
B> }
B>//----------------------------------------
B> datalist_type* operator[](const key_type& k) {
B> hash_type h_ = _hf(k, _hl.capacity() );
B> return &_hl[h_- 1];
B> }
Очень весело! Мне по ключу выдают список элементов, где я ещё и должен искать этот ключ. Ладно бы эти элементы были логически сгруппированы (и имел бы смысл такой "нечёткий запрос" — как, например, std::multiset/multimap). Так ведь нет — элементы перемешаны! То есть их объединение — исключительная прихоть судьбы в виде хеш-функции.
B> private:
B> void rehash() {
// а это что?
B> };
B> struct keyfinder {
B> const key_type& k_;
B> keyfinder(const key_type& k) : k_(k) {}
B> bool operator()(const data_type* d) const {
B> return d->first == k_;
B> }
B> };
B>};
B>
Итого,
... << RSDN@Home 1.1.2 stable >>
Перекуём баги на фичи!
