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。