Computing › Stl › Containers › Associative ›

Hash Map

Hash map helps to manage a sequence of elements as a hash table

View version details

Contents

Definition
Interface
Description
Performance
Hash Map Header Members
Hash Map Template Class Members
Page Comments

Key Facts

Gyroscopic Couple: The rate of change of angular momentum ( $\inline \tau$ ) = $\inline I\omega\Omega$ (In the limit).

$\inline I$ = Moment of Inertia.
$\inline \omega$ = Angular velocity
$\inline \Omega$ = Angular velocity of precession.

Blaise Pascal (1623-1662) was a French mathematician, physicist, inventor, writer and Catholic philosopher.

Definition

Hash_map template class is defined in the header <hash_map>, and in the backward-compatibility header <hash_map.h>. This class is an SGI extension; it is not part of the C++ standard.

Interface

#include <hash_map>
namespace std{
      template < class Key, class Type,
                 class Traits=hash_compare<Key, less<Key> >,
                 class Allocator=allocator<pair <const Key, Type> > >
      class hash_map;
}

Parameters

Parameter	Description
Key	The element data type to be stored in the hash_map
Type	The element data type to be stored in the hash_map
Traits	The type which includes two function objects, one of class compare that is a binary predicate able to compare two element values as sort keys to determine their relative order and a hash function that is a unary predicate mapping key values of the elements to unsigned integers of type `size_t`. This argument is optional, and `hash_compare<Key, less<Key> >` is the default value
Allocator	The type that represents the stored allocator object that encapsulates details about the hash_map's allocation and de-allocation of memory.This argument is optional, and the default value is `allocator<pair <const Key, Type>>`

Description

Hash_map helps to manage a sequence of elements as a hash table, each table entry storing a bidirectional linked list of nodes, and each node storing one element. An element consists of a key, for ordering the sequence, and a mapped value, which goes along for the ride.

Hash_map is a Hashed Associative Container because its elements are grouped into buckets based on the value of a hash function applied to the key values of the elements.

Hash_map is also an Unique Associative Container meaning that each of its elements must have a unique key, and a Pair Associative Container, because its element data values are distinct from its key values.

Examples of declaring a hash_map:

// Create an empty hash_map h_map of key type integer
hash_map <int, int> h_map; 
 
// Create an empty hash_map h_map1 with the key comparison function of less than
hash_map <int, int, hash_compare <int, less<int> > > h_map1;
 
// Create an empty hash_map h_map2 with the key comparison function of greater than
hash_map <int, int, hash_compare <int, greater<int> > > h_map2; //

Performance

The main advantage of hashing over sorting is greater efficiency; a successful hashing performs insertions, deletions, and finds in constant average time as compared with a time proportional to the logarithm of the number of elements in the container for sorting techniques.

A collision occurs when distinct key values are mapped into the same hashed value.

Hashed associative containers are optimized for the operations of lookup, insertion and removal. The member functions that explicitly support these operations are efficient when used with a well-designed hash function, performing them in a time that is on average constant and not dependent on the number of elements in the container. A well-designed hash function produces a uniform distribution of hashed values and minimizes the number of collisions. In the worst case, with the worst possible hash function, the number of operations is proportional to the number of elements in the sequence (linear time).

Hash Map Header Members

Operators

Operator	Description
operator!=	Tests if the hash_map object on the left side of the operator is not equal to the hash_map object on the right side
operator<	Tests if the hash_map object on the left side of the operator is less than the hash_map object on the right side
operator<=	Tests if the hash_map object on the left side of the operator is less than or equal to the hash_map or object on the right side
operator==	Tests if the hash_map object on the left side of the operator is equal to the hash_map object on the right side
operator>	Tests if the hash_map object on the left side of the operator is greater than the hash_map object on the right side
operator>=	Tests if the hash_map object on the left side of the operator is greater than or equal to the hash_map object on the right side
operator[ ]	Inserts an element into a hash_map with a specified key value

Classes

Class	Description
hash_compare	Describes an object that can be used by any of the hash associative containers: hash_map, hash_multimap, hash_set, or hash_multiset, as a default Traits parameter object to order and hash the elements they contain
value_compare	Provides a function object that can compare the elements of a hash_map by comparing the values of their keys to determine their relative order in the hash_map
hash_map	Used for the storage and fast retrieval of data from a collection in which each element is a pair that has a sort key whose value is unique and an associated data value

