Buttercola: O(1) Map

Constant Clear Map
Buttercola: O(1) Map
Design a Map so that it supports the following operations:
1. add(int val), O(1) time
2. remove(int val), O(1) time
3. contains(int val), O(1) time
4. clear(), O(1) time
5. iterate(), O(num of elements)

- use version to track valid element in map. Analysis:
If we just use a randomized array, i.e, a hash map, add(), remove(), and contains() operations take O(1) time. The clear() takes O(size of array) time (NOT SURE), and iterate takes O(size of array) time. Note that iterate() takes O(size of array) time instead of O(num of elements) because of the implementation of a hash map is usually an array or array + list. So it needs to iterate all elements of the array no matter if it is taken or not. 

If we only use a sequential accessed array, i.e, an ArrayList in Java, the add() takes O(1), but remove() and contains() takes O(num of elements) time. clear() takes O(1) ?? not sure. 
iterate() takes O(num of elements) time as well. 

So the idea is to combine the two data structures together. 

class Solution implements Iterable<Integer> {

  private int[] list;

  private Map<Integer, Integer> map;

  private int size;

  private final int INIT_CAPACITY = 4;

   

  public Solution() {

    list = new int[INIT_CAPACITY];

    map = new HashMap<>();

    size = 0;

  }

   

  public void add(int val) {

    if (size == list.length) {

      resize(2 * list.length);

    }

     

    map.put(val, size);

    list[size] = val;

    size++;

  }

   

  public void remove(int val) {

    if (!map.containsKey(val)) {

      throw new NoSuchElementException();

    }

     

    // step 1: get the index of the val to be removed

    int idxToRemove = map.get(val);

     

    // step 2: move the last element to the index to be removed

    int lastE = list[size - 1];

    list[idxToRemove] = lastE;

    //list[size - 1] = null;

     

    size--;

    map.remove(val);

    map.put(lastE, idxToRemove);

     

    // shrink the array

    if (size > 0 && size == list.length / 4) {

      resize(list.length / 2);

    }

     

  }

   

  public boolean contains(int val) {

    return map.containsKey(val) &&

           map.get(val) < size &&

           val == list[map.get(val)];

  }

  public void clear() {

    size = 0;

  }

   

  @Override

  public Iterator<Integer> iterator() {

    return new MyListIterator();

  }

   

  private class MyListIterator implements Iterator<Integer> {

    private int i = 0;

     

    @Override

    public boolean hasNext() {

      return i < size;

    }

     

   @Override

    public Integer next() {

      Integer result = 0;

      if (hasNext()) {

        result = (Integer) list[i];

        i++;

      }

       

      return result;

    }

     

    @Override

    public void remove() {

      throw new UnsupportedOperationException();

    }

  }

   

  private void resize(int newSize) {

    int[] newList = new int[newSize];

    newList = Arrays.copyOf(list, size);

    list = newList;

  }

Use two arrays, map[n] and list[n], where for the map[i], the index stores the val of the data, and its value stores the index of the data in the list array. The real value is stored in the list array as well for the convenience of iterator() in O(num of elements) time. 

The basic idea of this solution is very close the method 1, just to use the map[] array to simulate a hash map. Therefore here we assume that the size of the map[] array is unlimited and the value of the data to be stored is never out of boundary. 

  private Integer[] map;

  private Integer[] list;

  private int size;

  private final int INIT_CAPACITY = 4;

  private final int MAP_CAPACITY = 1000;

   

  public Solution() {

    list = new Integer[INIT_CAPACITY];

    map = new Integer[MAP_CAPACITY];

    this.size = 0;

  }

   

  public void add(int val) {   

    if (size == list.length) {

      resize(2 * list.length);

    }

     

    map[val] = size;

    list[size] = val;

    size++;

  }

   

  public void remove(int val) {

    if (!contains(val)) {

      throw new NoSuchElementException();

    }

     

    // step 1: get the index of the val to be removed

    int idxToRemove = map[val];

     

    // step 2: move the last element to the index to be removed

    int lastE = list[size - 1];

    list[idxToRemove] = lastE;

    list[size - 1] = null;

     

    size--;

     

    map[lastE] = idxToRemove;

    map[val] = null;

     

     

     

    // shrink the array

    if (size > 0 && size == list.length / 4) {

      resize(list.length / 2);

    }

  }

   

  public boolean contains(int val) {

    return map[val] != null &&

           map[val] < size &&

           val == list[map[val]];

  }

  public void clear() {

    size = 0;

  }

   

  @Override

  public Iterator<Integer> iterator() {

    return new MyListIterator();

  }

   

  private class MyListIterator implements Iterator<Integer> {

    private int i = 0;

     

    @Override

    public boolean hasNext() {

      return i < size;

    }

     

   @Override

    public Integer next() {

      Integer result = 0;

      if (hasNext()) {

        result = list[i];

        i++;

      }

       

      return result;

    }

     

    @Override

    public void remove() {

      throw new UnsupportedOperationException();

    }

  }

   

  private void resize(int newSize) {

    Integer[] newList = new Integer[newSize];

    for (int i = 0; i < size; i++) {

      newList[i] = list[i];

    }

    list = newList;

  }

   

  public static void main(String[] args) {

    Solution sol = new Solution();

    sol.add(1);

    sol.add(3);

    //sol.add(5);

     

    //System.out.println(sol.contains(3));

     

    sol.clear();

     

    sol.add(4);

    sol.add(5);

     

    System.out.println(sol.contains(3));

     

    //sol.remove(3);

     

     

    Iterator<Integer> it = sol.iterator();

    while (it.hasNext()) {

      int val = it.next();

      System.out.println(val);

    }

     

  }

Read full article from Buttercola: O(1) Map