单链表清空后仍然消耗内存
Single linked list still consuming memory after emptied
对于一项作业，我们被要求使用单链表实现数据结构。
我的问题是，在添加项目然后删除它们之后，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。
最后使用调试器跳转，变量 deck 具有字段 first = null
和计数 = 0;
为什么会这样？甲板是空的，没有物品，但内存仍然像以前一样使用。
代码通过了所有正确性测试，但在内存测试中失败。
我还查看了分步调试器，并且正在做应该做的事情。
会不会是在 removeFirst() 中我没有将任何内容设置为 null 而只是将 first 分配为 first.next ？
编辑：这是内存测试的输出
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
编辑2：
// 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;
}
这是 removeFirst()
编辑 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);
}
}
Edit4：这些是内存限制
谢谢。
从我的测试看来，内存仍在分配中，但正在等待垃圾回收。 java.lang.Runtime class 有一些方法可以通知您有关内存使用情况的信息，还有一个静态方法 gc() 可以建议 运行 进行垃圾收集。这是一个额外的方法和对您的 main() class 的修改，可能会对您有所帮助：
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 class 和 运行 中的 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，分配后使用了 19MB。
释放Deque中的所有Node后立即没有任何变化！
不过，在 gc() 调用之后，请注意分配给堆的总内存没有改变，但现在所有内存都可以免费供其他 Java 对象使用。垃圾收集最终会发生——通常是在堆中没有足够的连续内存来满足 new 请求时。
正如我在评论中所说，我对添加到堆中的额外 14MB 左右没有返回到 OS 并不感到惊讶。如果您在 Windows 中使用任务管理器，该内存仍将被视为 "in use"。到 OS 获取内存是昂贵的，所以通常这样做只是为了扩展大块（在这种情况下，似乎约为 1500 万字节）并且只在 运行 结束时释放。不过，这是依赖于实现的行为，并且在不同的 JVM 上可能会有所不同。
关于您的代码的注释。我将节点 class 转换为：
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<Item>。这是应该的，因为节点项类型是通用的。这将同一份报告的内存使用量从 19MB 减少到 15MB。非静态内部 classes 将内部 class 的每个实例绑定到周围 class 的特定实例。你不需要那个，它会花费时间和内存。
该修复可能会帮助您通过测试。
哦，是的，请注意字段名称从 Next 更改为 next，从 Item 更改为 item。如果您想符合传统的 Java 命名风格，请以小写字母开头字段和方法名称。在任何情况下都不应将 Item 用于字段名称和通用类型名称。
对于一项作业，我们被要求使用单链表实现数据结构。
我的问题是，在添加项目然后删除它们之后，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。 最后使用调试器跳转，变量 deck 具有字段 first = null 和计数 = 0;
为什么会这样？甲板是空的，没有物品，但内存仍然像以前一样使用。
代码通过了所有正确性测试，但在内存测试中失败。
我还查看了分步调试器，并且正在做应该做的事情。
会不会是在 removeFirst() 中我没有将任何内容设置为 null 而只是将 first 分配为 first.next ？
编辑：这是内存测试的输出
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
编辑2：
// 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;
}
这是 removeFirst()
编辑 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);
}
}
Edit4：这些是内存限制
谢谢。
从我的测试看来，内存仍在分配中，但正在等待垃圾回收。 java.lang.Runtime class 有一些方法可以通知您有关内存使用情况的信息，还有一个静态方法 gc() 可以建议 运行 进行垃圾收集。这是一个额外的方法和对您的 main() class 的修改，可能会对您有所帮助：
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 class 和 运行 中的 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，分配后使用了 19MB。
释放Deque中的所有Node后立即没有任何变化！
不过，在 gc() 调用之后，请注意分配给堆的总内存没有改变，但现在所有内存都可以免费供其他 Java 对象使用。垃圾收集最终会发生——通常是在堆中没有足够的连续内存来满足 new 请求时。
正如我在评论中所说，我对添加到堆中的额外 14MB 左右没有返回到 OS 并不感到惊讶。如果您在 Windows 中使用任务管理器，该内存仍将被视为 "in use"。到 OS 获取内存是昂贵的，所以通常这样做只是为了扩展大块（在这种情况下，似乎约为 1500 万字节）并且只在 运行 结束时释放。不过，这是依赖于实现的行为，并且在不同的 JVM 上可能会有所不同。
关于您的代码的注释。我将节点 class 转换为：
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<Item>。这是应该的，因为节点项类型是通用的。这将同一份报告的内存使用量从 19MB 减少到 15MB。非静态内部 classes 将内部 class 的每个实例绑定到周围 class 的特定实例。你不需要那个，它会花费时间和内存。
该修复可能会帮助您通过测试。
哦，是的，请注意字段名称从 Next 更改为 next，从 Item 更改为 item。如果您想符合传统的 Java 命名风格，请以小写字母开头字段和方法名称。在任何情况下都不应将 Item 用于字段名称和通用类型名称。