StackOverflowException при сериализации двоичного дерева

Question

Я пытаюсь реализовать двоичное дерево для приложения Android и хочу иметь возможность сериализовать его в файл на устройстве.К сожалению, я получаю ошибки переполнения стека при попытке его сериализации.

Код:

class BTree<V extends Model> implements Serializable {
/**
 * 
 */
private static final long serialVersionUID = 4944483811730762415L;

private V value;
private BTree<V> left;
private BTree<V> right;

public BTree(V value) {
    this.value = value;
}

public BTree(V value, BTree<V> left, BTree<V> right) {
    this.value = value;
    this.left = left;
    this.right = right;
}

private int getValue() {
    return this.value.hashCode();
}

public void insert(BTree<V> node) {     
    if (this.getValue() >= node.getValue()) {
        if (this.left == null) {
            this.left = node;
        } else {
            this.left.insert(node);
        }
    } else {
        if (this.right == null) {
            this.right = node;
        } else {
            this.right.insert(node);
        }
    }
}

public boolean containsKey(Object key) {
    return this.find(key) != null;
}

public V find(Object key) {
    if (key.hashCode() == this.getValue()) {
        return this.value;
    } else if (key.hashCode() > this.getValue() && this.left != null) {
        return this.left.find(key);
    } else if (key.hashCode() < this.getValue() && this.right != null) {
        return this.right.find(key);
    } else {
        return null;
    }
}

public ArrayList<V> getAllValues() {
    ArrayList<V> values = new ArrayList<V>();
    if (this.left != null) {
        values.addAll(this.left.getAllValues());
    }
    if (this.right != null) {
        values.addAll(this.right.getAllValues());
    }

    return values;
}
}

И я пытаюсь сериализовать этот блок текста в отдельный класс:

try {           
        FileOutputStream fos = this.context.openFileOutput(FILE_NAME, Context.MODE_PRIVATE);
        ObjectOutputStream oos = new ObjectOutputStream(fos);
        oos.writeObject(this.tree);
        oos.close();

        //this.lastModified = getLastModified(FILE_NAME);
    } catch (FileNotFoundException e) {
        //File will get created, so this doesn't matter
    } catch (IOException e) {
        Log.d("BTreeModel Serialization Error", "Error serialization model.");
        Log.e("Serialization error details", e.toString());
    } 

Что я заметил, так это то, что если я сериализуюсь в файл, который в данный момент не существует, он сериализуется нормально.Второй раз, когда я запускаю ту же программу, она вызывает StackOverflowException при повторной сериализации на диск.

Вот вывод logcat:

