Design a data structure that supports insert, delete, search and getRandom in constant time - GeeksforGeeks

Design a data structure that supports insert, delete, search and getRandom in constant time - GeeksforGeeks
Design a data structure that supports following operations in Θ(1) time.
insert(x): Inserts an item x to the data structure if not already present.
remove(x): Removes an item x from the data structure if present.
search(x): Searches an item x in the data structure.
getRandom(): Returns a random element from current set of elements

Classical data structure design:
Use Hashset(map) + another data structure
http://myprogrammingpractices.blogspot.com/2015/07/google-system-design-interview-question.html
You want to present numbers to people such that:
a person sees 10 numbers at a time
no two people should see the same numbers at the same time
they get 2 minutes to choose one of those numbers or ask for more. If they 
choose one after the 2 minutes are expired, the request fails.
http://stackoverflow.com/questions/5682218/data-structure-insert-remove-contains-get-random-element-all-at-o1
https://hellosmallworld123.wordpress.com/2014/08/31/design-a-data-structure-that-has-o1-add-search-remove/

The key here is to use an Array and a HashMap. The array stores the element while the hashMap stores the element as the key and the index in the Array as the value.

Add: Simply add to the end of the array, also add corresponding entries in the hashmap.
Remove: Remove from the hashMap, swap the index with the last index of the array, then remove the element from the array, update the swapped element in the hashmap.
getRandom: Generate a random index and access the array.

insert(x)
1) Check if x is already present by doing a hash map lookup.
2) If not present, then insert it at the end of the array.
3) Add in hash table also, x is added as key and last array index as index.

remove(x)
1) Check if x is present by doing a hash map lookup.
2) If present, then find its index and remove it from hash map.
3) Swap the last element with this element in array and remove the last element.Swapping is done because the last element can be removed in O(1) time.
4) Update index of last element in hash map.

getRandom()
1) Generate a random number from 0 to last index.
2) Return the array element at the randomly generated index.

search(x)
Do a lookup for x in hash map.

class MyDS

{

   ArrayList<Integer> arr;   // A resizable array

   // A hash where keys are array elements and vlaues are

   // indexes in arr[]

   HashMap<Integer, Integer>  hash;

   // Constructor (creates arr[] and hash)

   public MyDS()

   {

       arr = new ArrayList<Integer>();

       hash = new HashMap<Integer, Integer>();

   }

   // A Theta(1) function to add an element to MyDS

   // data structure

   void add(int x)

   {

      // If ekement is already present, then noting to do

      if (hash.get(x) != null)

          return;

      // Else put element at the end of arr[]

      int s = arr.size();

      arr.add(x);

      // And put in hash also

      hash.put(x, s);

   }

   // A Theta(1) function to remove an element from MyDS

   // data structure

   void remove(int x)

   {

       // Check if element is present

       Integer index = hash.get(x);

       if (index == null)

          return;

       // If present, then remove element from hash

       hash.remove(x);

       // Swap element with last element so that remove from

       // arr[] can be done in O(1) time

       int size = arr.size();

       Integer last = arr.get(size-1);

       Collections.swap(arr, index,  size-1);

       // Remove last element (This is O(1))

       arr.remove(size-1);

       // Update hash table for new index of last element

       hash.put(last, index);

    }

    // Returns a random element from MyDS

    int getRandom()

    {

       // Find a random index from 0 to size - 1

       Random rand = new Random();  // Choose a different seed

       int index = rand.nextInt(arr.size());

       // Return element at randomly picked index

       return arr.get(index);

    }

    // Returns index of element if element is present, otherwise null

    Integer search(int x)

    {

       return hash.get(x);

    }

}

Extended:
Implement HashTable with get,set,delete,getRandom functions in O(1).
重点在于2个hashmap+arraylist

设计一个数据结构，要求支持插入，删除和random返回一个元素这三种操作，每种操作的复杂度都要是O(1).
删除元素后，要使用数组最后一元素交换到被删除的当前位置。并更新hashmap中的最后一元素的位置信息
public class RandomizeHashTable {

private Map<Integer, Integer> map1; // key + value
private Map<Integer, Integer> map2; // key + index，这个index是key在list里的位置
private List<Integer> list; // key

public RandomizeHashTable() {
map1 = new HashMap<Integer, Integer>();
map2 = new HashMap<Integer, Integer>();
list = new ArrayList<Integer>();
}

public Integer get(int key) {
return map1.get(key);
}

public void set(int key, int value) {
if (map1.containsKey(key)) {
map1.put(key, value);
} else {
map1.put(key, value);
list.add(key);
map2.put(key, list.size() - 1);
}
}

public void delete(int key) {
map1.remove(key);
swap(list, map2.get(key), list.size() - 1);
list.remove(list.size() - 1);
map2.remove(key);
}

public Integer getRandom() {
Random rand = new Random();
int index = rand.nextInt(list.size());
return map1.get(list.get(index));
}

private void swap(List<Integer> list, int x, int y) {
int temp = list.get(x);
list.set(x,  list.get(y));
list.set(y, temp);
}

public static void main(String[] args) {
// TODO Auto-generated method stub

}
}
Read full article from Design a data structure that supports insert, delete, search and getRandom in constant time - GeeksforGeeks