hash.h File Reference

hash table. More...

#include <iostream>
#include "abacus/abacusroot.h"
#include "abacus/hash.inc"

Go to the source code of this file.

Classes
class	ABA_HASHITEM< KeyType, ItemType >
	see also class ABA_HASH More...
class	ABA_HASH< KeyType, ItemType >
	data structure stores a set of items and provides as central functions the insertion of a new item, the search for an item, and the deletion of an item. More...

---

Detailed Description

hash table.

Author:

Matthias Elf

This data structure stores a set of items and provides as central functions the insertion of a new item, the search for an item, and the deletion of an item.

Each item is associated with a key. The set of all possible keys is called the universe. A hash table has a fixed size . A hash function assigns to each key of the universe a number in , which we denote slot. If an item is inserted in the hash table, then it is stored in the component of the array associated with its slot. Usually, n is much smaller than the cardinality of the universe. Hence, it can happen that two elements are mapped to the same slot. This is called a collision. In order to resolve collisions, each slot of the hash table does not store an item explicitly, but is the start of a linear list storing all items mapped to this slot.

This template implements a hash table where collisions are resolved by chaining. Currently hash functions for keys of type int and ABA_STRING are implemented. If you want to use this data structure for other types (e.g., YOURTYPE), you should derive a class from the class ABA_HASH and define a hash function {int hf(YOURTYPE key)}.

The following sections implement two new classes. The class ABA_HASH contains the hash table which consists of pointers to the class ABA_HASHITEM. The class ABA_HASHITEM stores an inserted element and its key and provides the a pointer to the next item in the linked list.

License:

This file is part of ABACUS - A Branch And CUt System Copyright (C) 1995 - 2003 University of Cologne, Germany

This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 2.1 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA

See also:

http://www.gnu.org/copyleft/gpl.html

Definition in file hash.h.

---