@Override
	public void delete(Key key)
	{
		if (key == null)
			return;

		for (int i = hash(key); keys[i] != null; i = (i + 1) % M)
			if (key.equals(keys[i]))
			{ 
				// delete
				keys[i] = null;
				vals[i] = null;
				N--;
				
				// Re-insert all keys and vals which are to the right of keys[i],
				// thereby ensuring that the hash table is consistent for future
				// searches of keys with the same has as i
				for (int j = (i + 1) % M; keys[j] != null; j = (j + 1) % M)
				{
					Key keyToReInsert = keys[j];
					Value valToReInsert = vals[j];

					keys[j] = null;
					vals[j] = null;
					N--;
					put(keyToReInsert, valToReInsert);
				}
				break;
			}

		if (N > INIT_CAPACITY && N < M / 8)
			resize(M / 2);
	}