Java中的持久数据结构

Question

有没有人知道一个库或至少一些关于在Java中创建和使用持久化数据结构的研究？我并没有将持久性称为长期存储，而是将其作为长期存储（参见Wikipedia entry）。

我目前正在探索不同的方式来建模持久性结构的api。使用建设者似乎是一个有趣的解决方案：

// create persistent instance 
Person p = Builder.create(Person.class) 
      .withName("Joe") 
      .withAddress(Builder.create(Address.class) 
       .withCity("paris") 
       .build()) 
       .build(); 

// change persistent instance, i.e. create a new one 
Person p2 = Builder.update(p).withName("Jack"); 

Person p3 = Builder.update(p) 
       .withAddress(Builder.update(p.address()) 
       .withCity("Berlin") 
       .build) 
      .build(); 

但这仍然感觉有些boilerplated。有任何想法吗？

Answer 1

我想最明显的选择是：

O键的更新瞬时数据结构（制造商）。这很正常。例如StringBuilder代表String操作。作为你的榜样。

​​

o始终使用持久性结构。虽然似乎有很多复制，但实际上你应该共享几乎所有的状态，所以它看起来并没有那么糟糕。

final Person p3 = p 
    .withAddress(
     p.address().withCity("Berlin") 
    ); 

o将数据结构分解为许多变量，并用一个庞大而混乱的构造函数重新组合。

final Person p3 = Person.of(
    p.name(), 
    Address.of(
     p.house(), p.street(), "Berlin", p.country() 
    ), 
    p.x(), 
    p.y(), 
    p.z() 
); 

o使用回呼接口提供新数据。更多的样板。

final Person p3 = Person.of(new PersonInfo(
    public String name () { return p.name();) 
    public Address address() { return Address.of(new AddressInfo() { 
     private final Address a = p.address(); 
     public String house () { return a.house() ; } 
     public String street() { return a.street() ; } 
     public String city () { return "Berlin" ; } 
     public String country() { return a.country(); } 
    })), 
    public Xxx  x() { return p.x(); } 
    public Yyy  y() { return p.y(); } 
    public Zzz  z() { return p.z(); } 
}); 

o使用讨厌的黑客，使场短暂的代码可用。

final Person p3 = new PersonExploder(p) {{ 
    a = new AddressExploder(a) {{ 
     city = "Berlin"; 
    }}.get(); 
}}.get(); 

（有趣的是，我只是克里斯·奥卡萨基放下纯功能性数据结构的副本。）

Answer 2

这是非常困难的，如果不是不可能的，让事情一成不变未设计成。

如果能够从地面向上设计：

• 只使用final字段
• 不引用非不可变对象

Answer 3

建设者将会使你的代码太冗长是可用的。实际上，我所看到的几乎所有不可变数据结构都通过构造函数传入状态。对于什么样的价值，这里是一个不错的一系列描述C＃一成不变的数据结构的职位（这应该很容易转换成Java）：

• Part 1: Kinds of Immutability
• Part 2: Simple Immutable Stack
• Part 3: Covariant Immutable Stack
• Part 4: Immutable Queue
• Part 5: Lolz! （包括完整性）
• Part 6: Simple Binary Tree
• Part 7: More on Binary Trees
• Part 8: Even More on Binary Trees
• Part 9: AVL Tree Implementation
• Part 10: Double-ended Queue
• Part 11: Working Double-ended Queue Implementation

C＃和Java是非常详细的，所以在这些文章中的代码是相当可怕的。我建议学习OCaml，F＃或Scala，并熟悉这些语言的不变性。一旦掌握了技巧，您就可以更容易地将相同的编码风格应用于Java。

Answer 4

你想不变性：

1. 所以外部代码不能改变的数据？
2. 所以一旦设置了一个值不能改变？

在这两种情况下，都有更简单的方法来实现所需的结果。

从改变数据停止外部代码是易与接口：

public interface Person { 
    String getName(); 
    Address getAddress(); 
} 
public interface PersonImplementor extends Person { 
    void setName(String name); 
    void setAddress(Address address); 
} 

public interface Address { 
    String getCity(); 
} 


public interface AddressImplementor { 
    void setCity(String city); 
} 

