Сортировка… хэш-таблицей (ещё подсчётом-деревом и HashMap'ом)

Три дня назад я задумался об объединении сортировки подсчётом и деревом. Обсудив её с коллегой, пришли к следующему решению: вместо TreeSet использовать HashMap (при чём здесь вообще TreeSet, можно посмотреть ниже). Но и этого мне показалось мало, так что я решил реализовать собственную хэш-таблицу и посмотреть, что из этого выйдет. Результаты показались мне довольно интересными.

Все три типа сортировки отлично подходит для случаев, когда мощность множества уникальных элементов в массиве относительно мала (что под этим понимать, станет понятно после того, как мы взглянем на результаты тестов).

Сортировка подсчётом-деревом

Строим дерево Пар (Ключ, Количество), где Ключ отвечает за элемент массива, а Количество — количество повторений этого эл-та массива. Дерево, естественно, сбалансированное, чёрно-красное, например.

Далее всё логично. Добавляем все элементы массива в Пару, а Пару ищем в дереве (чтобы избежать пересоздания объектов используем заранее созданную Пару, у которой меняем Ключ. Здесь Количество нас не интересует, поскольку мы ищем соответствие исключительно по Ключу). Если такой Ключ уже есть, увеличиваем Количество, иначе добавляем новую Пару (Ключ, 1).

Переписываем массив, удаляя каждый раз вершину и записывая Ключ столько раз, сколько у него Количество.

Чтобы не реализовывать дерево самому, для описанного алгоритма использовал TreeSet, который работает на чёрно-красном дереве.

Использование HashMap

В качестве ключа будем хранить элемент массива, в качестве значения по ключу — количество повторений.

Использование моей собственной хэш-таблицы

Я решил прибегнуть к методу открытой адресации. В хэш-таблице храним объекты класса Пара, где first — ключ, second — количество повторений. Естественно, был добавлен конструктор, принимающий начальный размер таблицы и load factor. Хэш-функция самая простая: берём ключ по модулю, в случае повторного обращения добавляем единицу (единица хорошо подходит тем, что массив ключей получается наиболее упорядоченным, а в конце нам придётся отсортировать все ключи стандартной быстрой сортировкой, ведь в таблице они могут получиться не упорядоченными). Так что можно сказать, что это объединение хэширования и ещё одной сортировки.

Коллизии

Очевидно, могут возникать коллизии и это плохо скажется как на времени определения хэша, так и на скорости сортировки итогового массива хэшей (упорядоченные или почти упорядоченные данные сортируются быстрее). Но вот в чём дело: наша хэш-ф-я изменяется по мере расширения таблицы. Так что специально подобрать такие данные, становится значительно сложнее. Более того, можно сделать случайными (в определённом диапазоне, конечно) load factor и коэффициент расширения, что сделает невозможным заранее подобрать значения, приводящие к коллизиям. Ну и если в одной таблице одни данные приводили к коллизиям, то после перехэша, количество коллизий может значительно сократиться (в несколько раз). Слабым местом будут являться факториалы чисел, но их неимоверно мало (до 2^31, например, их всего 11 (не учитывая 0)).

Нам не подойдут криптографические хэш-ф-и ввиду того, что с ними про почти упорядоченный массив хэшей (в смысле упорядоченности по ключам) можно забыть.

Время работы

Сортировка подсчётом-деревом: в худшем случае за O(n log n), в лучшем — за линейное время.
Сортировка хэш-таблицей: время на хэширование + сложность сортировки массива хэшей (может изменяться в зависимости от выбранного алгоритма и реализации, так что здесь ничего указывать не буду). Дать оценку сложности трудно ввиду использования хэш-функции и возможных различных подходов к сортировке хэшей. Этот вопрос нуждается в дополнительном исследовании, однако очевидно, что в худшем случае (когда входные данные будут намеренно подобраны под конкретную на конкретном этапе выполнения хэш-функцию) время работы будет O(n^2).

Что по памяти?

Сортировка подсчётом-деревом потребует O(distinct(n)) дополнительной памяти
Для хэш-таблицы нам потребуется O(distinct(n)) памяти + память для сортировки хэшей (зависит от выбранного алгоритма).

Вот какие результаты в миллисекундах у меня получились на рандомных числах при сортировке массива объектов на 10 млн эл-тов, с диапазоном значений [0; x]:

На тестах load factor в моей хэш-таблице = 0.75, initial capacity = 20, увеличивается таблица каждый раз вдвое

При x = 10:
2044 — встроенная
285 — подсчётом-деревом (Usatov sort)
276 — HashMap (Usatov-Prokurat sort)
140 — моей хэш-таблицей (Usatov-Prokurat sort using MyHashTable)

x = 100:
2406 — встроенная
455 — подсчётом-деревом
283 — HashMap
134 — хэш-таблицей

x = 1_000:
2171 — встроенная
930 — подсчётом-деревом
380 — HashMap
209 — хэш-таблицей

x = 10_000
2879 — встроенная
1666 — подсчётом-деревом
634 — HashMap
326 — хэш-таблицей

x = 100_000
4045 — встроенная
2899 — подсчётом-деревом
866 — HashMap
762 — хэш-таблицей

x = 1_000_000
4997 — встроенная
5762 — подсчётом-деревом
2505- HashMap
1294 — хэш-таблицей

x = 10_000_000
5083 — встроенная
11480 — подсчётом-деревом
5099 — HashMap
3240 — хэш-таблицей

Как я и говорил в начале, эти сортировки лучше всего подходят для тех случаев, когда мощность множества элементов массива достаточно мала относительно размера массива.

Также стоит отметить, что встроенная сортировка намного быстрее работает на упорядоченных (почти упорядоченных) данных (или массиве в обратном порядке), но мой способ быстрее справляется на рандомных числах.

Сортировка подсчётом-деревом:

    static void usatovSort(Integer[] arr) {
        TreeSet<MyPair> tree = new TreeSet<>();
        MyPair temp;
        MyPair mp = new MyPair();
        for (int i : arr) {
            temp = mp;
            temp.first = i;
            temp = tree.ceiling(temp);
            if (temp != null && temp.first == i) // порядок условий важен, т.к если первое не выполняется, то проверка второго не производится
                temp.second++;
            else tree.add(new MyPair(i, 1));
        }
        int ptr = 0;
        while (!tree.isEmpty()) {
            temp = tree.pollFirst();
            for (int i = 0; i < temp.second; i++)
                arr[ptr++] = temp.first;
        }
    }

Сортировка через HashMap:

    static void usatovProkuratSortUsingHashMap(Integer[] arr) {
        HashMap<Integer, Integer> hm = new HashMap<>();
        Integer temp;
        for (Integer i : arr) {
            temp = hm.get(i);
            if (temp == null) hm.put(i, 1);
            else hm.put(i, temp + 1);
        }

        ArrayList<Integer> keys = new ArrayList<>(hm.keySet().size());
        keys.addAll(hm.keySet());
        keys.sort(Comparator.naturalOrder());
        int ptr = 0;
        for (Integer i : keys)
            for (int j = 0; j < hm.get(i); j++)
                arr[ptr++] = i;
    }

Сортировка через мою хэш-таблицу:

    static void usatovProkuratSortUsingMyHashTable(Integer[] arr) {
        MyHashTable mht = new MyHashTable();
        for (Integer i : arr)
            mht.add(i);
        MyPair[] res = mht.getPairs();
        int ptr = 0;
        Arrays.sort(res, Comparator.comparingInt(o -> o.first));
        for (MyPair mp : res)
            for (int i = 0; i < mp.second; i++)
                arr[ptr++] = mp.first;
    }

Реализация хэш-таблицы:

public class MyHashTable {

    private MyPair[] hashArr;
    private double count = 0;
    private double loadFactor = 0.5;
    private double expansivity = 2;
    private static final int DEFAULT_CAPACITY = 20;

    public MyHashTable() {
        hashArr = new MyPair[DEFAULT_CAPACITY];
    }

    public MyHashTable(double loadFactor) {
        hashArr = new MyPair[DEFAULT_CAPACITY];
        this.loadFactor = loadFactor;
    }

    public MyHashTable(int capacity) {
        hashArr = new MyPair[capacity];
    }

    public MyHashTable(int capacity, double loadFactor) {
        hashArr = new MyPair[capacity];
        this.loadFactor = loadFactor;
    }

    public MyHashTable(int capacity, double loadFactor, double expansivity) {
        hashArr = new MyPair[capacity];
        this.loadFactor = loadFactor;
        this.expansivity = expansivity;
    }

    public MyPair[] getPairs() {
        MyPair[] pairs = new MyPair[(int) count];
        int ptr = 0;
        for (MyPair i : hashArr)
            if (i != null)
                pairs[ptr++] = i;
        return pairs;
    }

    public MyPair get(int key) {
        int add = 0;
        while (true)
            if (hashArr[(key + add) % hashArr.length].first == key) {
                return hashArr[(key + add) % hashArr.length];
            } else if (add++ == hashArr.length) return null;
    }

    public void add(int key) {
        if (count / hashArr.length >= loadFactor) grow();
        int add = 0;
        while (true) {
            if (hashArr[(key + add) % hashArr.length] == null) {
                hashArr[(key + add) % hashArr.length] = new MyPair(key, 1);
                count++;
                return;
            }
            if (hashArr[(key + add) % hashArr.length].first == key) {
                hashArr[(key + add) % hashArr.length].second++;
                return;
            }
            add++;
        }
    }

    public void add(MyPair newMP) {
        if (count / hashArr.length >= loadFactor) grow();
        int add = 0;
        while (true) {
            if (hashArr[(newMP.first + add) % hashArr.length] == null) {
                hashArr[(newMP.first + add) % hashArr.length] = newMP;
                count++;
                return;
            }
            if (hashArr[(newMP.first + add) % hashArr.length].first == newMP.first) {
                hashArr[(newMP.first + add) % hashArr.length].second += newMP.second;
                return;
            }
            add++;
        }
    }

    private void grow() {
        MyPair[] oldHash = hashArr;
        hashArr = new MyPair[(int) (expansivity * hashArr.length)];
        for (MyPair i : oldHash)
            if (i != null)
                innerAdd(i);
    }

    private void innerAdd(MyPair mp) {
        int add = 0;
        while (true) {
            if (hashArr[(mp.first + add) % hashArr.length] == null) {
                hashArr[(mp.first + add) % hashArr.length] = mp;
                return;
            }
            if (hashArr[(mp.first + add) % hashArr.length].first == mp.first) {
                hashArr[(mp.first + add) % hashArr.length].second += mp.second;
                return;
            }
            add++;
        }
    }
}

Класс Пара:

public class MyPair implements Comparable<MyPair> {
    public int first;
    public int second;

    public MyPair() {
    }

    public MyPair(int first, int second) {
        this.first = first;
        this.second = second;
    }

    @Override
    public int compareTo(MyPair o) {
        return first - o.first;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        MyPair myPair = (MyPair) o;
        return first == myPair.first;
    }

    @Override
    public int hashCode() {
        return first;
    }
}