Searching: Hash Table
24th January 2006 - By Paradochs
Information
- Order: O(n)
- Best Case: O(1)
- Average: O(1)
Description (from wikipedia)
In computer science, a hash table, or a hash map, is a data structure that associates keys with values. The primary operation it supports efficiently is a lookup: given a key (e.g. a person’s name), find the corresponding value (e.g. that person’s telephone number). It works by transforming the key using a hash function into a hash, a number that the hash table uses to locate the desired value.
Hash tables are often used to implement associative arrays, sets and caches. Like arrays, hash tables provide constant-time O(1) lookup on average, regardless of the number of items in the table. However, the rare worst-case lookup time can be as bad as O(n). Compared to other associative array data structures, hash tables are most useful when large numbers of records of data are to be stored.
Hash tables store data in pseudo-random locations, so accessing the data in a sorted manner is a very time consuming operation. Other data structures such as self-balancing binary search trees generally operate more slowly (since their lookup time is O(log n)) and are rather more complex to implement than hash tables but maintain a sorted data structure at all times. See a comparison of hash tables and self-balancing binary search trees.
C++ Files and Code Listings
This code has a few built in functions to time the sort and count the number of comparisons.
This code was written and compiled successfully in Visual Studio .NET.
/*
Travis Gadberry
Patrick Hesser
Chris Ladewig
HashTable.h
21Mar05
*/
#ifndef HASHTABLE_H
#define HASHTABLE_H
#include <time.h>
#include <iostream>
#include <vector>
#define EmptySlot -1
using namespace std;
class HashTable {
public:
HashTable(int *, int);
HashTable(vector<int>);
int h(int, int) const;
bool search(int);
double getCreationTime() const;
int getCreationIncrements() const;
double getSearchTime() const;
int getSearchIncrements() const;
int getM() const;
int * getTable();
void setM(int);
void setSearchTime(int);
void setCreationTime(int);
private:
int * table;
int key;
double creationtime;
double searchtime;
int searchincrements;
int creationincrements;
int m;
};
#endif
/*
Travis Gadberry
Patrick Hesser
Chris Ladewig
HashTable.cpp
21Mar05
*/
#include "HashTable.h"
using namespace std;
HashTable::HashTable(int * A, int c){
time_t t1, t2;
int col=0;
t1 = clock();
int b=1;
if (c==10)
b=c+1;
else if (c==1000)
b=c+9;
else if (c==10000)
b=c+7;
setM(b);
int j=0, i = 0, k=0;
table = new int[b];
for(int l=0; l<b; l++)
table[l]=-1;
do {
k = h(A[i], j);
if (creationincrements++, table[k] == EmptySlot)
{
table[k] = A[i];
i++;
j = 0;
} else {
j++;
}
} while (i < b);
t2 = clock();
creationtime = (t2 - t1)/CLOCKS_PER_SEC;
searchtime=0;
}
HashTable::HashTable(vector<int> V){
int c = V.size();
int * A = new int[c];
for(int i=0; i<c; i++)
A[i] = V.at(i);
time_t t1, t2;
int col=0;
t1 = clock();
int b=1;
if (c==10)
b=c+1;
else if (c==1000)
b=c+9;
else if (c==10000)
b=c+7;
setM(b);
int j=0, i = 0, k=0;
table = new int[b];
for(int l=0; l<b; l++)
table[l]=-1;
do {
k = h(A[i], j);
if (creationincrements++, table[k] == EmptySlot)
{
table[k] = A[i];
i++;
j = 0;
} else {
j++;
}
} while (i < b);
t2 = clock();
creationtime = (t2 - t1)/CLOCKS_PER_SEC;
searchtime=0;
}
int HashTable::h(int k, int i) const{
int hp=((k%m)+(i*(1+(k%(m-1)))))%m;
return hp;
}
bool HashTable::search(int a){
// for(int k = 0; k < 10; k++)
// cout << k << " : " << table[k] << endl;
time_t t1, t2;
t1 = clock();
bool found = false;
int j, i = 0;
do {
j = h(a,i);
if (searchincrements++, table[j] == a)
{
found = true;
}
i++;
} while ((table[j] != EmptySlot) && (i < m) && (found==false));
t2 = clock();
searchtime = (t2 - t1)/CLOCKS_PER_SEC;
return found;
}
int * HashTable::getTable(){
return table;
}
double HashTable::getCreationTime() const{
return creationtime;
}
void HashTable::setCreationTime(int a){
creationtime=a;
}
int HashTable::getCreationIncrements() const{
return creationincrements;
}
double HashTable::getSearchTime() const{
return searchtime;
}
void HashTable::setSearchTime(int a){
searchtime=a;
}
int HashTable::getSearchIncrements() const{
return searchincrements;
}
int HashTable::getM() const{
return m;
}
void HashTable::setM(int a){
m=a;
}
January 24th, 2006 at 9:08 pm
[...] Hash Table Search [...]