私はそれがオープンソースでなければなりません...低メモリ使用に最適化されたjava.util.Map実装について知っている人はいますか？
を通常の場所（Apacheのコモンズ、グーグル）に見ていないものを見つけることができました。
リンクリストに基づいてかなり探しています。ユースケースはマップの10'000ですが、必ずしも多くの値は入っていません。スケールアップする必要はありません。サイズが大きくなりすぎると変換できます。
いくつかの計算されたjvm値（8バイト/ java.lang.Object、4バイト/ ref）を使用するいくつかのサイズでは、HashMapは約100 + 32nバイトです。理論上の最良は12 + 20 * nです。 < - 私は小さいnのためにそれが欲しい。
OK]をクリックして、最後にそれを自分自身を実装しました。私は速度の比較を行い、HashMapと比較しても4つのエントリではやや速く、5つ以上では遅くなっていることがわかりました。私はランダムな英語の単語のリストと同様の構成をしようとしたキーの長いリストでテストを行いました。
import java.util.*;
// PUBLIC DOMAIN
public class SmallMap extends AbstractMap {
private Entry entry = null;
public void clear() { entry = null; }
public boolean isEmpty() { return entry==null; }
public int size() {
int r = 0;
for(Entry e = entry; e!=null; e = e.next) r++;
return r;
}
public boolean containsKey(Object key) {
for(Entry e = entry; e!=null; e = e.next){
if(e.key.equals(key)){
return true;
}
}
return false;
}
public boolean containsValue(Object value) {
for(Entry e = entry; e!=null; e = e.next){
if(e.value==null){
if(value==null) return true;
}else if(e.value.equals(value)){
return true;
}
}
return false;
}
public Object get(Object key) {
for(Entry e = entry; e!=null; e = e.next){
if(e.key.equals(key)){
return e.value;
}
}
return null;
}
public Object put(Object key, Object value) {
for(Entry e = entry; e!=null; e = e.next){
if(e.key.equals(key)){
Object r = e.value;
e.value = value;
return r;
}
}
entry = new Entry(key, value, entry);
return null;
}
public Object remove(Object key) {
if(entry!=null){
if(entry.key.equals(key)){
Object r = entry.value;
entry = entry.next;
return r;
}
for(Entry e = entry; e.next!=null; e = e.next){
if(key.equals(e.next.key)){
Object r = e.next.value;
e.next = e.next.next;
return r;
}
}
}
return null;
}
public Set entrySet() { return new EntrySet(); }
class EntrySet extends AbstractSet{
public Iterator iterator() {
return new Iterator(){
Entry last = null;
Entry e = entry;
public boolean hasNext() { return e!=null; }
public Object next() {
last = e;
e = e.next;
return last;
}
public void remove() {
if(last == null) throw new IllegalStateException();
SmallMap.this.remove(last.key);
}
};
}
public int size() { return SmallMap.this.size();}
}
static private class Entry implements java.util.Map.Entry {
final Object key;
Object value;
Entry next;
Entry(Object key, Object value, Entry next){
if(key==null) throw new NullPointerException();
this.key = key;
this.value = value;
this.next = next;
}
public Object getKey() { return key; }
public Object getValue() { return value; }
public Object setValue(Object value) {
Object r = this.value;
this.value = value;
return r;
}
public int hashCode() {
return (key == null ? 0 : key.hashCode())^
(value == null ? 0 : value.hashCode());
}
}
}
HashMap "m"はどこに使用されていますか？そして、クラスを集めない理由はありますか？ –
ああ、それは偶然にも残っています。私がそれを使用することを検討している場合を除いて、それを一般的にしない理由はありません。 –
単純に、JDKのHashMap、Hashtable、およびConcurrentHashMapのいずれかを、同期または並行性の要件に応じて使用することをお勧めします。 これらを使用する場合は、コンストラクタでinitialCapacityとloadFactorを適切に設定すると役立ちます。
GoogleのコレクションとApacheコモンコレクションでは、LRUMap、ReferenceMap、MultikeyMapなどの機能が追加されています。しかし、私は小さなサイズではないとは思わない。
私の質問は明確ではありませんでした。私はメモリ使用量が少ないことを意味しました。実際には、フラット3マップと呼ばれるアパッチコモンズに小さなサイズに最適化されたものがあります。 –
元のリクエストが「HashMapよりもメモリ効率の良い 'Mapの実装を教えてくれた」とき、それは基本的に（そしてひどく単純化された）「HashMap」と余分な間接的なレベル。だから、常に 'HashMap'よりも多くのメモリが必要です。それは間違った方向です。 –
LinkedHashMapはリンクされたリストを使用していますが、メモリー使用量が少なくなるように最適化されているかどうかは疑問です。通常、マップの全ポイントは、キーから値へのルックアップをスピードアップすることです。これは、なぜあなたが共通の場所で必要なものを見つけていないのかを説明します。 Mapの独自の実装を記述するのが最も簡単かもしれません。他の誰かが同じことを必要とする場合に備えて、コードをリリースすることさえできます。
マップの使用を隠すような方法でコードを記述します（あなたはそれをやっていなければなりませんし、あなたも同様です）。問題が発生した時点で、コードをプロファイリングしてメモリが実際に問題であることが分かるため、次のものを見つけてください：
問題が発生していることが分かっている場合は、私は1つを知らない。しかし、あまりにもしばしば人々は、コードが遅い/ seたくさんのメモリ/ etc ...となる "アイデア"を扱い、正しいコードを作るのではなく、それを前面に最適化しようとします。
しかし、もしあなたが何かを書いているのであれば、それが重要であることを知っていれば、あなたが行くように測定するべきだと言いました。たとえば、クラスファイルを解析するためのコードを作成しています。小さな変更を加えて、パフォーマンスにどのような影響を与えるかを確認します。例えば、私が行った変更（3行）によってプログラムが4倍遅くなったという事実を知っていました...私はその時点で時間を過ごして、それを行うより速い方法を見つけ出しませんでした。
また、「n」の値が小さい場合は地図が必要ですか？おそらくリストは十分に速いでしょうか？また、既存のMapを調整してメモリを少なくしてみましたか？
は、それは3つのフィールドでの3つの値を格納するために最適化され、4
私は実装を見ていないで、別のマップに溢れていコモンズ・コレクションFlat3Mapを見てもらえますが、について考えて価値があるかもしれません。問題は、commons-collectionsが1.3と互換性があるのでジェネリックはないということだけです。
MapインターフェイスでArrayListをラップします。 ArrayList自体は数バイトしか使用しません。各ノードには、キー用と値用の2つのポインタが必要です。逐次検索を使用して値を検索します。わずかなエントリーしかない限り、パフォーマンスはOKです[*]。これにより、多数の値を持つ少数の花瓶のために実際の地図を使用する余裕ができます。
*：地図の平均サイズは10です。今日のコンピュータでは、毎秒約1億のキーを比較できるため、各ルックアップは平均して5マイクロ秒未満です。
パフォーマンスが依然として悪い場合は、キーで配列をソートしてバイナリ検索を試みることができます。
これらのマップをどのように使用するかは、1回のショットで入力してからルックアップを行うことができるかによって大きく異なります（ファースト）。 ...
（私は、これは 速いあなたのニーズに十分ではないと思います）アレイ内のすべての要素を配置すると要素を見つけるためにスキャンを行うことであろうメモリの最小量を使用して実装
最初にすべての要素を知っていれば、あまりにも多くの衝突なしに良いハッシュ方法を選択することができます。
または多分あなたは遅い挿入時間を許可する場合は、TreeMapのを使用することができます...
たぶん、この答えは少し遅れているが、Javolutionプロジェクトを見てみましょう。埋め込みやリアルタイム環境用の多くのデータ構造の実装が含まれています。具体的には、FastMapクラスがあります。
それを見てみましょう...そのサイズは小さいので、それはあらかじめ割り当てられているため、ハッシュマップより悪いです。実際にはnが非常に大きいときにのみパフォーマンスが向上します。 –
だけString秒を保存する場合、http://code.google.com/p/flatmap
編集を見ては申し訳ありませんああ、私はその後、私のアドバイスを忘れて、あなたは小さな巨大ではないマップを探しています参照してください。
私はそれは古い質問ですが、おそらく誰かがさらなるアイデアを加えることができると思います。
NB：以下はだけは本当にユースケースの特定のサブセットのために理にかなって：要件は、（極端な場合にすべてのマップのキーの同じセット）キーの非常に重複セットが含まれている場合
非常に有効な解決方法は、マップに関してキーを「外部化」し、マップに値を配列内にのみ含めることができます。
実装はオーバーラップ係数に「構造的に」依存してはいけませんが、キーが重なり合うほど実装が優れています。期待通りに
私の実装の詳細はわかりませんが、キー（マップオブジェクトの外に保存されている）を値配列のインデックスに変換する適切なメカニズムを持つことが重要です。値配列はのままです、つまりマップに5つのマッピングが含まれている場合は長さが5です。
このようなすべてのマップのキーは、数字にマップされた別のマップにあるとします。それでは、数値と配列のインデックスを関連付ける方法が必要です。
申し訳ありませんが、これは十分に具体的ではありませんが、このアイデアは同時に面白くて簡単だと思っていました。
また、本質的に高い「キー重複」ユースケースに適していますが、それ自体が一般的です。インプリメンテーションの詳細によっては、オーバーラップが低すぎるとパフォーマンスの問題が発生する可能性があります。
リンクリストに基づくマップは「最小」とは思わない。私は、Entryオブジェクトなしで配列ベースで作成します（つまり、値は配列に直接格納されます）。これは、衝突が厄介になることを意味しますが、これを回避する方法があります。 –
先週、私はこのマップの実装を行いました（あなたのニーズに一人ではないので）。残念ながら、実装はオープンソースではありません。私はマップの必要なサイズを16（マップオブジェクトの場合）+ 16（配列の場合;切り上げた場合）+ 8 * 'size'（配列の内容の場合）に減らしました。静的メソッドのみを使用して配列を直接操作したい場合を除いて、取得できるメモリの最低使用量です。マップごとに別の16バイトを節約できます。しかし、その場合、 'Map'インタフェースの実装ではなくなります。 –