浅谈一下java API设法的一个错误带来的后果引以为戒

java从出台以来有十二年的历史了，我们从未知到现在被广大程序员所接受 正是说明了它有其存在与发展的空间
但是人无完人 java在设计上也有自身的缺点，举个例子：从API里可以看到java.util.Stack类，stack 的特点是后进先出 且不能查找 array的特点是易于查找但是增删比较难
这个一般的程序员都很清楚 这个类是java.util.Vector的子类，Vector底层实现是用array且线程安全，这就与statck本身的特点不符合，再者由于是继承，stack就会将父类的所有方法都继承过来
如：add(int index,E element)这与stack是根本就不能实现的 但是SUN公司对于这个错误是没办法挽回了 以至于这个错误就一直错了十多年 最后SUN公司给出的解释就是不要轻易用这个类
从这件小事上来说明 一个设计者小小的失误对代码或者一个应用会起到为意想不到的结果 所以我们要努力再努力去完善自己

评论

20 楼 sunsy 2007-07-25  

那大家是否介绍几种比较好的stack实现。

19 楼 小玩子 2007-07-25  

好激烈的争论啊 不过就喜欢这种气氛

18 楼 JAVA_ED 2007-07-25  

netpcc 写道

1.C++ stl 里stack的实现类是可以通过第二个模板参数选择的。并非一定是deque。
2.C++的数据结构通常保存Value，而不是Reference。这样的话（a）Copy的成本比较高，（b）vector要求连续内存，所以对于size比较大的Value，以及大数据量不适合。而java只能是Reference，所以Copy的成本并不高。
3.我想说明的是做为stack的底层结构，vector比linkedlist好，不是和deque做比较。通常deque比vector更适合。但有些情况vector更好。但是我找不出来在什么情况下linkedlist比较好。
4.我的前提条件是对stack的push和pop的操作次数远大于stack的最大元素数量的情况。也就是不停的push和pop。这是stack的典型情况。
5.能不能具体说说把vector的methods暴露出来有什么缺点。

对于CPP的情况 你可以GOOGLE一下
JAVA的vector暴露了本不应该属于其具有的API

17 楼 netpcc 2007-07-24  

1.C++ stl 里stack的实现类是可以通过第二个模板参数选择的。并非一定是deque。
2.C++的数据结构通常保存Value，而不是Reference。这样的话（a）Copy的成本比较高，（b）vector要求连续内存，所以对于size比较大的Value，以及大数据量不适合。而java只能是Reference，所以Copy的成本并不高。
3.我想说明的是做为stack的底层结构，vector比linkedlist好，不是和deque做比较。通常deque比vector更适合。但有些情况vector更好。但是我找不出来在什么情况下linkedlist比较好。
4.我的前提条件是对stack的push和pop的操作次数远大于stack的最大元素数量的情况。也就是不停的push和pop。这是stack的典型情况。
5.能不能具体说说把vector的methods暴露出来有什么缺点。

16 楼 JAVA_ED 2007-07-24  

netpcc 写道

小玩子 写道

或者用Linkedlist也可以嘛
就是不知道为啥要选用vector

用Linkedlist实现stack完全没有道理。
stack只能从一头增删数据。如果不考虑shink和海量数据的话，vector还是很适合的。

linkedlist辅助空间极大，而且添加删除也比较慢。并不适合用来实装stack.

另外C++的STL的STACK的内部存储结构是可选的。并不局限于deque。

为什么CPP里用dequeue而不用vector
因为用Vector有个无法逃避的问题
当size大于预先分配时 会首先申请空间 然后拷贝构造
再释放原有空间
如果你的stack确定大小 的确可以自定义你自己的stack实现

vector的优点在于平均时间复杂度最小
看看STL的代码
Dequeue:

void  push_back(const value_type& __x)
      {
	if (this->_M_impl._M_finish._M_cur != this->_M_impl._M_finish._M_last - 1)
	  {
	    std::_Construct(this->_M_impl._M_finish._M_cur, __x);
	    ++this->_M_impl._M_finish._M_cur;
	  }
	else
	  _M_push_back_aux(__x);
      }

List:

