Как ускорить заполнение HashMap?

У меня есть система координат(оси X,Y).Мне даны 4 числа: x1,x2,y1,y2.Эти числа являются вершинами квадрата -
правая верхняя - x1,y1, а левая нижняя - x2,y2.
Нужно заполнить любой массив или коллекцию матрицей с 1 и 0.Где 1 - квадрат есть в этой точке,0 - пусто.Ниже пример:

000000000
111111000
111111000
111111000
000000000

Индексами или Keys являются координаты X и Y.
Я делаю это так:

private Map<Pair<Integer, Integer>, Integer> calculateRectangleSquare(int x1, int x2, int y1, int y2) {

        int minY = Math.min(y1, y2);
        int minX = Math.min(x1, x2);
        int maxY = Math.max(y1, y2);
        int maxX = Math.max(x1, x2);
        Map<Pair<Integer, Integer>, Integer> rectSquare = new HashMap<Pair<Integer, Integer>,Integer>();
        for (int i = minX; i < maxX; i++) {
            for (int j = minY; j < maxY; j++) {
                Pair<Integer, Integer> key = new Pair<Integer, Integer>(i, j);
                rectSquare.put(key, true);
            }
        }
        return rectSquare;
    }

Но время выполнения растёт экспоненциально!Если максимальный x и y будут равны 10 или 100,то нет проблем!
Однако 10000 он вообще никогда не сосчитает.Какой алгоритм можно использовать, чтобы улучшить время работы?
Я пробовал реализовать через двухмерный массив, но мне нужно чтобы была возможность работы с отрицательными
координатами, а я не понимаю ,как сдвигать.