Замена большого массива на Java?

У меня есть массив объектов длиной 614 125.
Дело в том, чтобы получить индекс из числа 3 байт, получая по модулю 85 каждого значения байта.

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

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

Есть ли альтернатива такой ситуации? Обратите внимание, что я пробовал HashMap, но он еще медленнее, потому что мои хэш-значения слишком далеки друг от друга.

Я пытаюсь найти способ не выделять огромный массив с самого начала, а динамически добавлять новые объекты. Использование моего объекта узла с «next» и «previous» решило бы проблему и сделало бы сортировку очень быстрой, но я не могу найти способ найти мой хэш без порядка O(N/2), который слишком длинный (я хочу O(1)).

Вот код, если он имеет какую-либо пользу:

HashMap

public class HashMap {
    public static final int ARRAY_SIZE = 614125;
    // This value represents 255/3 (max byte value)=> hash is 3 bytes long:
    // First byte%85 gives us the first index, same for second and third.
    private static final int MODULO = 85;
    private static final int FIRST_MULTIPLIER = 7225;
    private static final int SECOND_MULTIPLIER = 85;

    private Node[] mHashMap;
    private int index1, index2, index3;

    public HashMap() {
        mHashMap = new Node[ARRAY_SIZE];
    }

    public void put(int hash, int value) {
        index1 = (hash & 0xFF) % MODULO;
        index2 = ((hash >> 8) & 0xFF) % MODULO;
        index3 = ((hash >> 16) & 0xFF) % MODULO;
        int index = index1 * FIRST_MULTIPLIER + index2 * SECOND_MULTIPLIER + index3;
        Node node = mHashMap[index];
        if (node == null) {
            mHashMap[index] = new Node(value);
        } else {
            node.addValue(value);
        }
    }

    public Node get(int hash) {
        index1 = (hash & 0xFF) % MODULO;
        index2 = ((hash >> 8) & 0xFF) % MODULO;
        index3 = ((hash >> 16) & 0xFF) % MODULO;
        int index = index1 * FIRST_MULTIPLIER + index2 * SECOND_MULTIPLIER + index3;
        return mHashMap[index];
    }
}

Узел

public class Node {
    private Node mNext;
    private int mValue;

    public Node(int value) {
        mValue = value;
        mNext = null;
    }

    public void setNext(Node next) {
        mNext = next;
    }

    public boolean hasNext() {
        return mNext != null;
    }

    public Node next() {
        return mNext;
    }

    public int getValue() {
        return mValue;
    }

    public void addValue(int value) {
        mValue += value;
    }
}
Метки

1 ответ

  1. Я пытаюсь найти способ не выделять огромный массив с самого начала, а динамически добавлять новые объекты.

    Почему? IIUYC вам не нужно минимизировать потребление памяти. Использование меньшего объема памяти может привести к увеличению скорости, но я не думаю, что это применимо здесь.

    Виновником, скорее всего, является Ваше очень медленное вычисление хэша. Выполнение %несколько раз очень дорого и не требуется здесь. Если вы хотите сопоставить intс индексом массива, вы можете сделать это с помощью одного модуля (хорошо, когда размер массива является простым) или без медленной операции вообще (когда размер массива является степень двух).

    Я бы предложил что-то вроде

    private static final int LOG_ARRAY_SIZE = 19;
    private static final int ARRAY_SIZE = 1 << LOG_ARRAY_SIZE;
    
    private int toIndex(int x) {
        return (x * 0xcc9e2d51) >>> (32-LOG_ARRAY_SIZE);
    }
    
    public void put(int hash, int value) {
        index = toIndex(hash);
        Node node = mHashMap[index];
        if (node == null) {
            mHashMap[index] = new Node(value);
        } else {
            node.addValue(value);
        }
    }
    
    public Node get(int hash) {
        index = toIndex(hash);
        return mHashMap[index];
    }