@Override
	public void put(Key key, Value val)
	{
		if (val == null)
		{
			delete(key);
			return;
		}

		int i = rank(key);

		// key is already in table. Update
		if (i < N && key.compareTo(keys[i]) == 0)
		{
			vals[i] = val;
			return;
		}

		// insert new key-value pair
		if (N == keys.length)
			resize(keys.length * 2);

		for (int j = N; j > i; j--)
		{
			keys[j] = keys[j - 1];
			vals[j] = vals[j - 1];
		}
		keys[i] = key;
		vals[i] = val;
		N++;
	}