Java Collection - 基于字典/树的抽象数据结构的具体数据结构

Question

我的问题是在实现抽象数据结构实现(如变体映射/树)时使用的基本/具体数据结构(如数组)是什么？

我正在寻找在java集合中真正使用的东西,而不是理论上的答案.

Answer 1

基于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位.