void  push_back(const value_type& __x)
      { this->_M_insert(end(), __x); }

Vector:

void
      push_back(const value_type& __x)
      {
	if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
	  {
	    std::_Construct(this->_M_impl._M_finish, __x);
	    ++this->_M_impl._M_finish;
	  }
	else
	  _M_insert_aux(end(), __x);
      }

_M_insert_aux(end(), __x) 是个很费力气的函数 会分配内存再copy再插入
所以用Dequeue虽然不是最优 但还是适合普遍情况

JAVA里为什么不适合用vector 就是LZ说的原因

Vector is poor choice for stack implementation as all Vector methods are accessible
http://72.14.235.104/search?q=cache:c2JsFWrru2UJ:higheredbcs.wiley.com/legacy/college/koffman/0471467561/ppt/ch05.ppt+stack+linkedlist+or+vector&hl=en&ct=clnk&cd=16&gl=sg

15 楼 netpcc 2007-07-23  

jindw 写道

netpcc 写道

首先，辅助空间的消耗是按照空间复杂度来计算的。vector的情况比较复杂，但是通常可以按照O（1）来计算。而linkedlist是O(n)。

这个你还是看一下JDK源码再说吧。

我看了一下JDK1.5的源代码，没什么太大的问题。我已经说过了，vector的空间复杂度比较复杂，确实有可能比linkedlist大。按照JDK1.5的实现，按照O（1）计算可能不太合理，但是平均情况是linkedlist的1/4（linkedlist是双向链表）。如果开放出Vector(int initialCapacity, int capacityIncrement)构造函数或者从Ｓｔａｃｋ在继承一下，修改capacityIncrement的话，空间复杂度几乎就是Ｏ（１）了。但是Ｐｕｓｈ的时间复杂度会上升。
如有疑义，请详细说明。

jindw 写道

netpcc 写道

第三，linkedlist才会在Pop,push中反复分配，清理每个节点。vector的情况要好得多。

也是，但是相对于vector那样可能整个数组的从新分配、复制、清理，要好的多。小块的内存声请开销更低。

同上，反复Pop,Push中，vector并没有反复分配内存。
对于最大size是n，Pop/Push m次的情况来说，基于vector的stack。内存的分配次数为O(log (n))。和Pop/push次数无关。
linkedlist的内存分配次数为O(m)。
m>=n,且通常m远大于n。孰优孰劣很清楚了。
如有疑义，详细说明。

jindw 写道

netpcc 写道

第四，对于JAVA这样的纯引用Stack来说，vector在绝大多数情况下是最优解。

就凭Vector的同步特征，就可以让它在很多情况下被剔除出局。

如果是同步的问题的话，应该引入非同步的vector，比如ArrayList。

jindw 写道

netpcc 写道

第五，不存在一种数据结构在所有情况中都是最优的。C++大量使用value stack，所以deque适用于大多数情况。Java只有Reference stack，选择vector没有任何问题。而linked list只在极少数极端情况才适用。

不觉得，只要没有随机访问的需求，看不出linked list的致命缺陷。

linked list每次Push/Pop都要重新分配内存这点已经够致命了，而且还有巨大辅助空间的消耗。

14 楼 jindw 2007-07-23  

netpcc 写道

首先，辅助空间的消耗是按照空间复杂度来计算的。vector的情况比较复杂，但是通常可以按照O（1）来计算。而linkedlist是O(n)。

这个你还是看一下JDK源码再说吧。

netpcc 写道

第二，我已经说明过是在不考虑Shrink的情况。绝大多数stack是不shrink的，并且对于java来说Shrink的成本并不是很高。虽然时间复杂度是O(n)，但是常数非常小。

不懂

netpcc 写道

第三，linkedlist才会在Pop,push中反复分配，清理每个节点。vector的情况要好得多。

也是，但是相对于vector那样可能整个数组的从新分配、复制、清理，要好的多。小块的内存声请开销更低。

netpcc 写道

第四，对于JAVA这样的纯引用Stack来说，vector在绝大多数情况下是最优解。

就凭Vector的同步特征，就可以让它在很多情况下被剔除出局。

netpcc 写道