然后停止更改一次设定的值也被“容易”的使用java.util.concurrent.atomic.AtomicReference中（尽管休眠或者一些其他的持久层的使用可能需要修改）：

class PersonImpl implements PersonImplementor { 
    private AtomicReference<String> name; 
    private AtomicReference<Address> address; 

    public void setName(String name) { 
     if (!this.name.compareAndSet(name, name) 
      && !this.name.compareAndSet(null, name)) { 
      throw new IllegalStateException("name already set to "+this.name.get()+" cannot set to "+name); 
     } 
    } 
    // .. similar code follows.... 
} 

但是，为什么你有什么需要的不仅仅是接口来完成任务？

Answer 5

看一看Functional Java。目前提供持续的数据结构包括：

• 单链表（fj.data.List）
• 懒单链表（fj.data.Stream）
• 非空目录（fj.data.NonEmptyList）
• 可选值（长度为0的容器或1）（fj.data.Option）
• 集（fj.data.Set）
• 多路树（又名玫瑰树）（fj.data.Tree ）
• 不可变映射（fj.data.TreeMap）
• arity 1-8（fj.P1 ..）的产品（元组）P8）
• 载体元数2-8（fj.data.vector.V2..V8的）
• 尖列表（fj.data.Zipper）
• 尖树（fj.data.TreeZipper）
• 类型安全的，通用的异构列表（fj.data.hlist.HList）
• 永恒阵列（fj.data.Array）
• 不交的数据类型（fj.data.Either）

一些使用示例随二进制分发提供。来源可从Google Code获得BSD许可证。

Answer 6

按照与动态代理一个非常简单的试探：

class ImmutableBuilder { 

    static <T> T of(Immutable immutable) { 
     Class<?> targetClass = immutable.getTargetClass(); 
     return (T) Proxy.newProxyInstance(targetClass.getClassLoader(), 
      new Class<?>[]{targetClass}, 
      immutable); 
    } 

    public static <T> T of(Class<T> aClass) { 
     return of(new Immutable(aClass, new HashMap<String, Object>())); 
    } 
} 

class Immutable implements InvocationHandler { 

    private final Class<?> targetClass; 
    private final Map<String, Object> fields; 

    public Immutable(Class<?> aTargetClass, Map<String, Object> immutableFields) { 
     targetClass = aTargetClass; 
     fields = immutableFields; 
    } 

    public Object invoke(Object proxy, Method method, Object[] args) throws Throwable { 
     if (method.getName().equals("toString")) { 
      // XXX: toString() result can be cached 
      return fields.toString(); 
     } 

     if (method.getName().equals("hashCode")) { 
      // XXX: hashCode() result can be cached 
      return fields.hashCode(); 
     } 

     // XXX: naming policy here 
     String fieldName = method.getName(); 

     if (method.getReturnType().equals(targetClass)) { 
      Map<String, Object> newFields = new HashMap<String, Object>(fields); 
      newFields.put(fieldName, args[0]); 
      return ImmutableBuilder.of(new Immutable(targetClass, newFields)); 
     } else { 
      return fields.get(fieldName); 
     } 
    } 

    public Class<?> getTargetClass() { 
     return targetClass; 
    } 
} 

用法：

interface Person { 
    String name(); 
    Person name(String name); 
    int age(); 
    Person age(int age); 
} 

public class Main { 

    public static void main(String[] args) { 
     Person mark = ImmutableBuilder.of(Person.class).name("mark").age(32); 
     Person john = mark.name("john").age(24); 
     System.out.println(mark); 
     System.out.println(john); 
    } 
} 

成长方向：

• 命名策略（的getName，withName，名）
• 缓存toString（），hashCode（）
• equals（）方法的实现应该是简单（虽然未实现）

希望它能帮助:)

Answer 7

我实现了几个持久数据结构在Java中。谁是有兴趣在谷歌代码全部开源（GPL）的人：

http://code.google.com/p/mikeralib/source/browse/#svn/trunk/Mikera/src/mikera/persistent

主要体会我到目前为止有：

• 持续可变测试对象
• 持续哈希映射
• 持久性向量/列表
• 持久集（包括专门的持久性整数集）

Answer 8

谷歌番石榴现在举办各种immutable/persistent data structures。