Understanding Effective Java deep copy example

Question

In Effective Java, 2nd Edition, Item 11 one can find the following deep copy example:

public class HashTable implements Cloneable {
    private Entry[] buckets = ...;

    private static class Entry {
        final Object key;
        Object value;
        Entry next;
        Entry(Object key, Object value, Entry next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }

        // Recursively copy the linked list headed by this Entry
        Entry deepCopy() {
            return new Entry(key, value,
                    next == null ? null : next.deepCopy());
        }
    }
    @Override public HashTable clone() {
        try {
            HashTable result = (HashTable) super.clone();
            result.buckets = new Entry[buckets.length];
            for (int i = 0; i < buckets.length; i++)
                if (buckets[i] != null)
                    result.buckets[i] = buckets[i].deepCopy();
            return result;
        } catch (CloneNotSupportedException e) {
            throw new AssertionError();
        }
    }

I don't understand how this makes a deep copy: key and value are objects, therefore no primitive types. So to my understanding, using

// Recursively copy the linked list headed by this Entry
Entry deepCopy() {
    return new Entry(key, value,
            next == null ? null : next.deepCopy());
}

creates a new Entry with a reference to the key and value of the original Entry?

Doesn't a deep copy basically mean: go down until one reaches primitive types, then copy those to the clone?

Thanks for any hint on this!

Answer 1

It's a "deep copy" in that changes to the original object's linked list (via next) will not be seen in the copy or vice versa. Compare that with the "shallow copy" which would be taken if the new object just copied the original next reference.

It's a shallow copy in terms of the key and value though - if those are mutable types and are mutated then yes, the mutation will be seen via both the original and the "cloned" version.

So ultimately, it's a deeper copy than the naive "copy all references" approach - but it's not a fully deep copy.

Answer 2

When you create a deep copy, it is not enough to have the "same" entries in the new HashTable. You must create new instances for each of those entries. Otherwise, each table will hold a reference to the same entry object. Then, when someone modifies a value in the first table, it will also be modified in the secon table (the new copy).