我的问题是关于在实现抽象数据结构实现（如变体映射/树）中使用的基本/具体数据结构（如数组）是什么？
我正在寻找 java 集合中真正使用的东西，而不是理论上的答案。
问问题
1213 次
2 回答
9
基于对 Sun/Oracle JDK 的快速代码审查。您可以自己轻松找到详细信息。
列表/队列
ArrayList
生长Object[] elementData领域。默认可以容纳 10 个元素，当无法容纳更多对象时增长约 50%，将旧数组复制到更大的新数组。移除物品时不会收缩。
LinkedList
依次引用Entry实际元素、前一个和下一个元素（如果有）的引用。
ArrayDeque
类似于ArrayList但也持有两个指向内部E[] elements数组的指针 -head和tail. 在任一侧添加和删除元素都只是移动这些指针的问题。当太小时，数组会增长 200%。
地图
HashMap
Entry[] table拿着所谓的水桶的生长领域。每个桶包含具有与关键模块表大小相同的哈希的条目的链接列表。
TreeMap
Entry<K,V> root参考持有红黑平衡树的根。
ConcurrentHashMap
类似于HashMap但对每个存储桶（称为段）的访问是由一个独立的锁同步的。
套
TreeSet
在下面使用TreeMap(!)
HashSet
在下面使用HashMap(!)
BitSet
使用long[] words字段以尽可能提高内存效率。一个元素最多可存储 64 位。
于 2012-06-02T19:31:35.940 回答
1
当然，每种实现都有一个答案。看看javadocs，他们经常描述这些东西。http://docs.oracle.com/javase/7/docs/api/
于 2012-06-02T19:24:49.307 回答