09-07 05:29:42.011: ERROR/AndroidRuntime(916): FATAL EXCEPTION: main
09-07 05:29:42.011: ERROR/AndroidRuntime(916): java.lang.StackOverflowError
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at         java.util.IdentityHashMap.getModuloHash(IdentityHashMap.java:435)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.util.IdentityHashMap.findIndex(IdentityHashMap.java:419)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at     java.util.IdentityHashMap.get(IdentityHashMap.java:371)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.dumpCycle(ObjectOutputStream.java:471)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeObjectInternal(ObjectOutputStream.java:1739)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeObject(ObjectOutputStream.java:1689)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeObject(ObjectOutputStream.java:1653)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeFieldValues(ObjectOutputStream.java:1143)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.defaultWriteObject(ObjectOutputStream.java:413)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeHierarchy(ObjectOutputStream.java:1241)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeHierarchy(ObjectOutputStream.java:1205)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeNewObject(ObjectOutputStream.java:1575)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeObjectInternal(ObjectOutputStream.java:1847)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeObject(ObjectOutputStream.java:1689)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeObject(ObjectOutputStream.java:1653)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeFieldValues(ObjectOutputStream.java:1143)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.defaultWriteObject(ObjectOutputStream.java:413)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeHierarchy(ObjectOutputStream.java:1241)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeNewObject(ObjectOutputStream.java:1575)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeObjectInternal(ObjectOutputStream.java:1847)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeObject(ObjectOutputStream.java:1689)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeObject(ObjectOutputStream.java:1653)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeFieldValues(ObjectOutputStream.java:1143)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.defaultWriteObject(ObjectOutputStream.java:413)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeHierarchy(ObjectOutputStream.java:1241)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeNewObject(ObjectOutputStream.java:1575)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeObjectInternal(ObjectOutputStream.java:1847)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeObject(ObjectOutputStream.java:1689)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeObject(ObjectOutputStream.java:1653)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeFieldValues(ObjectOutputStream.java:1143)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.defaultWriteObject(ObjectOutputStream.java:413)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeHierarchy(ObjectOutputStream.java:1241)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeNewObject(ObjectOutputStream.java:1575)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeObjectInternal(ObjectOutputStream.java:1847)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeObject(ObjectOutputStream.java:1689)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeObject(ObjectOutputStream.java:1653)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeFieldValues(ObjectOutputStream.java:1143)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.defaultWriteObject(ObjectOutputStream.java:413)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeHierarchy(ObjectOutputStream.java:1241)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeNewObject(ObjectOutputStream.java:1575)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeObjectInternal(ObjectOutputStream.java:1847)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeObject(ObjectOutputStream.java:1689)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeObject(ObjectOutputStream.java:1653)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeFieldValues(ObjectOutputStream.java:1143)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.defaultWriteObject(ObjectOutputStream.java:413)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeHierarchy(ObjectOutputStream.java:1241)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeNewObject(ObjectOutputStream.java:1575)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeObjectInternal(ObjectOutputStream.java:1847)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeObject(ObjectOutputStream.java:1689)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeObject(ObjectOutputStream.java:1653)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeFieldValues(ObjectOutputStream.java:1143)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.defaultWriteObject(ObjectOutputStream.java:413)
09-07 05:29:42.011: ERROR/AndroidRuntime(916):     at java.io.ObjectOutputStream.writeHierarchy(ObjectOutputStream.j

Из действия, которое добавляет узлы:

public void onCreate(Bundle savedInstanceState) {
    super.onCreate(savedInstanceState);
    setContentView(R.layout.main);

    //TextView averageHashMapTime = (TextView)findViewById(R.id.averageHashCollectionTime);
    //averageHashMapTime.setText("Just a moment");
    //TextView averageBtreeTime = (TextView)findViewById(R.id.averageBTreeCollectionTime);
    //averageBtreeTime.setText("working");

    HashMapModelCollection<Integer, Content> hashCollection = new HashMapModelCollection<Integer, Content>(this);
    long totalTicks = 0;
    final int totalIterations = 16;

    BTreeModelCollection<Integer, Content> btreeCollection = new BTreeModelCollection<Integer, Content>(this);
    totalTicks = 0;
    for(int i = 0; i < totalIterations; i++) {
        Content test = new Content();
        test.setText(String.valueOf(i));
        Random r = new Random();
        int key = r.nextInt();
        Date start = new Date();
        btreeCollection.put(key, test);
        Date end = new Date();

        totalTicks += end.getTime() - start.getTime();
    }

    Log.d("Finished", "btree length: " + String.valueOf(totalTicks / totalIterations));
    Toast.makeText(this, "btree length: " + String.valueOf(totalTicks / totalIterations), Toast.LENGTH_LONG).show();
    //averageBtreeTime.setText(String.valueOf(totalTicks / totalIterations));

}

Класс, который непосредственно обрабатывает объекты BTree:

public class BTreeModelCollection<K extends Serializable, V extends Model> implements IModelCollection<K, V>,
    Serializable {


/**
 * 
 */
private static final long serialVersionUID = -3969909157515987705L;

private static final String FILE_NAME = "testCollection-5";

private BTree<V> tree;
private Context context;

public BTreeModelCollection(Context context) {
    this.context = context;
}

@Override
public void clear() {
    // TODO Auto-generated method stub

}

@Override
public boolean containsKey(Object key) {
    return tree.containsKey(key);
}

@Override
public boolean containsValue(Object value) {
    // TODO Auto-generated method stub
    return false;
}

@Override
public Set<java.util.Map.Entry<K, V>> entrySet() {
    // TODO Auto-generated method stub
    return null;
}

@Override
public V get(Object key) {
    return getTree().find(key);
}

@Override
public boolean isEmpty() {
    // TODO Auto-generated method stub
    return false;
}

@Override
public Set<K> keySet() {
    // TODO Auto-generated method stub
    return null;
}

@Override
public void put(K key, V value) {
    value.setKey(key);
    getTree();
    if (this.tree != null) {
        this.tree.insert(new BTree<V>(value));
    } else {
        this.tree = new BTree<V>(value);
    }
    serialize();
}

@Override
public V remove(Object key) {
    // TODO Auto-generated method stub
    return null;
}

@Override
public int size() {
    // TODO Auto-generated method stub
    return 0;
}

@Override
public Collection<V> values() {
    return getTree().getAllValues();
}

@Override
public void putAll(Map<? extends K, ? extends V> map) {
    // TODO Auto-generated method stub

}

private BTree<V> getTree() {
    if (this.tree == null) {
        loadTree();
    }

    return tree;
}

@SuppressWarnings("unchecked")
private void loadTree() {
    try {
        FileInputStream fis = context.openFileInput(FILE_NAME);
        ObjectInputStream ois = new ObjectInputStream(fis);
        this.tree = (BTree<V>)ois.readObject();
        ois.close();
    } catch (FileNotFoundException e) {
        this.tree = null;
    } catch (StreamCorruptedException e) {
        e.printStackTrace();
    } catch (IOException e) {
        this.tree = null;
    } catch (ClassNotFoundException e) {
        e.printStackTrace();
    } 
}

private void serialize() {
    if (this.tree == null) {
        Log.w("Serialization problem", "No collection to serialize to disk");
        return;
    }

    try {           
        FileOutputStream fos = this.context.openFileOutput(FILE_NAME, Context.MODE_PRIVATE);
        ObjectOutputStream oos = new ObjectOutputStream(fos);
        oos.writeObject(this.tree);
        oos.close();

        //this.lastModified = getLastModified(FILE_NAME);
    } catch (FileNotFoundException e) {
        //File will get created, so this doesn't matter
    } catch (IOException e) {
        Log.d("BTreeModel Serialization Error", "Error serialization model.");
        Log.e("Serialization error details", e.toString());
    } 
}

}

И класс Model:

public abstract class Model implements Serializable {

/**
 * 
 */
private static final long serialVersionUID = -5724152403115334006L;

private Serializable key;

void setKey(Serializable key) {
    this.key = key;
}

Serializable getKey() {
    return this.key;
}
}

Answer 1

Я получил копию вашей ошибки.Кажется, что Android не очень хорошо справляется с глубокой рекурсией, так как я пробовал ту же программу на рабочем столе, и она отлично работает с размером, который я пытаюсь.

Согласно обсуждению в комментарии, я выполнил альтернативную сериализациюэто не связано с рекурсией на уровень объекта.Определенно есть несколько способов сделать это, но я решил сериализовать структуру как String в формате данных JSON и записать ее в выходной поток.Обратите внимание, что я не проверил это полностью.Цель этого ответа - предложить подход, который вы, возможно, также могли бы использовать.

Теперь, предполагая, что мое значение равно int, я подумал, что структура JSON должна выглядеть так:

 { 
       root : {
           "value" : 8
           "left": {
                   "value" : 3
                   "left" : {
                       "value" : 1
                   }
               },
           "right" : {
               "value" : 10
               "right" : {
                   "value": 14
               }
           }
       }
   }

Теперь, следуя этой структуре, у меня есть методы для построения дерева в классе BTree:

    private JSONObject buildJSONObject(BTree  root) throws JSONException {
        JSONObject baseJSON = new JSONObject();
        JSONObject rootElement = new JSONObject();
        rootElement.put("value", root.getValue());
        baseJSON.put("root", rootElement);
        buildJSONObject(root, rootElement);
        return baseJSON;
    }

    private void buildJSONObject(BTree currentNode, JSONObject jsonElement) throws JSONException {
        jsonElement.put("value", currentNode.getValue());

        if(currentNode.left != null) {
            JSONObject leftJSON = new JSONObject();
            jsonElement.put("left", leftJSON);
            leftJSON.put("value", currentNode.left.getValue());
            buildJSONObject(currentNode.left, leftJSON);
        } 

        if (currentNode.right != null ){
            JSONObject rightJSON = new JSONObject();
            jsonElement.put("right", rightJSON);
            rightJSON.put("value", currentNode.right.getValue());
            buildJSONObject(currentNode.right, rightJSON);
        }
    }

Обратно, чтобы прочитать его обратно:

private void readJSONObject(String json) throws JSONException, IllegalAccessException, InstantiationException {
        JSONObject baseJSON = new JSONObject(json);
        JSONObject rootElement = baseJSON.getJSONObject("root");
        readJSONObject(this, rootElement);
    }

    private void readJSONObject(BTree btree, JSONObject jsonElement) throws JSONException, IllegalAccessException, InstantiationException {
        int nodeValue = jsonElement.getInt("value");
        btree.value.setKey(nodeValue);

        if(jsonElement.has("left")) {
            JSONObject leftJSON = jsonElement.getJSONObject("left");
            Model m = this.value.getClass().newInstance();
            this.left = new BTree((V) m); 
            readJSONObject(this.left, leftJSON);
        } 

        if (jsonElement.has("right")){
            JSONObject rightJSON = jsonElement.getJSONObject("right");
            V m = (V)this.value.getClass().newInstance();
            this.right = new BTree(m); 
            readJSONObject(this.right, rightJSON);
        }
    }

И, наконец, я применяю свою собственную сериализацию:

 private void writeObject(ObjectOutputStream oos)
    throws IOException {
        try {
            oos.defaultWriteObject();
            JSONObject root = buildJSONObject(this);
            oos.writeObject(root.toString());
            oos.writeObject(this.value);
        } catch(Exception e) {
            // handle exception
            throw new RuntimeException(e);
        }
    }

    // assumes "static java.util.Date aDate;" declared
    private void readObject(ObjectInputStream ois)
    throws ClassNotFoundException, IOException {
        ois.defaultReadObject();
        String jsonString = (String)ois.readObject();
        this.value = (V)ois.readObject();

        try {
            readJSONObject(jsonString);
        } catch (Exception e) {
            // handle exception
            throw new RuntimeException(e);
        }
    }

Answer 2

Вот код для исправленного класса, который решает проблему StackOverflowException. У него есть один критический недостаток: для несбалансированных деревьев это невероятно неэффективно, так как приходится многократно изменять размер внутреннего массива.

class BTree<V extends Model> implements Serializable {  
/**
 * 
 */
private static final long serialVersionUID = -7602392759811243945L;

private static final int MINIMUM_CAPACITY = 15;

private Model[] values;
private int depth = 3;

public void insert(V newValue) {    
    int index = 0;
    while(true) {           
        ensureSpotExists(index);

        Model value = values[index];
        if (value == null) {                
            values[index] = newValue;
            return;
        } else if (newValue.getKey().hashCode() < value.getKey().hashCode()) {
            index = (2 * index) + 1;
        } else if (newValue.getKey().hashCode() > value.getKey().hashCode()) {
            index = (2 * index) + 2;
        } else {
            values[index] = newValue;
            return;
        }
    }
}

protected void ensureSpotExists(int index) {
    if (this.values == null) {
        this.values = new Model[MINIMUM_CAPACITY];
    } else if (this.values.length < index + 1) {
        Model[] temp = this.values;
        this.values = new Model[getSize(++depth)];
        for(int i = 0; i < temp.length; i++) {
            this.values[i] = temp[i];
        }
    }
}

protected static int getSize(int depth) {
    int size = 0;
    for(int i = 0; i <= depth; i++) {
        size += Math.pow(2, i);
    }

    return size;
}

public boolean containsKey(Object key) {
    return this.find(key) != null;
}

public V find(Object key) {
    return null;
}

void replace(Object key, V value) {
    return;
}

public List<Model> getAllValues() {
    return Arrays.asList(this.values);
}  
}

Answer 3

Обычно это происходит, когда рекурсия не имеет правильного условия выхода.