有谁知道允许可变键的基于键的数据结构的任何实现或论文?
由于密钥正在发生变异,我不确定“密钥”是否是正确的术语,但我希望你能理解我的意思。
我想要这个的具体原因是能够尽可能高效地查找更改对象的邻居,而无需不断地对并行列表进行排序,不断地重构树或类似结构,或者当然在哈希图的完全崩溃时处理它键发生了变异。
一个快速、非常简单的用法示例是(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.
因此,理想情况下,这种数据结构将允许映射提供的优雅(如果可能的话,速度)用于访问集合中相对于另一个元素的其他元素,同时允许访问元素的那些值发生变化。
我意识到这可能是在要求一个“完美”的数据结构,但我真的只是对这种类型的数据结构上存在什么或人们有什么想法感兴趣。