HashMapImplementation() {
  _numberOfEntries = 0;
  _numberOfDeleted = 0;
  _loadLimit = _computeLoadLimit(_INITIAL_CAPACITY);
  _keys = new List(_INITIAL_CAPACITY);
  _values = new List<V>(_INITIAL_CAPACITY);
}

factory HashMapImplementation.from(Map<K, V> other) {
  Map<K, V> result = new HashMapImplementation<K, V>();
  other.forEach((K key, V value) { result[key] = value; });
  return result;
}

void clear() {
  _numberOfEntries = 0;
  _numberOfDeleted = 0;
  int length = _keys.length;
  for (int i = 0; i < length; i++) {
    _keys[i] = null;
    _values[i] = null;
  }
}

bool containsKey(K key) {
  return (_probeForLookup(key) != -1);
}

bool containsValue(V value) {
  int length = _values.length;
  for (int i = 0; i < length; i++) {
    var key = _keys[i];
    if ((key !== null) && (key !== _DELETED_KEY)) {
      if (_values[i] == value) return true;
    }
  }
  return false;
}

void forEach(void f(K key, V value)) {
  int length = _keys.length;
  for (int i = 0; i < length; i++) {
    var key = _keys[i];
    if ((key !== null) && (key !== _DELETED_KEY)) {
      f(key, _values[i]);
    }
  }
}

Collection<K> getKeys() {
  List<K> list = new List<K>(length);
  int i = 0;
  forEach(void _(K key, V value) {
    list[i++] = key;
  });
  return list;
}

Collection<V> getValues() {
  List<V> list = new List<V>(length);
  int i = 0;
  forEach(void _(K key, V value) {
    list[i++] = value;
  });
  return list;
}

bool isEmpty() {
  return _numberOfEntries == 0;
}

int get length() {
  return _numberOfEntries;
}

V operator [](K key) {
  int index = _probeForLookup(key);
  if (index < 0) return null;
  return _values[index];
}

void operator []=(K key, V value) {
  _ensureCapacity();
  int index = _probeForAdding(key);
  if ((_keys[index] === null) || (_keys[index] === _DELETED_KEY)) {
    _numberOfEntries++;
  }
  _keys[index] = key;
  _values[index] = value;
}

V putIfAbsent(K key, V ifAbsent()) {
  int index = _probeForLookup(key);
  if (index >=0) return _values[index];

  V value = ifAbsent();
  this[key] = value;
  return value;
}

V remove(K key) {
  int index = _probeForLookup(key);
  if (index >= 0) {
    _numberOfEntries--;
    V value = _values[index];
    _values[index] = null;
    // Set the key to the sentinel to not break the probing chain.
    _keys[index] = _DELETED_KEY;
    _numberOfDeleted++;
    return value;
  }
  return null;
}

String toString() {
  return Maps.mapToString(this);
}