清空[重复]后，单个链表仍在消耗内存

Question

在一次作业中，我们被要求使用单链表实现一个数据结构。

我的问题是，在添加项目然后删除它们之后，java程序仍然使用与以前相同的内存。

这里有一个简单的例子

Deque<Integer> deck = new Deque<>();
for( int i =0; i < 500000;i++) {
    deck.addFirst(i);
}

for( int i =0; i < 500000;i++) {
    deck.removeFirst();
}
System.out.println("end"); //Debugger here

添加50万个项目需要27mb内存。移除后，仍为27mb。在末尾使用调试器跳转，变量组的字段first=null，count=0；

为什么会这样？甲板是空的，没有任何项目，但内存仍像以前一样使用。

代码通过了所有的正确性测试，但是没有通过内存测试。

我还查看了分步调试器，并正在做应该做的事情。

可能是因为在removeFirst（）中，我没有将任何内容设置为null，只将first赋值为first。下一个

编辑：这是内存测试的输出

 Test 10: Total memory usage after inserting 4096 items, then successively
     deleting items, seeking values of n where memory usage is maximized
     as a function of n

               n        bytes
    ---------------------------------------------------
  => passed     3200        65592         
  => passed     1600        65592         
  => FAILED      800        65592   (1.7x)
  => FAILED      400        65592   (3.4x)
  => FAILED      200        65592   (6.7x)
  => FAILED      100        65592  (13.1x)
  => FAILED       50        65592  (25.3x)
  ==> 2/7 tests passed

如您所见，在50个元素仍在使用65592

第二版:

// remove and return the item from the front
public Item removeFirst() {
    if (this.isEmpty()) throw new java.util.NoSuchElementException();
    Item current = first.Item;
    first = first.Next;
    count--;
    return current;
}

这是删除第一（）

编辑3：

import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.concurrent.TimeUnit;

/**
 * Created by Alex on 6/30/2018.
 */

public class Deque<Item> implements Iterable<Item> {

    private Node first;

    private int count;

    private class Node {
        private Node Next;
        private Item Item;
    }

    // construct an empty deque
    public Deque() {
        first = null;
        count = 0;
    }

    // is the deque empty?
    public boolean isEmpty() {
        if (count == 0) {
            return true;
        }
        return false;
    }

    // return the number of items on the deque
    public int size() {
        return count;
    }

    // add the item to the front
    public void addFirst(Item item) {
        if (item == null) throw new IllegalArgumentException();
        Node temp = new Node();
        temp.Item = item;
        temp.Next = first;
        first = temp;
        count++;
    }

    // add the item to the end
    public void addLast(Item item) {
        if (item == null) throw new IllegalArgumentException();
        if (isEmpty()) {
            addFirst(item);
        } else {
            Node last = first;
            while (last.Next != null) {
                last = last.Next;
            }
            Node newLast = new Node();
            newLast.Item = item;
            newLast.Next = null;
            last.Next = newLast;
            count++;
        }
    }

    // remove and return the item from the front
    public Item removeFirst() {
        if (this.isEmpty()) throw new java.util.NoSuchElementException();
        Item current = first.Item;
        first = first.Next;
        count--;
        return current;
    }

    // remove and return the item from the end
    public Item removeLast() {
        if (isEmpty()) throw new java.util.NoSuchElementException();
        if (size() == 1) {
           return removeFirst();
        }else {
            Node newLast = first;
            Node oldLast = first;
            while (oldLast.Next != null) {
                newLast = oldLast;
                oldLast = oldLast.Next;
            }
            newLast.Next = null;
            count--;
          //  Item lastItem = ;
            return oldLast.Item;
        }
    }

    // return an iterator over items in order from front to end
    public Iterator<Item> iterator() {
        return new DequeIterator();
    }

    private void debug() {
        Iterator<Item> deckIter = iterator();
        while(deckIter.hasNext()) {
            System.out.println(deckIter.next());
        }
        System.out.println(isEmpty());
        System.out.println("Size:" + size());
    }

