Java基础整理之Java集合
Java集合框架
常用API:
boolean addAll();
int binarySearch(List<?extends Comparable<? super T>> list, T key)
int binarySearch(List list,T key, Comparator c)
boolean disjoint(Collection<?> c1, Collection<?>c2) 判断重复
void copy(List<? superT> dest, List<? extends T> src) src 到dest
int frequency(Collection<?>c, Object o)
void fill(List<? super T>list, T obj)
T max(Collection<?extends T> coll)
T max(Collection<?extends T> coll, Comparator<? super T> comp)
T min(Collection<?extends T> coll)
T min(Collection<?extends T> coll, Comparator<? super T> comp)
booleanreplaceAll(List<T> list, T oldVal, T newVal)
void reverse(List<?>list)
Collection<T> synchronizedCollection(Collection<T>c)
void swap(List<?> list, int i, int j) 交换
void sort(List<T> list) 排序
void shuffle(List<?> list) 打乱排序
List 按照插入顺序保存元素,有下标,可插入Null
int size() 返回list中元素个数
booleancontains(Object o) 判断list中书否存在此对象
boolean containsAll(Collection<?>c) 判断list中是否存在此容器,无关顺序
booleanisEmpty() 判断lis中元素个数是否为0
Iterator<E>iterator() 返回Iterator对象
Object[]toArray() 返回数组
<T>T[] toArray(T[] a) 产生制定类型的数组
booleanadd(E e) 将此对象添加到list末尾
voidadd(int index, E element) 在指定位置插入元素,下表不能超过size
booleanaddAll(Collection<? extends E> c) 在list末尾添加一个容器
boolean addAll(int index, Collection<? extends E> c) 在指定位置插入容器,下表不能超过size
booleanremove(Object o) 从list中移除对象
E remove(intindex) 根据下标移除对象
booleanremoveAll(Collection<?> c) 移除容器
booleanretainAll(Collection<?> c) 是否交集
voidsort(Comparator<? super E> c) 使用特定比较器排序
voidclear() 清空list
Eget(int index) 根据下表获得对象
Eset(int index, E element) 设置特定位置的对象
intindexOf(Object o) 返回对象的下标
intlastIndexOf(Object o) 返回对象最后一次出现的下标
List<E>subList(int fromIndex, int toIndex) 截取list
List
ArrayList:采用数组实现,默认大小为10,第一次add的时候分配内存空间,以后没此扩展为之前的1.5倍。随机访问速度快。
LinkedList:采用链表实现,增加删除速度快。
两个List都为非线程安全,要使用线程安全的List可以使用Collections中的线程安全方法将List转为线程安全的。
当经常需要根据下标进行操作时,使用ArrayList。不需要进行下标操作时,使用LinkedList。
Set 没有下标,不能保存重复的元素,有些能保存null,有些不能
add(E)
addAll(Collection<?extends E>)
clear()
contains(Object)
containsAll(Collection<?>)
equals(Object)
hashCode()
isEmpty()
iterator()
remove(Object)
removeAll(Collection<?>)
retainAll(Collection<?>)
size()
spliterator()
toArray()
toArray(T[])
测试归属性,询问某个对象是否在set中,set是基于对象的值来去顶归属性的;查找是set最重要操作;Set和Collection接口完全一样;输出顺序没有规律。
HashSet使用散列函数,最快获取元素的方式。使用HashMap实现。
TreeSet将元素存储在红-黑数结构中。按照比较结果的升序保存对象。使用TreeMap实现。1. 关于hashCode和equals的处理,遵循如下规则:
1) 只要重写equals,就必须重写hashCode。
2) 因为Set存储的是不重复的对象,依据hashCode和equals进行判断,所以Set存储的对象必须重写这两个方法。
3) 如果自定义对象做为Map的键,那么必须重写hashCode和equals。 正例:String重写了hashCode和equals方法,所以我们可以非常愉快地使用String对象作为key来使用。
2. ArrayList的subList结果不可强转成ArrayList,否则会抛出ClassCastException异常:java.util.RandomAccessSubList cannot becast to java.util.ArrayList ;
说明:subList 返回的是 ArrayList 的内部类 SubList,并不是 ArrayList ,而是原ArrayList的一个子集,对于SubList 子列表的所有操作最终会反映到原列表上。对原集合元素个数的修改,会导致子列表的遍历、增加、删除均产生ConcurrentModificationException 异常。
3. 使用集合转数组的方法,必须使用集合的toArray(T[] array),传入的是类型完全一样的数组,大小就是 list.size()。
说明:使用 toArray 带参方法,入参分配的数组空间不够大时,toArray 方法内部将重新分配内存空间,并返回新数组地址;如果数组元素大于实际所需,下标为[ list.size()]的数组元素将被置为 null,其它数组元素保持原值,因此最好将方法入参数组大小定义与集合元素个数一致。
4. 使用工具类 Arrays.asList()把数组转换成集合时,不能使用其修改集合相关的方法,它的 add/remove/clear 方法会抛出 UnsupportedOperationException 异常。
说明:asList 的返回对象是一个 Arrays 内部类,并没有实现集合的修改方法。Arrays.asList体现的是适配器模式,只是转换接口,后台的数据仍是数组。创建一个新的List,使用addAll()方法进行添加,也可使用Collections.addAll()方法添加。
5. 不要在 foreach 循环里进行元素的 remove/add 操作。remove 元素请使用 Iterator方式,如果并发操作,需要对Iterator 对象加锁。
6. 集合初始化时,尽量指定集合初始值大小。(集合扩容效率问题)
7. 使用 entrySet 遍历 Map 类集合 KV,而不是 keySet 方式进行遍历。
说明:keySet 其实是遍历了 2 次,一次是转为 Iterator 对象,另一次是从 hashMap 中取出key 所对应的 value。而 entrySet 只是遍历了一次就把 key 和 value 都放到了 entry 中,效率更高。如果是 JDK8,使用 Map.foreach 方法。8. 高度注意 Map 类集合 K/V 能不能存储 null 值的情况,如下表格:
9. 利用 Set 元素唯一的特性,可以快速对一个集合进行去重操作,避免使用 List 的contains 方法进行遍历、对比、去重操作
(1) HashMap:遍历顺序不确定,允许一条记录的键为null,允许多条记录的值为null。非线程安全,如果需要满足线程安全,可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力,或者使用ConcurrentHashMap。
(2) Hashtable:Hashtable是遗留类,承自Dictionary类,线程安全的并发性不如ConcurrentHashMap,因为ConcurrentHashMap引入了分段锁。Hashtable不建议在新代码中使用,不需要线程安全的场合可以用HashMap替换,需要线程安全的场合可以用ConcurrentHashMap替换。
(3) LinkedHashMap:LinkedHashMap是HashMap的一个子类,保存了记录的插入顺序,在用Iterator遍历LinkedHashMap时,先得到的记录肯定是先插入的,也可以在构造时带参数,按照访问次序排序。
(4) TreeMap:TreeMap实现SortedMap接口,能够把它保存的记录根据键排序,默认是按键值的升序排序,也可以指定排序的比较器,当用Iterator遍历TreeMap时,得到的记录是排过序的。如果使用排序的映射,建议使用TreeMap。在使用TreeMap时,key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator,否则会在运行时抛出java.lang.ClassCastException类型的异常。
对于上述四种Map类型的类,要求映射中的key是不可变对象。不可变对象是该对象在创建后它的哈希值不会被改变。如果对象的哈希值发生变化,Map对象很可能就定位不到映射的位置了。
HashMap:
实现结构:数组+链表(当链表长度>=8时,链表转换为红黑树)(JDK1.8),使用哈希表来存储的,
采用了链地址法解决冲突,两个key会定位到相同的位置,表示发生了Hash碰撞。当然Hash算法计算结果越分散均匀,Hash碰撞的概率就越小,map的存取效率就会越高。如果哈希桶数组很大,即使较差的Hash算法也会比较分散,如果哈希桶数组数组很小,即使好的Hash算法也会出现较多碰撞,所以就需要在空间成本和时间成本之间权衡,
Node数组默认初始长度length为16,负载因子Loadfactor默认大小为0.75。这两个数组可以在创建HashMap时通过构造函数传参进行控制。threshold是HashMap所能容纳的最大数据量的Node(键值对)个数。threshold = length * Load factor。当map中的数目的值要超过threshold时,map将进行重新resize(扩容),扩容后的HashMap容量是之前容量的两倍。
实现:
1. 确定哈希桶数组索引位置
a) (key == null) ? 0 : (h =key.hashCode()) ^ (h >>> 16);
h & (length - 1)
2. 分析HashMap的put方法
3. 扩容机制
数组大小 * 2