java学习笔记015 集合

1.集合

Collection
	List	有序，可重复
	Set	无序，不可重复
Map
	key <==> value

2.Collection接口

通用的方法
	boolean		add(E e)
	boolean		addAll(Collection coll)
	int		size()
	boolean		isEmpty()
	void		clear()		//元素都指向null, size=0
	boolean		contains()	//内部调用了equals()方法
	boolean		containsAll(Collection coll)
	boolean		remove(Object obj)		//内部调用了equals()方法
	boolean		removeAll(Collection coll)	//移除this中与coll的交集
	boolean		retainAll(Collection coll)	//this添加(coll与this的差集)
	boolean		equals(Collection coll)		//集合是否equal
	int		hashCode()
	T[]		toArray()	//转换成数组;数组转成集合:Arrays.asList(T ... t)
	Iterator<T>		iterator()

3.Iterator接口(迭代器)

Iterator iterator = coll.iteraror();
最开始指针指在元素上面(没有指向元素)，next()时指针下移指向下个元素
1)方法
	
	T		next()	//越界NoSuchElementException
	boolean		hasNext()
	void		remove()
	
	eg:	while(iterator.hasNext()){
			System.out.println(iterator.next());
		}
	
2)foreach循环since 1.5
	for(Object obj : coll){
		//内部(原理)调用迭代器
		//只能遍历，不能更改原有数据
	}

4.List接口

ArrayList,LinkedList,Vector都实现了List接口，存储的数据有序，可重复
ArrayList (since 1.2)
	1)实现
		线程不安全,效率高,底层使用Object[]实现
		add(Object obj)		//底层容量不够会扩容，默认扩容1.5倍
		jdk 1.7 ：底层Object[] elementDate初始长度为10
		jdk 1.8 ：底层Object[] elementDate初始为{}，第一次调用add()操作时创建长度为10的数组
	2)List接口方法
		void	add(int index, Object ele)
		boolean	addAll(int index, Collection eles)
		Object	get(int index)
		int	indexOf(Object obj)
		int	lastIndexOf(Object obj)
		Object	remove(int index)
			//区分boolean remove(Object obj),如果删除集合里面的int型数据，用list.remove(new Integer(3));
		Object	set(int index, Object obj)
		List	subList(int fromIndex, int toIndex)	//左闭右开
		
LinkedList
	底层使用双向链表，适合频繁进行插入、删除操作的数据

Vector (since 1.0)
	线程安全的,效率低,底层使用Object[]实现

5.Set接口

1)特性
	Set接口继承Collection接口，没有定义额外的方法
	无序性
		不等于随机性，存储的数据在底层数组中，并非按索引的顺序进行添加，而是根据数据的哈希值添加
	不可重复性
		保证添加的元素按equals()判断时不能返回true

2)HashSet
	线程不安全的，可以存null
	HashSet添加元素a的过程
		首先调用元素a所属类的hashCode()方法计算它的哈希值
		此哈希值经过某种算法得到其在HashSet底层数组中的索引位置
		判断底层数组此位置上是否已有元素
			如果此位置上还没有元素，直接将元素a添加到此位置				//添加成功I
			如果此位置上已经存在元素b(或以链表形式存储的多个元素)，则比较元素a和元素b的哈希值
				如果哈希值(与此索引位置上所有元素均)不相同，元素a添加成功	//添加成功II
				如果哈希值相同，还要调用元素a所属类的equals()方法
					equals()返回true，添加失败			//添加失败
					equals()返回false，元素a添加成功			//添加成功II
					
	说明：
	1元素a添加成功II的情况
		jdk 1.7	元素a放到数组中，指向原来的元素
		jdk 1.8	原来的元素在数组中，指向元素a
	2向set中添加的元素所属的类要求重写hashCode()和equals()方法，且重写的hashCode()和equals()方法保持一致性(同为true或同为false)
	3HashSet是用HashMap实现的
		eg: src HashSet.java
		private static final Object PRESENT = new Object();
		public HashSet(){
			map = new HashMap<>();
		}
		public boolean add(E e){
			return map.put(e, PRESENT)==null;
		}
	
3)LinkedHashSet
	HashSet的子类，遍历数据时，可以按添加的顺序遍历
	适合需要频繁遍历的数据

