Collection集合
在collection接口之上还有一个Iterable接口，也就意味着这一组集合全部都可以通过迭代器来操作。
继承了Collection的抽象类abstractCollection实现了大部分通用的操作,以便于子类的使用.
List集合
list作为有序集合，定义了多个可以随机访问的接口,list集合可以通过两种方式来访问
- 迭代器访问，必须顺序访问
- 整数索引访问，随机访问
链表更适合迭代器访问,数组适合索引访问,java1.4引入了RandomAccess接口,用来标识是否支持高效随机访问.
不得不提Iterator接口,LIstIterator是Iterator的子接口,定义了在迭代器之前增加add()方法以及可以反向遍历的两个方法:previous() ,hasPervious(),列表迭代器有保持位置的计数器
LinkedList
链表数据结构,LinkedList虽然提供了随机访问的方法,但是其实是"虚假的",例如:
public static void main(String[] args) {
LinkedList<String> link = new LinkedList<String>();
link.add("小汪汪");
link.add("小张张");
link.add("小黄黄");
for (int i = 0; i < link.size(); i++) {
System.out.println(link.get(i));
}
}
在语法上支持随机访问,其实并不是,每一次遍历元素都要从头开始,linkedlist不存储位置信息.因此,进行随机访问使用arraylist.
Arraylist
数组集合,封装了一个动态再分配的对象数组,支持高速随机访问.
Vector
Vector极少使用,不过多赘述,可以理解为线程安全的ArrayList。
- List常见实现类
ArrayList，LinkedList，Vector - ArrayList ,LinkedList的区别
数组，访问速度快，便于查询。链表，插入删除快，访问慢，不支持随机访问。 - List集合的扩容机制
ArrayList：初始长度为10，可指定长度。未添加数据前为0，添加一个数据增长到10。通过grow()方法按照原来数据的1.5倍增长。最大长度为Integer.MAX_VALUE或者Integer.MAX_VALUE-8.
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = 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);
}
Vector：grow()方法，按照原来数据长度的两倍增长。
LinkedList：链表，节点增加数据即可。
Set集合
HashSet
散列表:
为了能够快速查找到指定元素,但是又不知道元素的位置,就需要遍历全部数据,当数据过多时,就会消耗大量的时间.散列表就可以快速访问数据,不同的数据对象就有不同的散列码.注意:要与equals方法保持一致,如果两个数据相同,那么散列码也要保持相同.
散列表基于链表数组实现，每个列表被称为桶，计算散列码，与桶的总数取余，插入对应的桶中，这个操作可能会发生散列冲突。在java8以后，当桶满时从链表转化为平衡二叉树，提高性能。
如果想更多控制性能，大致知道有多少个元素，通常将桶数设定为元素个数的75%到150%。
当然大部分并不知道有多少个元素，装填因子可以确定什么时候散列表再散列，通常设定为0.75，如果表中元素填满了75%以上，就再散列，是原来的2倍。
contains()方法已经被重新定义，只查看一个元素不再遍历，迭代器依次按顺序遍历所有元素，并非随机访问。不关心元素顺序使用Hashset。
TreeSet
树集是一个有序集合,可将数据自动排序,添加数据效率比散列表稍慢,但查找速度要快,速度为Log以2为底的N次方。结合Compareable接口或提供comparetor方法实现排序。
Map
HashMap和TreeMap与hashSet和treeSet底层是相同的，散列映射将键进行散列，树映射根据键的顺序组织为一个搜索树。散列与比较函数只能作用于键。
映射视图
集合框架并不认为映射本身就是一个集合，但是可以得到视图。
三种视图：
Set<K> keySet()
Collection<V> values()
Set<Map.Entry(k,v)> entrySet<>
利用lamda表达式,遍历Map集合:
HashMap<String, String> map = new HashMap<String, String>();
map.put("f","f");
map.put("x", "x");
map.forEach((k,v)->System.out.println(k+v))
链接散列集映射
LinkedHashset和LinkedHashMap会记住插入元素项的顺序。在表中插入元素时，就会并入到双向链表。
HashTable
与HashMap作用一样，接口也基本相同。与vector一样，方法是同步的，如果对兼容性没要要求，就使用HashMap。如果需要并发访问，应该使用ConcurrentHashMap。
扩容机制：初始容量为11，每次扩容变为原来的2n+1.
- HashMap 的长度为什么是2的幂次方?
在散列表中，进行取余操作，使用的是hash%length=hash&(length-1)。两个操作相同，&运算的效率更高，但是长度必须是2的n次方。
网友评论