Hash Map Template Class Members

Typedefs

Typedef	Description
allocator_type	A type that represents the allocator class for the hash_map object
const_iterator	A type that provides a bidirectional iterator that can read a `const` element in the hash_map
const_pointer	A type that provides a pointer to a `const` element in a hash_map
const_reference	A type that provides a reference to a `const` element stored in a hash_map for reading and performing `const` operations
const_reverse_iterator	A type that provides a bidirectional iterator that can read any `const` element in the hash_map
difference_type	A signed integer type that can be used to represent the number of elements of a hash_map in a range between elements pointed to by iterators
iterator	A type that provides a bidirectional iterator that can read or modify any element in a hash_map
key_compare	A type that provides a function object that can compare two sort keys to determine the relative order of two elements in the hash_map
key_type	A type describes the sort key object that constitutes each element of the hash_map
mapped_type	A type that represents the data type stored in a hash_map
pointer	A type that provides a pointer to an element in a hash_map
reference	A type that provides a reference to an element stored in a hash_map
reverse_iterator	A type that provides a bidirectional iterator that can read or modify an element in a reversed hash_map
size_type	An unsigned integer type that can represent the number of elements in a hash_map
value_type	A type that provides a function object that can compare two elements as sort keys to determine their relative order in the hash_map

Member Functions

Function	Description
begin()	Returns an iterator addressing the first element in the hash_map
rbegin()	Returns an iterator addressing the first element in a reversed hash_map
clear()	Erases all the elements of a hash_map
count()	Returns the number of elements in a hash_map whose key matches a parameter-specified key
empty()	Tests if a hash_map is empty
end()	Returns an iterator that addresses the location succeeding the last element in a hash_map
rend()	Returns an iterator that addresses the location succeeding the last element in a reversed hash_map
equal_range()	Returns a pair of iterators, respectively, to the first element in a hash_map with a key that is greater than a specified key and to the first element in the hash_map with a key that is equal to or greater than the key
erase()	Removes an element or a range of elements in a hash_map from specified positions
find()	Returns an iterator addressing the location of an element in a hash_map that has a key equivalent to a specified key
get_allocator()	Returns a copy of the allocator object used to construct the hash_map
hash_map()	Constructs a hash_map that is empty or that is a copy of all or part of some other hash_map
insert()	Inserts an element or a range of elements into a hash_map
key_comp()	Returns an iterator to the first element in a hash_map with a key value that is equal to or greater than that of a specified key
lower_bound()	Returns an iterator to the first element in a hash_map with a key value that is equal to or greater than that of a specified key
upper_bound()	Returns an iterator to the first element in a hash_map that with a key value that is greater than that of a specified key
size()	Specifies a new size for a hash_map
max_size()	Returns the maximum length of the hash_map
swap()	Exchanges the elements of two hash_maps
value_comp()	Retrieves a copy of the comparison object used to order element values in a hash_map

References:

Example:

Example - hash_map methods

Problem

This program illustrates a hash_map including a default constructor and the insert(), begin(), erase() member functions of the STL hash_map interface.

Workings

#include <iostream>
#include <hash_map>
#define _DEFINE_DEPRECATED_HASH_CLASSES 0
typedef pair <int, int> Int_Pair;
 
using namespace std;
using namespace stdext;
 
int main()
{
  hash_map <int, int> hm1;
  hash_map <int, int> :: iterator hm1_Iter;
  hash_map <int, int> :: const_iterator hm1_cIter;
 
  hm1.insert (Int_Pair(0, 0));
  hm1.insert (Int_Pair(1, 1));
  hm1.insert (Int_Pair(2, 4));
 
  hm1_cIter = hm1.begin ( );
  cout <<"The first element of hm1 is "<<hm1_cIter -> first<<"."<<endl;
 
  hm1_Iter = hm1.begin ( );
  hm1.erase ( hm1_Iter );
 
  // The following 2 lines would err because the iterator is const
  // hm1_cIter = hm1.begin ( );
  // hm1.erase ( hm1_cIter );
 
   hm1_cIter = hm1.begin( );
   cout <<"The first element of hm1 is now "<<hm1_cIter -> first<<"."<<endl;
 
  return 0;
}

Solution

Output:

The first element of hm1 is 0.
The first element of hm1 is now 1.

References

References:

http://msdn.microsoft.com/en-us