第五，不存在一种数据结构在所有情况中都是最优的。C++大量使用value stack，所以deque适用于大多数情况。Java只有Reference stack，选择vector没有任何问题。而linked list只在极少数极端情况才适用。

不觉得，只要没有随机访问的需求，看不出linked list的致命缺陷。

netpcc 写道

讨论数据结构及算法时，请不要泛泛而谈。“几个”，“未必”这样的词不能说明任何问题。具体说明时间复杂度和空间复杂度才有说服力。

我是经验主义，仅供参考，不想去说服每一个人。

13 楼 netpcc 2007-07-23  

首先，辅助空间的消耗是按照空间复杂度来计算的。vector的情况比较复杂，但是通常可以按照O（1）来计算。而linkedlist是O(n)。

第二，我已经说明过是在不考虑Shrink的情况。绝大多数stack是不shrink的，并且对于java来说Shrink的成本并不是很高。虽然时间复杂度是O(n)，但是常数非常小。

第三，linkedlist才会在Pop,push中反复分配，清理每个节点。vector的情况要好得多。

第四，对于JAVA这样的纯引用Stack来说，vector在绝大多数情况下是最优解。

第五，不存在一种数据结构在所有情况中都是最优的。C++大量使用value stack，所以deque适用于大多数情况。Java只有Reference stack，选择vector没有任何问题。而linked list只在极少数极端情况才适用。

讨论数据结构及算法时，请不要泛泛而谈。“几个”，“未必”这样的词不能说明任何问题。具体说明时间复杂度和空间复杂度才有说服力。

12 楼 jindw 2007-07-22  

netpcc 写道

ｌｉｎｋｅｄｌｉｓｔ的优点是在中间插入，删除元素的时间复杂度为Ｏ（１）。而缺点是消耗大量辅助空间。
这个优点对Ｓｔａｃｋ没有用。因此就只有缺点而没有优点了。

而且对ｓｔａｃｋ提供除Ｐｕｓｈ，Ｐｏｐ之外其他的操作也不是什么大问题。毕竟对栈里的数据进行查找，排序是常用操作。需要在栈中间插入或者删除一些元素的需求也不是特别奇怪。像表达式解析经过大幅优化后经常需要这么干。

ｌｉｎｋｅｄｌｉｓｔ缺点是随机访问慢。现在的硬件环境还有谁会在乎几个引用的空间。
再说，linkedlist之外，用数组实现的有序集合，同样要让费空间，这个让费，未必比linkedlist小，而且，增删时还需要反复的从新分配、清理。。。。

11 楼 netpcc 2007-07-20  

ｌｉｎｋｅｄｌｉｓｔ的优点是在中间插入，删除元素的时间复杂度为Ｏ（１）。而缺点是消耗大量辅助空间。
这个优点对Ｓｔａｃｋ没有用。因此就只有缺点而没有优点了。

而且对ｓｔａｃｋ提供除Ｐｕｓｈ，Ｐｏｐ之外其他的操作也不是什么大问题。毕竟对栈里的数据进行查找，排序是常用操作。需要在栈中间插入或者删除一些元素的需求也不是特别奇怪。像表达式解析经过大幅优化后经常需要这么干。

10 楼 小玩子 2007-07-20  

netpcc 写道

小玩子 写道

或者用Linkedlist也可以嘛
就是不知道为啥要选用vector

用Linkedlist实现stack完全没有道理。
stack只能从一头增删数据。如果不考虑shink和海量数据的话，vector还是很适合的。

linkedlist辅助空间极大，而且添加删除也比较慢。并不适合用来实装stack.

另外C++的STL的STACK的内部存储结构是可选的。并不局限于deque。

你为什么说用linkedlist实现stack完全没有道理呢？

9 楼 netpcc 2007-07-20  

小玩子 写道

或者用Linkedlist也可以嘛
就是不知道为啥要选用vector

用Linkedlist实现stack完全没有道理。
stack只能从一头增删数据。如果不考虑shink和海量数据的话，vector还是很适合的。

linkedlist辅助空间极大，而且添加删除也比较慢。并不适合用来实装stack.

另外C++的STL的STACK的内部存储结构是可选的。并不局限于deque。

8 楼 jindw 2007-07-18  

