class MapEntry<K, V> implements Map.Entry<K, V>, Serializable {

    private static final long serialVersionUID = 1759214536880718767L;
    K key;
    V value;
    int hash;
    boolean deleted;

    public MapEntry(final K key, final V value, final int hash) {
      super();
      this.key = key;
      this.value = value;
      this.hash = hash;
    }

    @Override
    public K getKey() {
      return this.key;
    }

    @Override
    public V getValue() {
      return this.value;
    }

    @Override
    public V setValue(final V value) {
      V old = this.value;
      this.value = value;
      return old;
    }
  }

  private MapEntry<K, V>[] entries;

  private int size;

  private int loadThreshold;

  static final int hash(final Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }

  public ArrayHashMap() {
    this.clear();
  }

  @SuppressWarnings({"unchecked", "rawtypes"})
  private void setEntries(final MapEntry[] entries) {
    this.entries = entries;
    this.loadThreshold = Math.round(this.entries.length * LOAD_FACTOR);
  }

  @Override
  public int size() {
    return this.size;
  }

  @Override
  public boolean containsKey(final Object key) {
    MapEntry<K, V>[] table = this.entries;

    if (this.size == 0) {
      return false;
    }

    int hash = hash(key);
    int index = hash & (table.length - 1);
    for (int i = index; i < table.length; i++) {
      MapEntry<K, V> entry = table[i];
      if (entry == null) {
        return false;
      }

      if (entry.deleted) {
        if (entry.hash == hash && entry.key.equals(key)) {
          return false;
        }
      } else if (entry.hash == hash && entry.key.equals(key)) {
        return true;
      }
    }
    return false;
  }

  @Override
  public V get(final Object key) {
    MapEntry<K, V>[] table = this.entries;

    int hash = hash(key);
    int index = hash & (table.length - 1);
    for (int i = index; i < table.length; i++) {
      MapEntry<K, V> entry = table[i];
      if (entry == null) {
        return null;
      }

      if (entry.deleted) {
        if (entry.hash == hash && entry.key.equals(key)) {
          return null;
        }
      } else if (entry.hash == hash && entry.key.equals(key)) {
        return entry.value;
      }
    }
    return null;
  }

  @Override
  public void clear() {
    this.size = 0;
    setEntries(new MapEntry[8]);
  }

  @Override
  public V put(final K key, final V value) {
    int hash = hash(key);

    MapEntry<K, V>[] table = this.entries;
    while (true) {

      int index = hash & (table.length - 1);
      MapEntry<K, V> tombstone = null;
      for (int i = index; i < table.length; i++) {
        MapEntry<K, V> entry = table[i];
        if (entry != null && !entry.deleted) {
          if (entry.hash == hash && entry.key.equals(key)) {
            return entry.setValue(value);
          }
        } else if (entry != null && entry.deleted) {
          if (tombstone == null) {
            tombstone = entry;
          }
        } else if (tombstone != null) {
          this.size++;
          tombstone.key = key;
          tombstone.hash = hash;
          tombstone.deleted = false;
          resizeIfLoadHigh(table);

          return tombstone.setValue(value);
        } else {
          entry = new MapEntry<K, V>(key, value, hash);
          table[i] = entry;
          this.size++;
          resizeIfLoadHigh(table);

          return null;
        }
      }

      table = resize(table);
      setEntries(table);
    }
  }

  private void resizeIfLoadHigh(final MapEntry<K, V>[] table) {
    if (this.size >= this.loadThreshold) {
      setEntries(this.resize(table));
    }
  }

  @SuppressWarnings("unchecked")
  private MapEntry<K, V>[] resize(final MapEntry<K, V>[] table) {
    MapEntry<K, V>[] newTable = new MapEntry[table.length * 2];

    for (int i = 0; i < table.length; i++) {
      MapEntry<K, V> entry = table[i];

      if (entry != null && !entry.deleted) {
        int hash = entry.hash;
        int index = hash & (newTable.length - 1);
        boolean success = false;
        for (int j = index; j < newTable.length; j++) {
          if (newTable[j] == null) {
            newTable[j] = entry;
            success = true;
            break;
          }
        }
        assert (success);
      }
    }
    return newTable;
  }


  @Override
  public V remove(final Object key) {<FILL_FUNCTION_BODY>

    MapEntry<K, V>[] table = this.entries;

    int hash = hash(key);
    int index = hash & (table.length - 1);
    for (int i = index; i < table.length; i++) {
      MapEntry<K, V> entry = table[i];
      if (entry == null) {
        return null;
      }

      if (entry.deleted) {
        if (entry.hash == hash && entry.key.equals(key)) {
          return null;
        }
      }

      if (entry.hash == hash && entry.key.equals(key)) {
        entry.deleted = true;
        entry.hash = 0;
        this.size--;
        return entry.setValue(null);
      }
    }
    return null;
  
<methods>public void clear() ,public boolean containsKey(java.lang.Object) ,public boolean containsValue(java.lang.Object) ,public abstract Set<Entry<K,V>> entrySet() ,public boolean equals(java.lang.Object) ,public V get(java.lang.Object) ,public int hashCode() ,public boolean isEmpty() ,public Set<K> keySet() ,public V put(K, V) ,public void putAll(Map<? extends K,? extends V>) ,public V remove(java.lang.Object) ,public int size() ,public java.lang.String toString() ,public Collection<V> values() <variables>transient Set<K> keySet,transient Collection<V> values