集合类
集合类表示一组对象(注意不能是基本类型),用来更好的组织、管理和操作数据,包括集合、数组、列表、队列、映射等数据结构。
集合类最顶层不是抽象类而是接口,因为接口代表的是某个功能,而抽象类是已经快要成形的类型,不同的集合类的底层实现是不相同的,同时一个集合类可能会同时具有两种及以上功能(既能做队列也能做列表),所以采用接口会更加合适,接口只需定义支持的功能即可。
ArrayList
ArrayList
底层是用数组实现的。ArrayList 类是一个可以动态修改的数组,与普通数组的区别就是它是没有固定大小的限制,我们可以添加或删除元素。ArrayList
的预存大小初始默认为10,之后每次扩增都会增加到原来的1.5倍+1。
ArrayList 继承了 AbstractList ,并实现了 List 接口。
LinkedList
LinkedList
底层是用链表实现的,那么就无法做到随机存取,每次访问一个下标的元素都会从链表头或者链表尾开始遍历。
LinkedList
类继承了AbstractSequentialList 类,实现了List,Deque,Cloneable,Serializable接口,可以实现数组、队列、双端队列、栈等。
同时,LinkedList
可以当作栈和队列来使用!
LinkedList<String> list = new LinkedList<>();
list.offer("A"); //入队
System.out.println(list.poll()); //出队
list.push("A");
list.push("B"); //进栈
list.push("C");
System.out.println(list.pop());
System.out.println(list.pop()); //出栈
System.out.println(list.pop());
迭代器
Java Iterator
是用于访问Java集合的方法,可以迭代集合。Iterator
是迭代器最简单的实现,ListIterator
扩展了Iterator
接口,是集合API中的接口。
对于普通的迭代器,当迭代到集合末尾时,想要再次遍历集合就需要重新定义一个新的迭代器。
foreach
方法的本质也是使用迭代器。(可以在字节码反编译文件中看到)
集合Set
Set是一个接口,继承了Collection接口,实现它的类有HashSet,TreeSet,LinkedHashSet
等。但是它们本质上都是Map,都是用映射来实现的。HashSet里面是HashMap,用哈希表实现,因此输出集合是无序的;TreeSet里面是TreeMap,用红黑树实现,因此可以给集合排序。
Map
map是映射,即键值对<key, value>
,一个key唯一对应一个value。map接口继承Object接口,HashMap和TreeMap类分别实现了map接口。前者内部实现是哈希表,后者是红黑树。
Map是java中的接口,直接继承Object,Map.Entry是Map内部的一个接口,它表示Map中的一个键值对,定义为Entry<K, V>
。getKey()
方法用来获得该键值对的键, getValue()
获得值, setValue(Object value)
方法可以设置键对应的值。Map.entrySet()
用来获得所有键值对的集合,注意这是一个集合,一般用此方法来遍历map中的所有键值对。
HashMap和LinkedHashMap。HashMap内部是用哈希表实现的,JDK1.8之后开链表法改为尾插法。哈希表本质上是一个数组,这里是用开链表法,即根据hashcode值得到一个key将要插入的哈希表位置相同的value集合都会插入到同一个链表中,尾插法,当该链表的元素个数大于8之后会变成用红黑树来存储,又退化至元素小于6时会变回链表。
HashMap内部的哈希表是一个Node<K, V>
集合,Node实现了Map.Entry接口,即Node本质也是一个键值对,不过封装起来之后里面也包含了下一个键值对的引用还有一些方法等。
HashMap有两个参数:内部哈希表的大小和装载因子。哈希表大小只能为2的幂次,默认为16,每次扩容都会扩容至原来的2倍,且哈希表大小最大为2的30次幂,根据源码static final int MAXIMUM_CAPACITY = 1 << 30
。装载因子loadFactor
默认为0.75,根据装载因子判断是否需要进行扩容。
LinkedHashMap直接继承自HashMap类,具有它的全部性质。LinkedHashMap里的数据元素也是键值对Entry
,它继承了HashMap里的Node类,在其基础上新增了Entry<K, V> before, after
关键字,即每个节点都进化成了一个双向链表,保证了插入的顺序。
TreeMap内部直接使用了一棵红黑树,由于红黑树是建立在二叉排序树基础上的,即插入红黑树的键key必须有可比较的性质,也可以重写其内部的比较器comparator
。TreeMap也有Entry类,在Map.Entry接口的基础上新增了字段Entry<K, V> left, right, parent;
和boolean color = BLACK;
,可以看出本质上是一个红黑树的结点。
map的一些使用:
Map<Integer, String> map = new HashMap<>();
map.put(1, "A");
map.put(2, "B");
map.put(3, "C");
System.out.println(map.get(1)); //获取Key为1的值
System.out.println(map.getOrDefault(0, "K")); //不存在就返回K
map.remove(1); //移除这个Key的键值对
map.forEach((k, v) -> System.out.println(k+"->"+v));
for (Map.Entry<Integer, String> entry : map.entrySet()) { //也可以获取所有的Entry来foreach
int key = entry.getKey();
String value = entry.getValue();
System.out.println(key+" -> "+value);
}
System.out.println(map.keySet()); //直接获取所有的key
System.out.println(map.values()); //直接获取所有的值
虽然map内部并未实现迭代器,但是调用其entrySet()
方法获得其键值对的集合后,可以用迭代器访问该集合。
// 注意Entry是Map内部的一个泛型接口
Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator();
0 条评论