4)TreeSet
	可以按照添加对象的指定属性进行排序
	向TreeSet中添加的数据要求是相同类的对象
	排序方式：自然排序和定制排序
		自然排序 ： 实现Comparable接口重写的compareTo()方法返回0的时候，TreeSet认为比较的两个对象"相同"
		定制排序 ： new TreeSet(Comparator comparator)
			@override
			public int compare(Object o1, Object o2){...}

6.Map接口

1)Map，存储双列数据，存储key-value键值对数据
   |---HashMap：Map主要的实现类，线程不安全，效率高，key和value可以为null
           |---LinkedHashMap
   |---Hashtable：古老的实现类，线程安全，效率低，key和value不可以为null
           |---Properties	key和value都是String类型
   |---SortedMap
           |---TreeMap

2)HashMap
	1Map的结构
		key : 无序，不可重复，使用Set存储，HashMap被存储的对象要重写equals()和hashCode()方法
		value : 无序，可重复，使用Collection存储，
		entry : 一个entry包含一个key和一个value，使用Set存储

	2HashMap的底层实现原理
		1）实例化后，创建长度为16的数组Entry[] table (jdk 1.7)
		...
		2)map.put(key, value)
		首先计算key所在类的hashCode()计算key的哈希值，此哈希值经过某种算法计算后得到Entry在数组中存放的索引位置
			如果此索引位置上没有元素，那么Entry添加成功	//添加成功I
			如果此索引位置上已有元素（一个元素或以链表形式存储的多个元素），比较此元素key与已有元素key的哈希值
				如果此元素key与已有元素key的哈希值均不相同	//添加成功II
				如果此元素key与已有某元素key的哈希值相同，则调用equals()进行比较
					如果equals()返回false		//添加成功II
					如果equals()返回true，使用新put的Entry的value替换原来Entry的value
					
		关于添加成功II
			新添加的Entry以链表的形式存储
				jdk 1.7 
				jdk 1.8 
			默认扩容方式，数组长度扩充成原来的2倍，扩容的时候需要重新计算索引
			何时扩容？
			
			
	3jdk 1.8的不同：
		new HashMap()底层Node[]（jdk 1.7叫Entry[]）在第一次put的时候,才初始化一个长度为16的Node[]
		底层是数组+链表（jdk 1.7 及以前）
		底层是数组+链表+红黑树（jdk 1.8)
			   当某一个索引位置上的元素 > 8
			且 当前数组的长度		> 64 时，此索引位置上的所有数据改为用红黑树进行存储
					
3)Map中常用方法
	1增删
		Object		put(Object key, Object value)
		void		putAll(Map map)
		Object		remove(Object key)
		void		clear()
	2查
		Object		get(Object key)
		boolean		conatinsKey(Object key)
		boolean		conatinsValue(Object value)
		int		size()
		boolean		isEmpty()
		boolean		equals(Object obj)	//
	3集合
		Set		keySet()
		Collection	values()
		Set		entrySet()

4)TreeMap与Properties
	向TreeMap中添加元素，要求元素的key是同一个类的对象
	排序方式： 自然排序 和 定制排序
		1)Comparable接口
		2)Comparator接口	//new TreeMap(new Comparator(Object o1, Object o2){...});
	
	Properties的key和value都是String类型的，常用来处理配置文件
	eg:读取properties文件中的数据(key=value)
		Properties pros = new Properties();
		FileInputStream fis = new FileInputStream("demo.properties");
		pros.load(fis);
		String keyValue = pros.getProperty("key");

7.Collections工具类

可以操作Collection(List,Set),Map
常用方法(均为static)
	排列
		reverse(List)	//反转顺序
		shuffle(List)	//随机排序
		sort(List)	//按list的自然顺序升序排列
		sort(List, Comparator)	//
		swap(List, int, int)	//交换两索引处的元素
	统计量
		Object	max(Collection)		
		Object	max(Collection, Comparator)	
		Object	min(Collection)		
		Object	min(Collection, Comparator)	
		int	frequency(Collection, Object)	//指定元素在集合中出现的次数
		//List destination = Arrays.asList(new Object[source.size()]);
	void	copy(List destination, List source)	//要求destination的size不小于source的size，destination原索引处已有的元素复制后会被覆盖
	boolean	replaceAll(List list, Object oldVal, Object newVal)
	同步/线程安全
		//返回一个线程安全的集合
		Collection	synchronizedCollection(Collection)	
		List		synchronizedList(List)
		Map		synchronizedMap(Map)
		Set		synchronizedSet(Set)