    // an iterator, doesn't implement remove() since it's optional
    private class DequeIterator implements Iterator<Item> {
        private Node current = first;
        public boolean hasNext()  { return current != null;                     }
        public void remove()      { throw new UnsupportedOperationException();  }

        public Item next() {
            if (!hasNext()) throw new NoSuchElementException();
            Item item = current.Item;
            current = current.Next;
            return item;
        }
    }

    // unit testing (optional)
    public static void main(String[] args) throws InterruptedException {
        Deque<Integer> deck = new Deque<>();

        for( int i =0; i < 500000;i++) {
            deck.addFirst(i);
        }

        for( int i =0; i < 500000;i++) {
            deck.removeFirst();
        }
        System.out.println("end");
        TimeUnit.MINUTES.sleep(5);
    }
}

编辑4:这些是内存限制

https://imgur.com/nQuDfUF

谢谢你。

Answer 1

从我的测试来看，内存似乎仍在分配中，但正在等待垃圾回收机制。java.lang.Runtime类有一些方法来通知您内存使用情况，还有一个静态方法gc（）来建议运行垃圾回收。这里有一个额外的方法和对main（）类的修改可能会对您有所帮助：

private final static long MB = 1024*1024;
static void memStats(String when)
{
    Runtime rt = Runtime.getRuntime();
    long max = rt.maxMemory();
    long tot = rt.totalMemory();
    long free = rt.freeMemory();
    System.out.printf(
        "mem(mb): %5d tot, %5d free %5d used %5d max %s\n",
         tot/MB, free/MB, (tot-free)/MB, max/MB, when);
}

// unit testing (optional)
public static void main(String[] args) {
    Deque<Integer> deck = new Deque<>();
    memStats("startup");
    for( int i =0; i < 500000;i++) {
        deck.addFirst(i);
    }
    memStats("after alloc");

    for( int i =0; i < 500000;i++) {
        deck.removeFirst();
    }
    memStats("after removal");
    Runtime.getRuntime().gc();
    memStats("after gc");

    System.out.println("end");
    try {
        TimeUnit.MINUTES.sleep(5);
    } catch (InterruptedException ex)
    {
    }
}

将这些替换为Deque类中的main（）并运行它。我得到：

mem(mb):    15 tot,    15 free     0 used   247 max startup
mem(mb):    29 tot,    10 free    19 used   247 max after alloc
mem(mb):    29 tot,    10 free    19 used   247 max after removal
mem(mb):    29 tot,    29 free     0 used   247 max after gc
end

如您所见，（1）分配给Java的内存从分配给Java对象的总内存15MB开始，使用了0MB。（忽略max数字。这并没有报告我认为它做了什么。）它增加到29MB，分配后使用了19个。

在释放Deque中的所有节点s后，没有任何变化！

不过，在gc（）调用之后，请注意，分配给堆的总内存没有改变，但现在所有内存都可以供其他Java对象使用。垃圾收集最终会发生，通常是在堆中没有足够的连续内存来满足新请求时。

正如我在评论中所说的，我对添加到堆中的大约14MB没有返回到操作系统中并不感到惊讶。如果您在Windows中使用任务管理器，该内存仍将被视为“正在使用”。向操作系统获取内存是很昂贵的，所以通常只在大块扩展时才这样做(在这种情况下，似乎是1500万字节)，并且只在运行结束时释放。不过，这是依赖于实现的行为，在不同的JVM上可能会有所不同。

关于您的代码的注释。我将节点类转换为:

private static class Node<Item> {
    Node<Item> next; // lowercase next
    Item item; // You were using Item for both a type and field name!?
}

…并几乎将每次出现的Node转换为Node

这个补丁可能会帮助你通过测试。

哦，是的，请注意字段名从Next到next和Item到item的变化。如果您想适合传统的Java命名样式，请以小写字母开头字段和方法名称。在任何情况下，您都不应该同时使用Item作为字段名和泛型类型名。