Оптимизированные реализации java.util. Карта и java.util. Набор?

Какую версию JVM вы используете?

Если у вас нет версии 6 (хотя я подозреваю, что это так), то может помочь переключение на 6.

Если это версия серверное приложение и запущено в Windows, попробуйте использовать -server, чтобы использовать правильную реализацию точки доступа.

• Commons Collections имеет карту идентификаторов, которая сравнивается через ==, что должно быть быстрее. - [Joda Primities] [1] as имеет примитивные коллекции, как и Trove. Я поэкспериментировал с Trove и обнаружил, что он лучше использует память.
• Я отображал коллекции из многих небольших объектов с несколькими целыми числами. изменение их на целые числа сэкономило почти половину памяти (хотя для компенсации потребовался более беспорядочный код приложения).
• Мне кажется разумным, что отсортированные деревья должны потреблять меньше памяти, чем хэш-карты, потому что они не требуют коэффициента загрузки (хотя, если кто-то можете подтвердить или у вас есть причина, по которой это на самом деле глупо, напишите в комментариях).

Коллекции Commons имеют FastArrayList , FastHashMap и FastTreeMap , но я не знаю чего они стоят ...

Здесь есть некоторые примечания и ссылки на несколько альтернативных библиотек структур данных: http://www.leepoint.net/notes-java/data/collections/ds-alternatives. html

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

Вероятно, проблема связана не столько с Map или Set ], сколько с объектами, стоящими за ними. В зависимости от вашей проблемы, вам может потребоваться схема, больше похожая на базу данных, где «объекты» хранятся в виде группы байтов, а не как объекты Java. Вы можете встроить базу данных (например, Apache Derby) или заняться своими делами. Это очень зависит от того, что вы на самом деле делаете. HashMap не был намеренно большим и медленным ...

Проверьте GNU Trove:

http://trove4j.sourceforge.net/index.html

В общих коллекциях есть по крайней мере одна реализация, специально созданная для скорости: Flat3Map она довольно специфична в том смысле, что она будет действительно быстрой, если есть не более трех элементов.

Я подозреваю, что вы можете получить больше пробега, следуя совету @ thaggie, добавив взглянуть на время выполнения метода equals / hashcode.

Вы можете немного сэкономить на памяти:

(a) используя более сильный и широкий хэш-код и, таким образом, избегая необходимости хранить keys ;

(b) путем выделения себя из массива, избегая создания отдельного объекта для каждой записи в хеш-таблице .

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

Помните, эта реализация не хранит ключи , поэтому, если два элемента имеют одинаковый хэш-код (который вы d ожидать после хеширования порядка 2 ^ 32 или пары миллиардов элементов, если у вас хорошая хеш-функция), тогда один элемент перезапишет другой:

public class CompactMap<E> implements Serializable {
  static final long serialVersionUID = 1L;

  private static final int MAX_HASH_TABLE_SIZE = 1 << 24;
  private static final int MAX_HASH_TABLE_SIZE_WITH_FILL_FACTOR = 1 << 20;

  private static final long[] byteTable;
  private static final long HSTART = 0xBB40E64DA205B064L;
  private static final long HMULT = 7664345821815920749L;

  static {
    byteTable = new long[256];
    long h = 0x544B2FBACAAF1684L;
    for (int i = 0; i < 256; i++) {
      for (int j = 0; j < 31; j++) {
        h = (h >>> 7) ^ h;
        h = (h << 11) ^ h;
        h = (h >>> 10) ^ h;
      }
      byteTable[i] = h;
    }
  }

  private int maxValues;
  private int[] table;
  private int[] nextPtrs;
  private long[] hashValues;
  private E[] elements;
  private int nextHashValuePos;
  private int hashMask;
  private int size;

  @SuppressWarnings("unchecked")
  public CompactMap(int maxElements) {
    int sz = 128;
    int desiredTableSize = maxElements;
    if (desiredTableSize < MAX_HASH_TABLE_SIZE_WITH_FILL_FACTOR) {
      desiredTableSize = desiredTableSize * 4 / 3;
    }
    desiredTableSize = Math.min(desiredTableSize, MAX_HASH_TABLE_SIZE);
    while (sz < desiredTableSize) {
      sz <<= 1;
    }
    this.maxValues = maxElements;
    this.table = new int[sz];
    this.nextPtrs = new int[maxValues];
    this.hashValues = new long[maxValues];
    this.elements = (E[]) new Object[sz];
    Arrays.fill(table, -1);
    this.hashMask = sz-1;
  }

