Java中的容器（集合）
程序员文章站
2022-06-09 11:30:10
1、Java常用容器：List，Set，Map List： 继承了Collection接口（public interface List extends Collection ），有序且允许出现重复值。 Set： 继承了Collection接口（public interface Set
1、java常用容器：list，set，map
list：
- 继承了collection接口（public interface list<e> extends collection<e> ），有序且允许出现重复值。
set：
- 继承了collection接口（public interface set<e> extends collection<e> ），无序且不允许出现重复值。
map：
- 是一个使用键值对存储的容器（public interface map<k,v> ）。
2、collection 和 collections 的区别
collection：
- collection是一个集合类的通用接口（源码：public interface collection<e> extends iterable<e>）。
- 通过查看源码可以发现，其中包含的都是一些通用的集合操作接口，他的直接继承接口有list和set。
collections：
- collections是一个集合工具类（源码：public class collections）。
- 其中提供一系列对集合操作的静态方法，比如排序：sort()，集合安全：synchronizedcollection()，反转：reverse()等等。
3、arraylist 和 linkedlist 的区别
arraylist：
- 底层数据结构是一个数组，查询效率比较高，添加删除较慢（默认添加在末尾，在指定位置添加元素效率比较低，因为需要将指定位置后续的元素都往后移位）。
linkedlist：
- 底层数据结构是一个双向链表（prev指向前节点，next指向后节点），查询效率比较慢，添加删除比较快。
4、arraylist 和 vector 的区别
arraylist：
- 非线程安全，读取效率较高。
vector：
- 线程安全（源码中显示该类的方法使用了synchronized），读取效率较低（推荐使用copyonwritearraylist,该类适合读多写少的场景）。
5、hashmap 和 hashtable 的区别
hashmap：
- 非线程安全，允许空键值，执行效率相对较高（底层使用的数据结构是数组+链表+红黑树（jdk8）或者数组+链表（jdk7））。
hashtable：
- 线程安全，不允许空键值，执行效率相对较低（推荐使用concurrenthashmap）。
6、hashmap 和 treemap 的使用场景
hashmap：
- 一般情况下进行插入，删除，定位元素的话，使用hashmap（常用）。
treemap：
- 如果需要使用有序的集合，推荐用treemap。
7、hashmap 实现原理
以put操作为例：
- 首先会根据key的hashcode得到hash值（部分源码：return (key == null) ? 0 : (h = key.hashcode()) ^ (h >>> 16)），依据hash值得到该元素在数组的位置（下标），如果该位置不存在元素，则将该元素直接放入此位置上；否则判断元素是否相等，如果是，则覆盖，否则使用拉链法解决冲突（创建一个链表，先加入的放到链尾，后加入的放在链头，超过8位时，使用红黑树存储）。
- 放入的元素是包含了键值对的元素，而非仅仅只有值。
8、hashset 实现原理
以add操作为例：
- 进入add源码（return map.put(e, present)==null），可以看到其底层是用map来实现的，只是传入的值当做了map的key，而map的value使用的是统一的present。
9、迭代器：iterator
iterator：
- 是一个轻量级的对象（创建代价小），主要用来对集合进行遍历移除等操作。
- 示例代码如下
package com.spring.test.service.demo;
import java.util.*;
/**
* @author: philosopherzb
* @date: 2019/10/1
*/
public class demo {
public static void main(string[] args){
list<string> list = new arraylist<>(5);
for(int i=0;i<5;i++){
list.add("test" + i);
system.out.println("输入：test" + i);
}
//利用iterator()返回一个iterator对象
iterator<string> it = list.iterator();
//判断是否还存在元素
while(it.hasnext()){
//第一次调用next()会返回集合中的第一个元素，之后返回下一个
string s = it.next();
if("test3".equals(s))
//移除某个元素
it.remove();
}
list.foreach(l->{
system.out.println(l);
});
}
}
10、arraylist 扩容源码解析（jdk8）
源码解析：
- 首先我们使用 arraylist<string> list = new arraylist<>(5)创建一个arraylsit，这表明创建的arraylist初始容量为5.
- 源码如下：
//默认初始容量10
private static final int default_capacity = 10;
//一个空的默认对象数组，当arraylist(int initialcapacity)，arraylist(collection<? extends e> c)中的容量等于0的时候使用
private static final object[] empty_elementdata = {};
//一个空的默认对象数组，用于arraylist()构造器
private static final object[] defaultcapacity_empty_elementdata = {};
//一个对象数组，transient表示不能序列化
transient object[] elementdata;
//数组大小
private int size;
//以传入的容量构造一个空的list
public arraylist(int initialcapacity) {
//如果传入值大于0，则创建一个该容量大小的数组。
if (initialcapacity > 0) {
this.elementdata = new object[initialcapacity];
} else if (initialcapacity == 0) {
//否则如果传入值等于0，则创建默认空数组
this.elementdata = empty_elementdata;
} else {
//如果小于0则抛出异常
throw new illegalargumentexception("illegal capacity: "+
initialcapacity);
}
}
- 接着我们使用add方法添加一个字符串到该list中，list.add("test")。进入add源码会发现，真正的扩容是发生在add操作之前的。
- 源码如下：
//默认添加在数组末尾
public boolean add(e e) {
//添加之前先确认是否需要扩容
ensurecapacityinternal(size + 1); // increments modcount!!
//新加入的元素是添加在了数组的末尾，随后数组size自增。
elementdata[size++] = e;
return true;
}
- 进入ensurecapacityinternal()方法查看对应源码如下：
private void ensurecapacityinternal(int mincapacity) {
//先通过calculatecapacity方法计算最终容量，以确认实际容量
ensureexplicitcapacity(calculatecapacity(elementdata, mincapacity));
}
- 到这一步，我们需要先进入calculatecapacity()方法看看他是如何计算最后容量的，源码如下：
private static int calculatecapacity(object[] elementdata, int mincapacity) {
//如果elementdata为默认空数组，则比较传入值与默认值（10），返回两者中的较大值
//elementdata为默认空数组指的是通过arraylist()这个构造器创建的arraylist对象
if (elementdata == defaultcapacity_empty_elementdata) {
return math.max(default_capacity, mincapacity);
}
//返回传入值
return mincapacity;
}
- 现在我们确认了最终容量，那么进入ensureexplicitcapacity，查看源码如下：
private void ensureexplicitcapacity(int mincapacity) {
modcount++;
// overflow-conscious code
//如果最终确认容量大于数组容量，则进行grow()扩容
if (mincapacity - elementdata.length > 0)
grow(mincapacity);
}
- 可以看到，只有当最终容量大于数组容量时才会进行扩容。那么以我们上面的例子而言具体分析如下：
- 首先因为我们创建的时候就赋了初始容量5，所以elementdata.length = 5。
- 当我们add第一个元素的时候，mincapacity是等于size + 1 = 1的。
- 此时mincapacity - elementdata.length > 0条件不成立，所以不会进入grow(mincapacity)方法进行扩容。
- 以此类推，只有添加到第五个元素的时候，mincapacity = 6 大于 elementdata.length = 5，这时就会进入grow(mincapacity)方法进行扩容。
- grow()以及hugecapacity()源码如下：
//可分配的最大数组大小
private static final int max_array_size = integer.max_value - 8;
//扩容
private void grow(int mincapacity) {
// overflow-conscious code
//oldcapacity表示旧容量
int oldcapacity = elementdata.length;
//newcapacity表示新容量，计算规则为旧容量+旧容量的0.5，即旧容量的1.5倍。如果超过int的最大值会返回一个负数。
//oldcapacity >> 1表示右移一位，对应除以2的1次方。
int newcapacity = oldcapacity + (oldcapacity >> 1);
//如果新容量小于最小容量，则将最小容量赋值给新容量(有时手动扩容可能也会返回<0，对应方法为ensurecapacity())
if (newcapacity - mincapacity < 0)
newcapacity = mincapacity;
//如果新容量大于max_array_size，则执行hugecapacity(mincapacity)返回对应值
if (newcapacity - max_array_size > 0)
newcapacity = hugecapacity(mincapacity);
// mincapacity is usually close to size, so this is a win:
//复制旧数组到新容量数组中，完成扩容操作
elementdata = arrays.copyof(elementdata, newcapacity);
}
private static int hugecapacity(int mincapacity) {
//如果最小容量超过了int的最大值，mincapacity会是一个负数，此时抛出内存溢出错误
if (mincapacity < 0) // overflow
throw new outofmemoryerror();
//比较最小容量是否大于max_array_size，如果是则返回integer.max_value，否则返回max_array_size
return (mincapacity > max_array_size) ?
integer.max_value :
max_array_size;
}
（以上所有内容皆为个人笔记，如有错误之处还望指正。）
上一篇： 西红柿牛腩做法你知道多少
下一篇： 长乐国庆集训Day2