[Uneex] GCC STL в 4.0: где hash_map?

[Vladimir Prus]

On Wednesday 03 May 2006 14:43, Aleksey Fedoseev wrote:
> >>Лично мне проблема кажется надуманной. Написать свой контейнер для
> >>хэш-таблицы на основе готовых stl-контейнеров - дело 10 минут.
> >
> > Вы писали? Мне кажется это утверждение надуманным. Я уже проходил такое:
> > "да тут работы на 10 минут"
>
> Вот самый простой пример.

Мне кажется, что хотя приведенная реализация впролне пригодна для 
использования, она все таки не вполне сопоставима по качеству со стандартной 
реализацией hash_map.

1. Интерфейс.

   Класс не предоставляет никаких итераторов. 

2. Реализация.

>  const size_t DNS_CACHE_HASH_SIZE = 256;

Использование фиксированного размера делает класс непригодным для 
использования как хеш-таблица общего назначения. Кроме этого, использование 
числа 256 означает, что из всего хеш-значения используются только младшие 8 
бит. Для примера, в STL для размера таблицы всегда используется простое 
число.
   
>         bool has(const Key& key) {
>                 size_t index = make_hash(key);
>                 const EntryMap& map = hash_table[index];
>                 EMIter citer = map.find(key);
>                 if(citer != map.end()) {
>                         return true;
>                 } else {
>                         return false;
>                 }
>         }

Этот метод должен быть обьявлет как const.
       
>         bool find(const Key& key, Entry& entry) {
>                 size_t index = make_hash(key);
>                 const EntryMap& map = hash_table[index];
>                 EMIter citer = map.find(key);
>                 if(citer != map.end()) {
>                         entry = citer->second;

Здесь происходит "глубокое" копирование объекта, что может негативно сказаться 
на производительности.
      
>         /**
>          * Hashe table with entry maps (used for find/add acceleration)
>          */             
>         typedef typename std::map<Key, Value> EntryMap;
>         typedef typename EntryMap::const_iterator EMIter;
>         std::vector<EntryMap> hash_table;

Классическое решения для хеш-таблиц это вектор, в каждом элементе которого 
находится список пар (ключ/значение). Использование std::map вместо списка 
несколько странно. Если количество элементов в std::map мало, то от него мало 
проку. Если количество элементов в std::map велико, то более эффективно будет 
увеличить размер хеш-таблицы.

- Volodya