java.util.map和java.util.set的优化实现?

通常这些方法很快。 您应该检查以下几点:是否实现了哈希代码?它们是否足够均匀?否则你会得到垃圾表演。

http://trove4j.sourceforge.net/ <--这有点快,节省了一些内存。我在50000个更新上保存了几毫秒

您确定正确使用地图/集合吗?也就是说,不要试图迭代所有的值或类似的东西。此外,例如,不要执行包含操作,然后执行删除操作。只需检查移除。

还要检查您是否使用双精度vs双精度。我注意到在成千上万的检查中有一些MS性能改进。

您是否也正确/适当地设置了初始容量?

你看过吗 Trove4J ?从网站:

Trove旨在提供java.util.collections API的快速、轻量级实现。

提供的基准 here .

除了google和commons收藏之外,以下是我所知道的:

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

当然,您可以始终实现自己的数据结构,这些结构针对您的用例进行了优化。为了更好地提供帮助,我们需要知道您访问模式以及您在集合中存储的数据类型。

尝试提高equals和hashcode方法的性能,这有助于加速标准容器对对象的使用。

可以将AbstractMap和/或AbstractSet扩展为起点。不久前,我做了这项工作,实现了一个基于二进制trie的映射(键是一个整数,树上的每个“级别”都有一个位位置)。左边的孩子是0,右边的孩子是1)。这对我们来说效果很好,因为密钥是eui-64标识符,而对我们来说,前5个字节的大部分时间都是相同的。

要实现抽象映射,至少需要实现entry set()方法,以返回一组map.entry,每个都是键/值对。

要实现一个集合,可以扩展抽象集并提供size()和迭代器()的实现。

不过,至少是这样。您还需要实现get和put,因为默认映射是不可修改的,get的默认实现通过entryset迭代以查找匹配项。

您可以通过以下方式节省一点内存:

(a)使用A 更强、更宽的哈希代码 因此 避免储存钥匙 ;

(b)从阵列中分配自己, 避免为每个哈希表条目创建单独的对象 .

如果它是有用的,这里是一个不加修饰的Java实现 数字接收器 我有时发现哈希表很有用。您可以直接在一个字符序列(包括字符串)上键入键,否则您必须自己为您的对象设计一个强大的64位哈希函数。

记住,这个实现 不储存钥匙 ,因此,如果两个项目具有相同的哈希代码(按照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;
  }

}

查看GNU Trove:

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

公共集合中至少有一个实现是专门为速度构建的: Flat3Map 非常具体的一点是,只要不超过3个元素,它就会非常快。

我怀疑通过遵循@thaggie的建议add查看equals/hashcode方法的时间,您可能会获得更多里程。

你说你对一些课程做了概述,但是你有没有做过任何时间来检查他们的速度?我不知道你会怎么检查他们的内存使用情况。当您比较不同的实现时,手头上有一些具体的数字似乎是件好事。

这里有一些注释和到几个可选数据结构库的链接: http://www.leepoint.net/notes-java/data/collections/ds-alternatives.html

我还将投下一张支持FastUtil的强烈票。(在另一个响应和该页面中提到)它的数据结构比您可以动摇的多,并且版本针对作为键或值的基元类型进行了优化。(缺点是JAR文件很大,但您可以根据需要对其进行修剪)

几年前我做过类似的事情——非常大的地图和布景,还有很多。默认的Java实现占用了太多的空间。最后,我滚动了自己的代码,但只有在检查了代码所需的实际使用模式之后。例如,我有一组已知的大型对象,这些对象是在早期创建的,一些地图是稀疏的,而另一些则是密集的。其他结构单调地增长(没有删除),而在其他地方,使用“集合”并偶尔做一些无害的额外工作来处理重复项要比花时间和空间来避免重复更快。我使用的许多实现都是基于数组的,并且利用了这样一个事实:我的哈希代码是按顺序分配的,因此对于密集映射,查找只是一个数组访问。

带走信息:

1. 看看你的算法,
2. 考虑多个实现,以及
3. 请记住,大多数图书馆都是为一般用途(如插入 和 删除,一系列的大小,既不是稀疏的也不是密集的,等等),所以他们将有日常开支,你可能可以避免。

哦,写单元测试…

有时,当我看到map和set操作使用高百分比的CPU时,它表明我已经过度使用了map和set,并且重新构造了我的数据,几乎消除了前10%的CPU使用者的收集。

查看是否可以避免集合的副本、对集合的迭代和任何其他操作,这些操作会导致访问集合的大多数元素并创建对象。

可能不是那么多 Map 或 Set 这导致了问题,但背后的物体。根据您的问题,您可能需要更多的数据库类型方案,其中“对象”存储为一组字节而不是Java对象。您可以嵌入一个数据库(比如ApacheDerby)或者自己做一些专门的事情。这完全取决于你实际在做什么。 HashMap 不是故意的大而慢…

公共集合具有 FastArrayList , FastHashMap 和 FastTreeMap 但我不知道它们的价值…

• Commons集合有一个ID映射,它通过==进行比较,应该更快。 - [Joda Primities][1] 原始集合和特洛夫一样。我用Trove做了实验,发现它的记忆利用率更好。
• 我正在用几个整数映射许多小对象的集合。把它们改成ints可以节省近一半的内存(尽管需要一些更混乱的应用程序代码来补偿)。
• 在我看来,排序树应该比哈希映射消耗更少的内存是合理的,因为它们不需要加载因子(尽管如果有人可以确认或者有理由认为这是愚蠢的,请在评论中发表)。

您使用的是哪个版本的JVM?

如果你不在6号(尽管我怀疑你在),那么换到6号可能会有帮助。

如果这是一个在Windows上运行的服务器应用程序,请尝试使用-server来使用正确的热点实现。

我使用下面的包(koloboke)来执行int散列映射,因为它支持promisive类型,并且在一个长变量中存储了两个int,这对我来说很酷。 koloboke