java容器

灰太狼 2022-05-21 10:19 248阅读 0赞

# java容器 #

java容器作为数据结构的标准实现，包含有`Map`, `Collection`(`Queue`, `Set`, `List`)，上面主要为接口的定义，包含了常用的功能数据结构．  
接口定义了功能，接口有多种具体实现，不同的实现方式，会有不同的适用场景，在不同的场景下的算法效率不同．

![这里写图片描述][70]

`Iterator`是用户遍历`Collection`类的，在for(T t:Collection)\{\}语法中，内部是调用的`Iterator`相关接口．

## List ##

`List`的主要实现有`LinkedList`和`ArrayList`，如果需要随机访问，优先用`ArrayList`，有`RandomAccess`接口可以判断是否支持随机访问；如果需要频频增删，优先使用`LinkedList`．

## Map ##

`Map`的实现数据结构有Hash和Tree．其区别是Hash无法排序，Tree是可以排序(`SortedMap`)的, 同时TreeMap也实现了`NavigableMap`接口，可以实现TreeMap的更精确的查找．  
`TreeMap`, `SortedMap`, `NavigableMap`三者的关系如下:

![这里写图片描述][70 1]

另外有几种特殊的实现, 一个是针对使用场景，可以自动释放键值对的`WeakHashMap`;另一个是针对访问频率，访问频率越高，放在前面的，`LinkedHashMap`; 其值可以直接使用`==`进行比较的为`IdentityHashMap`．  
为了方便遍历，`Map`实现有三种视图, `KeySet`, `EntrySet`, `Values`，其中:  
\- KeySet为Map中Key值的集合  
\- EntrySet为Map中(Key,Value)键值对的集合  
\- Values为Map中值的集合

## Set ##

`Set`和`Map`的实现方式比较类似，因为都是需要查询，使用`HashTable`和`Tree`实现的．所以`Set`最主要的实现方式是`HashSet`和`TreeSet`，同样`HashSet`不能排序，`TreeSet`可以排序．

*Java中HashTable的实现方式*:

采用数组(Array)＋桶(`Bucket`)方式实现，数组的长度为桶的个数．结构大致如下:

![这里写图片描述][70 2]

## Queue ##

队列主要有`PriorityQueue`实现，也可以使用`ArrayList`作为队列使用．

[70]: /images/20220521/289dbb1b71cb48bab7456a0e1a83c411.png
[70 1]: /images/20220521/c7b3c65067b94886a9fa14ff3882ab91.png
[70 2]: /images/20220521/c8f29739918b4db88cc70df0b1e14f5d.png