  public int size() {
    return size;
  }

  public E put(CharSequence key, E val) {
    return put(hash(key), val);
  }

  public E put(long hash, E val) {
    int hc = (int) hash & hashMask;
    int[] table = this.table;
    int k = table[hc];
    if (k != -1) {
      int lastk;
      do {
        if (hashValues[k] == hash) {
          E old = elements[k];
          elements[k] = val;
          return old;
        }
        lastk = k;
        k = nextPtrs[k];
      } while (k != -1);
      k = nextHashValuePos++;
      nextPtrs[lastk] = k;
    } else {
      k = nextHashValuePos++;
      table[hc] = k;
    }
    if (k >= maxValues) {
      throw new IllegalStateException("Hash table full (size " + size + ", k " + k);
    }
    hashValues[k] = hash;
    nextPtrs[k] = -1;
    elements[k] = val;
    size++;
    return null;
  }

  public E get(long hash) {
    int hc = (int) hash & hashMask;
    int[] table = this.table;
    int k = table[hc];
    if (k != -1) {
      do {
        if (hashValues[k] == hash) {
          return elements[k];
        }
        k = nextPtrs[k];
      } while (k != -1);
    }
    return null;
  }

  public E get(CharSequence hash) {
    return get(hash(hash));
  }

  public static long hash(CharSequence cs) {
    if (cs == null) return 1L;
    long h = HSTART;
    final long hmult = HMULT;
    final long[] ht = byteTable;
    for (int i = cs.length()-1; i >= 0; i--) {
      char ch = cs.charAt(i);
      h = (h * hmult) ^ ht[ch & 0xff];
      h = (h * hmult) ^ ht[(ch >>> 8) & 0xff];
    }
    return h;
  }

}

Вы можете расширить AbstractMap и / или AbstractSet в качестве отправной точки. Я сделал это не так давно, чтобы реализовать карту на основе двоичного дерева (ключ был целым числом, и каждый «уровень» в дереве был битовой позицией. Левый дочерний элемент был 0, а правый дочерний элемент был 1). Это сработало для нас, потому что ключом были идентификаторы EUI-64, и для нас большую часть времени верхние 5 байтов должны были быть одинаковыми.

Чтобы реализовать AbstractMap, вам нужно, по крайней мере, реализовать entrySet (), чтобы вернуть набор Map.Entry, каждый из которых является парой ключ / значение.

Чтобы реализовать набор, вы расширяете AbstractSet и предоставляете реализации size () и iterator ().

Однако это по крайней мере. Вы также захотите реализовать get и put, поскольку карта по умолчанию неизменяема,

Попробуйте улучшить производительность ваших методов equals и hashCode, это может помочь ускорить использование ваших объектов стандартными контейнерами.

Here are the ones I know, in addition to Google and Commons Collections:

• http://trove4j.sourceforge.net/
• http://javolution.org/
• http://fastutil.dsi.unimi.it/

Of course you can always implement your own data structures which are optimized for your use cases. To be able to help better, we would need to know you access patterns and what kind of data you store in the collections.

Вы сказали, что профилировали некоторые классы, но сделали ли вы какое-то время, чтобы проверить их скорость? Я не уверен, как бы вы проверили их использование памяти. Похоже, было бы неплохо иметь под рукой некоторые конкретные цифры при сравнении различных реализаций.

Вы смотрели Trove4J ? С веб-сайта:

Trove стремится предоставить быстрые и легкие реализации API java.util.Collections.

Контрольные тесты представлены здесь .

Иногда, когда я вижу, что операции Map и Set используют высокий процент ресурсов ЦП, это указывает на то, что я чрезмерно использовал Map и Set, и реструктуризация моих данных почти удаляла коллекции сверху 10% потребителя ЦП.

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

Я прошел через нечто подобное пару лет назад - очень большие карты и наборы, а также очень многие из них. Реализации Java по умолчанию занимали слишком много места. В конце концов, я свернул свой, но только после того, как изучил фактические шаблоны использования, которые требовались моему коду. Например, у меня был известный большой набор объектов, которые были созданы на раннем этапе, и некоторые карты были разреженными, а другие - плотными. Другие структуры росли монотонно (без удалений), в то время как в других местах было быстрее использовать «коллекцию» и выполнять случайную, но безобидную дополнительную работу по обработке повторяющихся элементов, чем тратить время и пространство на избежание дублирования.