Skip to content

Instantly share code, notes, and snippets.

Created May 17, 2013 21:39
What would you like to do?
Hashed Array, a set type data structure which has O(1) insertion, O(1) removal, and O(1) uniformly randomly retrieval.
#include <iostream>
#include <vector>
#include <map>
#include <cmath>
using namespace std;
// Hashed array
template <class T>
class HashedArray
void insert(T x);
void remove(T x);
T getRandom();
int size();
void print();
vector<T> a;
map<T, int> h;
template <class T>
void HashedArray<T>::insert(T x)
int i = a.size();
h[x] = i;
template <class T>
void HashedArray<T>::remove(T x)
if(h.find(x) == h.end()) return;
int m = a.size()-1;
T d = a[m];
int i = h[x];
a[i] = d;
h[d] = i;
template <class T>
T HashedArray<T>::getRandom()
int r = rand() % a.size();
return a[r];
template <class T>
int HashedArray<T>::size()
return a.size();
template <class T>
void HashedArray<T>::print()
for (int i=0; i<a.size(); i++)
cout << a[i] << " ";
cout << endl;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment