Do anonymous classes *always* maintain a reference to their enclosing instance?

Yes, instances of anonymous inner classes hold on to a reference to their enclosing instances even if these references are never actually used. This code:

public class Outer {
  public Runnable getRunnable() {
    return new Runnable() {
      public void run() {
        System.out.println("hello");
      }
    };
  }
}

When compiled with javac generates two class files, Outer.class and Outer$1.class. Disassembling the latter, the anonymous inner class, with javap -c yields:

Compiled from "Outer.java"
class Outer$1 extends java.lang.Object implements java.lang.Runnable{
final Outer this$0;

Outer$1(Outer);
  Code:
   0:   aload_0
   1:   aload_1
   2:   putfield        #1; //Field this$0:LOuter;
   5:   aload_0
   6:   invokespecial   #2; //Method java/lang/Object."<init>":()V
   9:   return

public void run();
  Code:
   0:   getstatic       #3; //Field java/lang/System.out:Ljava/io/PrintStream;
   3:   ldc     #4; //String hello
   5:   invokevirtual   #5; //Method java/io/PrintStream.println:(Ljava/lang/String;)V
   8:   return

}

The putfield line shows that a reference to the enclosing instance is being stored in the field this$0 (of type Outer) by the constructor even though this field is never used again.

This is unfortunate if you're attempting to create small potentially long-lived objects with anonymous inner classes as they'll hold onto the (potentially large) enclosing instance. A workaround is to use an instance of a static class (or a top-level class) instead. This is unfortunately more verbose.

You can easily turn a nested anonymous-class into a "static" anonymous-class by introducing a static method in your class.

import java.util.ArrayList;


public class TestGC {
    public char[] mem = new char[5000000];
    public String str = "toto";

    public interface Node {
        public void print();
    }

    public Node createNestedNode() {
        final String str = this.str;
        return new Node() {
            public void print() {
                System.out.println(str);
            }
        };
    }

    public static Node createStaticNode(TestGC test) {
        final String str = test.str;
        return new Node() {
            public void print() {
                System.out.println(str);
            }
        };
    }

    public Node createStaticNode() {
        return createStaticNode(this);
    }

    public static void main(String... args) throws InterruptedException {
        ArrayList<Node> nodes = new ArrayList<Node>();
        for (int i=0; i<10; i++) {
            // Try once with createNestedNode(), then createStaticNode()
            nodes.add(new TestGC().createStaticNode());
            System.gc();
            //Thread.sleep(200);
            System.out.printf("Total mem: %d  Free mem: %d\n", Runtime.getRuntime().totalMemory(), Runtime.getRuntime().freeMemory());
        }
        for (Node node : nodes)
            node.print();
        nodes = null;
        System.gc();
        //Thread.sleep(200);
        System.out.printf("Total mem: %d  Free mem: %d\n", Runtime.getRuntime().totalMemory(), Runtime.getRuntime().freeMemory());
    }
}

The static alternative (in this case) is not much larger (1 line):

public class Outer {
  static class InnerRunnable implements Runnable {
      public void run() {
        System.out.println("hello");
      }
    }
  public Runnable getRunnable() {
    return new InnerRunnable();
  }
}

BTW: if you use a Lambda in Java8 there will be no nested class generated. However I am not sure if the CallSite objects which get passed around in that case hold an reference to the outer instance (if not needed).