変更可能なキーを許可するキーベースのデータ構造の実装または論文を知っている人はいますか?
キーが変異しているので、「キー」という用語が正しいかどうかはわかりませんが、私の意味を理解していただければ幸いです。
これが必要な特定の理由は、並列リストを常にソートしたり、ツリーまたは同様の構造を常に再構築したり、もちろんハッシュマップの完全な崩壊に対処したりする必要なく、オブジェクトを変更するための可能な限り効率的な近隣ルックアップを実行できるようにすることです。キーが変異しています。
簡単で非常に単純な使用例は次のようになります (Java HashMap 構文):
MutableKeyMap<Point, String> m = new MutableKeyMap<Point, String>();
Point p = new Point(5, 6)
m.put(p, "foo");
Point o = new Point(6, 6);
m.put(o, "bar");
// The points are currently neighbors, so
m.get(new Point(o.x - 1, o.y)); // returns "foo".
m.get(new Point(p.x + 1, p.y)); // returns "bar"
// Now here is where most data structures fall apart without some reworking
o.y += 1;
m.get(new Point(o.x - 1, o.y - 1)); // Still returns "foo" because the point "foo" is mapped to has not changed
m.get(new Point(p.x + 1, p.y)); // returns null, as to be expected because o would no longer map to there
m.get(new Point(p.x + 1, p.y + 1)); // A hash map would return null here as well when it should return "bar",
// because the data structure cannot account for the identity-changing mutation of the key.
m.get(o); // even returns null because of this in a hash map.
// Therefore we have effectively deleted the entry. In this data structure the idea would be to maintain this link despite the mutation.
したがって、理想的には、このデータ構造は、別の要素に関してセット内の他の要素にアクセスするためのマップによって提供されるエレガンス (および可能であれば速度) を可能にし、要素へのアクセスに使用される値を変更できるようにします。
これはおそらく「完璧な」データ構造を求めていることは承知していますが、このタイプのデータ構造に何が存在するか、または人々が持っているアイデアに本当に興味があります。