Data Structure: Insert-Delete-Contains-GetRandom

Simple but useful data structure written in Java. Provides Insert, Delete, Contains, and GetRandom in O(1).

It could easily be extended to provide Get( int index), Pop(), Push(), etc if needed.

The important thing is that the objects are only being stored in the List, while the HashMap simply maps the object to its index in the list.

import java.util.HashMap;
import java.util.ArrayList;
import java.util.Random;

/**
* A Data Structure that implements Insert, Contains, Delete, and GetRandom in O(1)
*
* @author dkirby
*
*/
public class Insert_Contains_Delete_GetRandom
{
private HashMap<Object, Integer> _hash;
private ArrayList<Object> _list;

public Insert_Contains_Delete_GetRandom()
{
_hash = new HashMap<>();
_list = new ArrayList<>();
}

public void insert(Object object)
{
int index = _list.size();

_hash.put(object, index);
_list.add(object);
}

public boolean contains(Object object)
{
return _hash.containsKey(object);
}

public void delete(Object object)
{
if (_hash.containsKey(object))
{   
// get the index of the specified object in the list
int index = _hash.get(object);  

// get the index of the last element in the list
int end = _list.size() - 1;

// get the element at the 'end' position
Object o = _list.get(end);  

// copy the 'end' element into position 'index'
_list.set(index, o);

// drop the last element from the list
_list.remove(end);  

// update the hash of the object that was moved
_hash.put(o, index);

// remove the specified object from the hash
_hash.remove(object);
}
}

public Object getRandom()
{
Random rand = new Random();
int index = rand.nextInt(_list.size());

return _list.get(index);
}
}