template<class K, class V, class HK, class HF>
class hashmap
{
public:
  typedef K key_type;
  typedef V value_type;
  typedef HK hash_type;
  typedef HF hash_function;

  typedef pair<const key_type, value_type> data_type;

  typedef list<data_type> datalist_type; // данные с одинаковым хешем сгруппированы подряд
private:
  typedef pair<hash_value, datalist_type::iterator> hash_entry;
  typedef list<hash_entry> hashlist_type;

  hash_function hf_;
  hashlist_type hl_;
  datalist_type dl_;

  struct hashfinder
  {
    hash_type h_; // хеш имеет смысл хранить по значению (он маленький)
    hashfinder(hash_type h) : h_(h) {}
    bool operator()(const hash_entry& e) const { return e.first == h_; } // <-- здесь компаратор хеша
  };
  struct keyfinder
  {
    const key_type& k_; // ... а ключ - по ссылке (скорее всего, он большой)
    findhash(const key_type& k) : k_(k) {}
    bool operator()(const data_type& d) const { return d.first == k_; } // <-- здесь компаратор ключа
  };

public:
  typedef datalist_type::iterator iterator;
  typedef datalist_type::const_iterator const_iterator

  iterator find(const key_type& k) // также - версия const
  {
    hash_type h = hf_(k);
    hashlist_type::iterator hli = find_if(hl_.begin(), hl_.end(), hashfinder(h));
    if(hli == hl_.end()) return dl_.end();
    datalist_type::iterator dli = find_if(hl_.second, dl_.end(), keyfinder(k));
  }

  pair<iterator,bool> insert(const key_type& k, const value_type& v)
  {
    hash_type h = hf_(k);
    hashlist_type::iterator hli = find_if(hl_.begin(), hl_.end(), findhash(h));
    if(hli == hl_.end()) // новый хэш
    {
      datalist_type::iterator dli = dl_.insert(dl_.end(), data_type(k,v)); // добавим запись
      hl_.push_back(make_pair<h,dli>); // и добавим хеш
      return make_pair<dli,true>;
    }
    datalist_type::iterator dli = hli.second;
    hashlist_type::iterator hle = hli; ++hle;
    datalist_type::iterator dle = (hle == hl_.end()) ? dl_.end() : hle.second);
    dli = find_if(dli, dle, keyfinder(k));
    if(dli != dle) // ключ найден
      return make_pair<dli,false>;
    dli = dl_.insert(dle, data_type(k,v)); // добавим запись в конец отрезка коллизий
    return make_pair<dli,true>;
  }

  value_type& operator[](const key_type& k) // const недоступен
  {
    static value_type defvalue; // чтобы не конструировать дефолты каждый раз
    return insert(k,defvalue).first.second;
  }
};

struct general_allocator
{                                                    // типовая реализация
  template<class T> T* allocate() const              { return new T(); }
  template<class T> T* duplicate(const T& src) const { return new T(src); }
  template<class T> void deallocate(T* obj) const    { delete obj; }
};

struct hashstring
{
  string str;
  int hash;

  hashstring() : str(), hash(0) {}
  hashstring(const string& s) : str(s), hash(hashfunc(s)) {}
};

bool operator < (const hashstring& l, const hashstring& r)
{
  if(l.hash < r.hash) return true;
  if(r.hash < l.hash) return false;
  // хеши совпали - проверим строки
  if(l.str < r.str) return true;
  return false; // l >= r
}
// остальные операторы определяются через оператор <
// впрочем, для map достаточно только его

/////////
map<hashstring, my_value_type> my_table;

template<class K, class V, class HF>
class hashtable
{
private:
  struct hashkey
  {
    int h_;
    K k_;
    hashkey() : h_(0) {}
    hashkey(int h, K k) : h_(h), k_(k) {}

    bool operator< (const hashkey& r) const { ..... }
  };
  map<hashkey, V> cont_;
  HF hf_;

public:
  hashtable() {}
  hashtable(HF hf) : hf_(hf) {}

  bool empty() const { return cont_.empty(); }
  void clear() { cont_.clear(); }

  V& operator[](const K& k) const
  {
    return cont_[hashkey(hf_(k),k)];
  }
  bool exist(const K& k) const
  {
    return cont_.find(hashkey(hf_(k),k)) != cont_.end();
  }
  // а итераторы пусть погуляют.
};

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_; 
      }
    };


};

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;

B>    typedef hash_table_type::iterator iterator;
B>    typedef hash_table_type::reverse_iterator reverse_iterator;

B>    typedef datalist_type::iterator   iterator_list;

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>    }

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>    }

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>