Hash Tables

A efficient and flexible implementation of hash tables. More...

Collaboration diagram for Hash Tables:

Detailed Description

A efficient and flexible implementation of hash tables.

This file provides class HashTable. This class is both efficient and flexible: efficient because the access to elements is usually computed using a small amount of processor instructions, and flexible because several methods allow to fine tune the behavior of each hash table. For instance, a hashtable can allow or forbid different elements to have the same key. This behavior can be modified at any time during the execution of the program. Functions for hashing keys are defined in file HashFunc.h. Here again, these functions are quite flexible as they can be overloaded by the user to support new kind of keys. In addition to HashTable, the current file provides classes HashTableIteratorSafe and HashTableConstIteratorSafe (a.k.a. HashTable<>::iterator_safe and HashTable<>::const_iterator_safe) that allow safe parsing of the hash tables. By safe, we mean that whenever the element pointed to by such an iterator is removed from the hashtable, accessing it through the iterator (*iter) does not result in a segmentation fault but rather in an exception being thrown. This safety is ensured at a very low cost (actually, our experiments show that our HashTables and HashTable's safe iterators significantly outperform the standard library unordered_maps). Of course, if there is no possibility for an iterator to point to a deleted element, the user can use the "unsafe" iterators HashTableIterator and HashTableConstIterator (a.k.a. HashTable<>::iterator and HashTable<>::const_iterator). These iterators are slightly faster than their safe counterparts. However, as in the standard library, accessing through them a deleted element usually results in a mess (most probably a segfault).

Warning

HashTables guarantee that any element stored within them will have the same location in memory until it is removed from the hashtable (and this holds whatever operation is performed on the hashtable like new insertions, deletions, resizing, etc.).

Usage example:

// creation of an empty hash table
HashTable<int,string> table1;

// insert two elements into the hash table
table1.insert (10,"xxx");
table1.insert (20,"yyy");
table1.emplace (30,"zzz");

// creation of a nonempty hashtable using initializer lists
HashTable<int,bool> table { std::make_pair (3,true), std::make_pair(2,false)
};

// display the content of the hash table
cerr << table1;

// get the number of elements stored into the hash table
cerr << "number of elements in table1 = " << table1.size () << endl;

// create two copies of the hash table
HashTable<int,string> table2, table3 = table1;
table2 = table3;

// get the element whose key is 10
cerr << table1[10] << " = xxx" << endl;

// check whether there exists an element with key 20
if (table1.exists (20)) cerr << "element found" << endl;

// transform the hashtable of string into a hashtable of int assuming f is
// defined as: int f (const string& str) { return str.size (); }
HashTable<int,int> table = table1.map (f);

// remove two elements from table1 and table2
table1.erase (10);         // key = 10
table1.eraseByVal ("yyy"); // val = "yyy"
table2.clear ();

// check whether the hash table is empty
if (!table1.empty ()) cerr << "table not empty" << endl;

// check wether hashtables contain the same elements
if ((table1 == table2) && (table1 != table3))
  cerr << "check for equality/inequality" << endl;

// parse the content of a hashtable using an unsafe iterator
for (HashTable<int,string>::const_iterator iter = table1.cbegin();
      iter != table1.cend(); ++iter)
  cerr << *iter;
HashTable<int,string>::iterator iter = table1.begin();
iter += 2;
cerr << iter.key () << " " << iter.val ();

// use an iterator to point the element we wish to erase
HashTable<int,string>::iterator_safe iterS = table1.beginSafe ();
table1.erase ( table1.beginSafe () + 4 );
table1.erase ( iterS ); // this is safe because the iterator is safe

// check for iterator's safety
for (HashTable<int,string>::iterator_safe iter = table1.beginSafe ();
          iter != table1.endSafe (); ++iter )
  table1.eraseByVal ( *iter );

Warning

agrum/core/set_tpl.h To speed-up accessors in sets, we rely on the fact (which holds currently) that hashTable's iterators end are never modified by insertions or deletions of elements in hash tables. If this property were to be changed, set_tpl.h should be updated accordingly.

agrum/core/bijection_tpl.h Same as set_tpl.h but, in addition, bijections assume that once a pair (key,val) has been created in the hashtable, its location in memory will never change, even if the hashtable is resized.

agrum/core/sequence_tpl.h Same as bijection_tpl.h.

agrum/core/priorityQueue_tpl.h Same as bijection_tpl.h.

agrum/core/heap_tpl.h Same as bijection_tpl.h.

Classes
class	gum::HashTableConst
	Parameters specifying the default behavior of the hashtables. More...
class	gum::HashTableBucket< Key, Val >
	A recipient for a pair of key value in a gum::HashTableList. More...
class	gum::HashTableList< Key, Val, Alloc >
	A chained list used by gum::HashTable. More...
class	gum::HashTable< Key, Val, Alloc >
	The class for generic Hash Tables. More...
class	gum::HashTableIteratorStaticEnd
	A class used to create the static iterator used by HashTables. More...
class	gum::HashTableConstIteratorSafe< Key, Val >
	Safe Const Iterators for hashtables. More...
class	gum::HashTableIteratorSafe< Key, Val >
	Safe Iterators for hashtables. More...
class	gum::HashTableConstIterator< Key, Val >
	Unsafe Const Iterators for hashtablesHashTableConstIterator provides a fast but unsafe way to parse HashTables. More...
class	gum::HashTableIterator< Key, Val >
	Unsafe Iterators for hashtablesHashTableIterator provides a fast but unsafe way to parse HashTables. More...

Functions
template<typename Key , typename Val , typename Alloc >
std::ostream &	gum::operator<< (std::ostream &s, const HashTableList< Key, Val, Alloc > &list)
	Prints the content of a gum::HashTableList in the stream. More...
template<typename Key , typename Val , typename Alloc >
std::ostream &	gum::operator<< (std::ostream &s, const HashTableList< Key *, Val, Alloc > &list)
	Prints the content of a gum::HashTableList with pointers key in the stream. More...
template<typename Key , typename Val , typename Alloc >
std::ostream &	gum::operator<< (std::ostream &s, const HashTable< Key, Val, Alloc > &table)
	Prints the content of a gum::HashTable in the stream. More...
template<typename Key , typename Val , typename Alloc >
std::ostream &	gum::operator<< (std::ostream &s, const HashTable< Key *, Val, Alloc > &table)
	Prints the content of a gum::HashTable with pointers key in the stream. More...

Function Documentation

operator<<() [1/4]

template<typename Key , typename Val , typename Alloc >

std::ostream & gum::operator<<	(	std::ostream &	s,
		const HashTableList< Key, Val, Alloc > &	list
	)

Prints the content of a gum::HashTableList in the stream.

Definition at line 1203 of file hashTable_tpl.h.

References gum::HashTableList< Key, Val, Alloc >::__deb_list.

                                                                         {
    bool deja = false;
    stream << "[";

    for (HashTableBucket< Key, Val >* ptr = list.__deb_list; ptr;
         ptr = ptr->list.next, deja = true) {
      if (deja) stream << " , ";

      stream << ptr->key() << "=>" << ptr->val();
    }

    stream << "]";

    return stream;
  }

operator<<() [2/4]

template<typename Key , typename Val , typename Alloc >

std::ostream & gum::operator<<	(	std::ostream &	s,
		const HashTableList< Key *, Val, Alloc > &	list
	)

Prints the content of a gum::HashTableList with pointers key in the stream.

Definition at line 1221 of file hashTable_tpl.h.

References gum::HashTableList< Key, Val, Alloc >::__deb_list.

                                                                          {
    bool deja = false;
    stream << "[";

    for (HashTableBucket< Key, Val >* ptr = list.__deb_list; ptr;
         ptr = ptr->list.next, deja = true) {
      if (deja) stream << " , ";

      stream << ptr->key() << "=>" << ptr->val();
    }

    stream << "]";

    return stream;
  }

operator<<() [3/4]

template<typename Key , typename Val , typename Alloc >

std::ostream & gum::operator<<	(	std::ostream &	s,
		const HashTable< Key, Val, Alloc > &	table
	)

Prints the content of a gum::HashTable in the stream.

Definition at line 1239 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__nodes, and gum::HashTable< Key, Val, Alloc >::__size.

                                                                      {
    bool deja = false;
    stream << "{";

    for (Size i = Size(0); i < table.__size; ++i)
      for (auto ptr = table.__nodes[i].__deb_list; ptr; ptr = ptr->next) {
        if (deja) stream << " , ";

        stream << ptr->key() << "=>" << ptr->val();

        deja = true;
      }

    stream << "}";

    return stream;
  }

operator<<() [4/4]

template<typename Key , typename Val , typename Alloc >

std::ostream & gum::operator<<	(	std::ostream &	s,
		const HashTable< Key *, Val, Alloc > &	table
	)

Prints the content of a gum::HashTable with pointers key in the stream.

Definition at line 1259 of file hashTable_tpl.h.

References gum::HashTable< Key, Val, Alloc >::__nodes, and gum::HashTable< Key, Val, Alloc >::__size.

                                                                       {
    bool deja = false;
    stream << "{";

    for (Size i = Size(0); i < table.__size; ++i)
      for (auto ptr = table.__nodes[i].__deb_list; ptr; ptr = ptr->next) {
        if (deja) stream << " , ";

        stream << ptr->key() << "=>" << ptr->val();

        deja = true;
      }

    stream << "}";

    return stream;
  }