小玩子 写道

好像1.6StringBuffer还有一个类似的类 StringBuilder 速度要比StringBuffer快 但是线程不安全

集合需要同步的情况还是比较常见，不过也没必要在实现类里面实现，后来jdk4的Collections工具类的一些同步包装方法就比较漂亮。

很难想象StringBuffer需要同步的情景。

7 楼 Godlikeme 2007-07-17  

集合操作线程同步意义不大，只能保证操作的原子性，不能保证数据的完整性。StringBuffer得不偿失。

6 楼 小玩子 2007-07-17  

晕 应该是1.5 咋打错了呢

5 楼 小玩子 2007-07-17  

好像1.6StringBuffer还有一个类似的类 StringBuilder 速度要比StringBuffer快 但是线程不安全

4 楼 歆渊 2007-07-17  

Stack 是从1.0就有了, 那时候还不是 Collections Framework, java.util.* 的设计也就没有那么成体系, 看看 Properties, Hashtable 也差不多.

Java 在 1.0 的时代还挣扎在生存斗争里, 主要精力还是在 安全, 网络, 跨平台 等等那些亮点上, 细节上感觉没有顾得上精雕细琢. 到了1.1好像底气才比较足起来, 做了很多重大改进.

其实像 StringBuffer 也是类似, 程序里 String s = "Hello, " + "World" 这样的语句是编译为 String s = new StringBuffer().append("Hello,").append("World").toString(); 的, 这种用法用户代码根本得不到那个StringBuffer的引用, 也就不可能在多个线程间共享, 所以也就根本不可能出现并发访问, 用不着同步的.

但是StringBuffer从头到尾都是同步实现的, 当然也是考虑给不注意同步问题的程序员预先买单, 而且牺牲的只是大约30%的性能, Java一开始的时候自己已经慢得够呛了, 这点性能损失虽然没有必要, 但是很不明显.

另外一个可能的部分原因是Java的同步机制太有创意了, 最初大家都很兴奋, 喜欢把它用在各种看起来需要的地方.

不过现在Java的性能问题已经是本质性的改善了, 也确立了自己的地位, 类似的历史问题也到了回过头去追求完美的时候了. 所以从5.0开始, 引入了 StringBuilder, 不需要同步的时候就用它, 而接口和实现逻辑与StringBuffer完全相同, 只是简单去掉了一些synchronized关键字.

3 楼 小玩子 2007-07-17  

或者用Linkedlist也可以嘛
就是不知道为啥要选用vector

2 楼 JAVA_ED 2007-07-17  

<br/>
<strong>小玩子 写道：</strong><br/>
<div class='quote_div'><font>java从出台以来有十二年的历史了，我们从未知到现在被广大程序员所接受 正是说明了它有其存在与发展的空间<br/>
但是人无完人 java在设计上也有自身的缺点，举个例子：从API里可以看到java.util.Stack类，stack 的特点是后进先出 且不能查找 array的特点是易于查找但是增删比较难<br/>
这个一般的程序员都很清楚 这个类是java.util.Vector的子类，Vector底层实现是用array且线程安全，这就与statck本身的特点不符合，再者由于是继承，stack就会将父类的所有方法都继承过来<br/>
如：add(int index,E element)这与stack是根本就不能实现的 但是SUN公司对于这个错误是没办法挽回了 以至于这个错误就一直错了十多年 最后SUN公司给出的解释就是不要轻易用这个类<br/>
从这件小事上来说明 一个设计者小小的失误对代码或者一个应用会起到为意想不到的结果 所以我们要努力再努力去完善自己<br/>
</font>
<p><font><img src='/javascripts/fckeditor/editor/images/smiley/msn/regular_smile.gif' alt=''/></font></p>
</div>
<br/>
的确 我猜测可能是因为STL里一般用dequeue adapt stack, 但是JAVA没有dequeue 所以选择了vector<br/>
可以选择用LinkedList实现 也可以封装JDK的stack<br/>
<br/>

1 楼 baallee 2007-07-17  

不知道是不是作者偷懒，哈哈，继承Vector实在是匪夷所思。无依无靠实现个stack也不是什么难事吧。