【Java基础】集合

一、集合概述

为了方便对多个对象进行存储和操作，集合是一种Java容器，可以动态地把多个对象引用放入容器中

数组存储的特点

• 一旦初始化后，长度不可改变，元素类型不可改变
• 提供的方法很少，对于添加、删除、获取实际元素个数等操作非常不便
• 有序、可重复

集合的两种体系

• Collection接口：单列数据，定义了存取一组对象的方法的集合。
  • List：有序、可重复的集合
  • Set：无序、不可重复的集合
• Map接口：双列数据，保存具有映射关系的“key-value”键值对集合
  

二、Collection接口

常用方法

public class CollectionTest {@Testpublic void test1(){Collection col1 = new ArrayList();// add(Object o)	添加元素col1.add("wanfeng");col1.add("jingyu");col1.add(123);// size()	元素个数System.out.println("col size = "+col1.size());// addAll(Collection c)	添加集合中的所有元素Collection col2 = new ArrayList();col2.add(false);col2.add(34.56);col2.add(29);col2.add("wanwan");Student s1 = new Student("wanfeng", 12);col2.add(s1);col1.addAll(col2);System.out.println(col1);// isEmpty()	判断集合是否有元素System.out.println(col1.isEmpty());// clear()	清空所有元素col1.clear();System.out.println(col1);// contains()	元素是否存在，ArrayList源码中调用的是Object类的equals方法（==比较地址值），// 若要比较内容需要在类中重写equals方法System.out.println(col2.contains(34.56));System.out.println(col2.contains("wanfeng"));System.out.println(col2.contains(s1));System.out.println(col2.contains(new Student("wanfeng", 12)));// containsAll()	集合中的元素是否全部存在Collection col3 = new ArrayList();col3.add("wanwan");col3.add(false);System.out.println(col2.containsAll(col3));// remove(Object o)	删除指定元素 若为自定义类也需要重写equals方法System.out.println(col2.remove("fengfeng"));System.out.println(col2.remove(new Student("wanfeng", 12)));// removeAll(Collection c) 删除c中包含的所有元素System.out.println(col2.removeAll(col3));System.out.println(col2);//retainAll(Collection c) 取交集Collection col4 = new ArrayList();col4.add(34.56);col4.add(true);col2.retainAll(col4);System.out.println(col2);// equals(Object o)	比较两个集合是否相同col2.add(true);Collection col5 = new ArrayList();col5.add(true);col5.add(34.56);System.out.println(col2.equals(col5));// hashCode()	返回哈希值System.out.println(col2.hashCode());// toArray()	转换为数组Object[] arr = col2.toArray();for(int i=0; i<arr.length; i++){if(i > 0) System.out.print(" ");System.out.print(arr[i]);}System.out.println();// Arrays.asList()数组转换为集合List<Object> list = Arrays.asList(arr);System.out.println(list);// iterator()	返回迭代器，用于集合遍历}}class Student{private String name;private int id;public Student() {}public Student(String name, int id) {this.name = name;this.id = id;}@Overridepublic boolean equals(Object o) {System.out.println("Student.equals([o]): 执行成功~");if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;Student student = (Student) o;if (id != student.id) return false;return name != null ? name.equals(student.name) : student.name == null;}
}

iterator迭代器

Iterator对象称为迭代器，主要用于遍历Collection集合中的元素。Iterator提供一种方法访问一个容器对象中各个元素，而又不需要暴露该对象的内部细节。迭代器模式，就是为容器而生。

/*
iterator()	返回迭代器，用于集合遍历iterator.next()		迭代器后移，并返回当前指向元素（未开始遍历时指向第一个元素的前面）iterator.hasNext() 	后面是否存在元素
*/
Iterator iterator = col2.iterator();
while (iterator.hasNext()){System.out.println(iterator.next());
}

foreach遍历

Collection col2 = new ArrayList();
col2.add(false);
col2.add(34.56);
col2.add(29);
col2.add("wanwan");
col2.add("jingyu");//本质也是用了iterator
//item是元素的拷贝，而不是元素本身
for(Object item : col2){System.out.println(item);
}

三、List接口

List接口存储有序、可重复的元素。

List接口实现类

相同点：三个类都实现了List接口，存储数据的特点都是有序的、可重复的

不同点：

• ArrayList：List的主要实现类。线程不安全，效率高。底层使用Object[]存储
• LinkedList：频繁使用插入、删除操作时效率高，底层使用双向链表存储。
• Vector：List的古老实现类（JDK1.0）。线程安全，效率低。底层使用Object[]存储

四、ArrayList

源码分析：使用空参构造器ArrayList()时，底层Object[] elementData初始化为{ }，在第一次添加进行扩容调用grow。（JDK8）

public class ListTest {@Testpublic void test1(){ArrayList list = new ArrayList(10);System.out.println(list.size());list.add(11);list.add(22);list.add(33);list.add("wanfeng");list.add(new Student("jingyu", 13));System.out.println(list);// add(int index, Object o)	将元素添加到索引位置list.add(1, "feng");System.out.println(list);// addAll(int index, Collection c)	将集合c中的所有元素添加到索引位置Collection col2 = new ArrayList();col2.add(false);col2.add(34.56);col2.add(22);col2.add("wanwan");col2.add("jingyu");list.addAll(2, col2);System.out.println(list);// size()	元素个数System.out.println(list.size());// get(int index)	获取索引位置的元素System.out.println(list.get(7));// indexOf(Object o)	元素首次出现的索引位置，找不到返回-1System.out.println(list.indexOf(22));System.out.println(list.indexOf(999));// lastIndexOf(Object o)	元素最后一次出现的索引位置System.out.println(list.lastIndexOf(22));// remove(int index) / remove(Object o)	删除元素Object remove = list.remove(1);list.remove(new Integer(22));System.out.println(list);// set(int index, Object o)	修改指定位置的元素为olist.set(1, new Integer(987));System.out.println(list);// subList(int start, int end)	返回指定范围的子集合，左闭右开List sub = list.subList(2, 8);System.out.println(sub);// iterator迭代器遍历Iterator iterator = list.iterator();while(iterator.hasNext()){System.out.println(iterator.next());}// foreach 增强for循环for(Object item : list){System.out.println(item);}}
}

五、LinkedList

源码分析：使用空参构造器LinkedList()时，底层声明了Node类型的first和last属性，默认值为null

常用方法与ArrayList基本一致

六、Set接口

存储无序、不可重复的数据。无序不等于随机，以HashSet为例，数据添加时并非按照索引顺序添加，而是根据数据的hash值顺序添加。不可重复性是指添加的元素按照equals判断时，不能返回true，即只能添加一个。

Set接口中没有新的方法，都是Collection中的方法

在实际应用中，Set常用来过滤重复数据

Set接口实现类

• HashSet：Set主要实现类，线程不安全，可以存储null
• LinkedHashSet：HashSet的子类。遍历时可按照添加顺序遍历
• TreeSet：底层使用红黑树存储。存储的数据必须是同一个类型，可以按照添加对象的指定属性进行排序

七、HashSet

底层是一个数组（默认长度为16）。

HashSet添加元素的机制

当添加数据时，取得hash值，根据hash函数放入数组指定的位置。若该位置上已有元素，则比较二者hashCode（若类中没有重写调用Object类中的hashCode，这个方法生成的hasCode是随机的），若不同则添加成功，以链表形式和已有元素连接。若hash值相同则调用equals方法比较，若为false代表不重复，添加成功，否则添加失败。

在Set中添加数据需要注意的规则

• 添加的数据所在类一定要重写hashCode()和equals()

• equals里用到的属性和hashCode里用到的属性相同

IDEA工具中对hashCode()的重写为什么常出现31这个数字？

选择系数应尽量选择较大的系数，增加hash地址，减少冲突，提高查找效率。31只占用5bit，相乘造成数据溢出的概率较小。i * 31 == (i<<5) - 1，很多虚拟机里都有相关优化。31是一个素数，其他数和31相乘的结果只能被素数本身和这个其他数整除，减少冲突.

八、LinkedHashSet

底层结构与HashSet相同，都是数组，但是添加了双向链表结构，遍历时以链表形式遍历而不是数组，因此可以以添加顺序遍历

九、TreeSet

添加的数据必须是相同类的对象，添加后自动排序，需要实现Comaprable接口，同时实现的ComapreTo方法也用来判断两个元素是否重复

• 自然排序：实现Comaprable接口，比较两个对象是否重复的标准是compareTo()是否返回0
• 定制排序：声明一个Comparator接口的匿名子类的对象（实现compare方法），将该对象作为TreeSet构造器参数时，TreeSet将会以compare方法比较两个对象是否重复

public class SetTest {// Tree自然排序@Testpublic void test3(){TreeSet set1 = new TreeSet();set1.add(10);set1.add(34);set1.add(6);set1.add(18);set1.add(-9);for(Iterator iterator= set1.iterator(); iterator.hasNext(); ){System.out.println(iterator.next());}TreeSet studentSet = new TreeSet();// Student需要实现Comparable接口studentSet.add(new Student("wanfeng", 12));studentSet.add(new Student("jingyu", 20));studentSet.add(new Student("wanwan", 15));studentSet.add(new Student("jingjing", 13));studentSet.add(new Student("jingjing", 34));for(Iterator iterator= studentSet.iterator(); iterator.hasNext(); ){System.out.println(iterator.next());}}// TreeSet定制排序@Testpublic void test4(){Comparator comparator = new Comparator() {@Overridepublic int compare(Object o1, Object o2) {if(o1 instanceof Student && o2 instanceof Student){Student s1 = (Student) o1;Student s2 = (Student) o2;return s1.getId() - s2.getId();}else{throw new RuntimeException("类型不一致");}}};// 以comparator比较器作为比较标准TreeSet studentSet = new TreeSet(comparator);studentSet.add(new Student("wanfeng", 12));studentSet.add(new Student("jingyu", 20));studentSet.add(new Student("wanwan", 15));studentSet.add(new Student("jingjing", 13));studentSet.add(new Student("jingjing", 34));for(Iterator it=studentSet.iterator(); it.hasNext(); ){System.out.println(it.next());}}
}

十、Map接口

存储键值对（key-value)

Map接口实现类

• HashMap：Map接口的主要实现类；线程不安全，效率高；可以存储null
  • LinkedHashMap：HashMap的子类。在HashMap基础上增加了链表结构，按添加顺序遍历。对于频繁遍历操作，效率优于HashMap
• TreeMap：添加键值对时进行排序（按key排序的自然排序、定制排序）。底层使用红黑树
• Hashtable：Map接口的古老实现类；线程安全，效率低；不能存储null
  • Properties：处理配置文件，key-value都是String类型

Map常用方法（HashMap）

@Test
public void test2(){Map map1 = new HashMap();// put(Object key, Object value)	添加键值对map1.put("BB", 12);map1.put("AA", 23);map1.put("CC", 34);System.out.println(map1);// putAll(Map m)	将m中的键值对全部添加Map map2 = new HashMap();map2.put("wanfeng", 23);map2.put("jingyu", 21);map1.putAll(map2);System.out.println(map1);// remove(Object key)	根据key删除键值对,返回valueObject remove_value = map1.remove("AA");System.out.println("remove_value: "+remove_value);System.out.println(map1);// clear()	删除所有键值对map2.clear();System.out.println("map2 size: "+map2.size());System.out.println(map2);// get(Object key)	获取key对应的valueObject get_value = map1.get("wanfeng");System.out.println("get_value: "+get_value);// containsKey(Object key)	是否包含keySystem.out.println(map1.containsKey("jingyu"));// containsValue(Object value)	是否包含valueSystem.out.println(map1.containsValue(23));// size()	获取键值对个数System.out.println("map1 size: "+map1.size());// isEmpty()	map是否为空System.out.println(map1.isEmpty());System.out.println(map2.isEmpty());// equals(Map m)	判断两个map是否相同System.out.println(map1.equals(map2));
}

Map遍历（HashMap）

@Test
public void test3(){Map map1 = new HashMap();map1.put("BB", 12);map1.put("AA", 23);map1.put("CC", 34);System.out.println(map1);// 遍历key：拿到keySet再用iterator遍历Set keyset = map1.keySet();for(Iterator it=keyset.iterator(); it.hasNext(); ){System.out.println(it.next());}// 遍历value，拿到Collection，再用iterator或增强for循环遍历Collection values = map1.values();for(Object value : values){System.out.println(value);}// 第一种方式：遍历key-value拿到EntrySet，使用iterator遍历，// 每一个Entry调用 getKey() 和 getValue() 获取。// 第二种方式，遍历key的时候调用get(Object key)同时遍历valueSet entrySet = map1.entrySet();for(Iterator it=entrySet.iterator(); it.hasNext(); ){Object o = it.next();Map.Entry entry = (Map.Entry) o;System.out.println(entry.getKey() + " --> " + entry.getValue());}}

十一、HashMap

JDK7以前底层结构为数组+链表，JDK8以后增加了红黑树

Map的结构

• key：无序、不可重复，用Set存储所有key（key所在类要重写hashCode和equals）
• value：无序、可重复，用Collection存储所有key
• key-value：一个Entry对象，无序、不可重复，用Set存储所有Entry

HashMap底层实现原理

JDK7

• 创建HashMap对象后，底层创建了长度为16的数组Entry[] table
• put(key1, value1) 添加键值对时，调用key1所在类的hashCode获取hash值并经过indexFor（和数组长度-1的与运算）得到这个Entry的存放位置，如果此位置没有数据则添加成功。如果此位置已有数据，比较key1的hash值和已有数据的hash值
  • 若hash值不相同，则添加成功（链表存储）
  • 若hash值相同，调用equals进行比较
    • 若返回false，添加成功（链表存储）
    • 若为true，用value1替换已有数据的value
• 在不断添加过程中，当超过临界值（threshold）且添加的位置已有元素时，扩容为原来的2倍

JDK8

• 创建HashMap对象后，底层没有创建长度16的数组
• 数组的类型是Node[]，而不是Entry[]
• 首次调用put方法时，底层创建长度为16的数组
• 当数组某个索引位置（链表）上的元素个数 > 8 且当前数组长度 > 64时，此索引位置上的链表改为红黑树存储
• HashMap中的常量和变量
  • DEFAULT_INITIAL_CAPACITY = 16：默认容量
  • DEFAULT_LOAD_FACTOR = 0.75：默认加载因子
  • threshold：扩容临界值 = 容量 * 加载因子
  • TREEIFY_THRESHOLD = 8：Bucket中链表长度大于默认值时，转化为红黑树
  • MIN_TREEIFY_CAPACITY = 64：链表转化为红黑树时的最小hash表容量

十二、LinkedHashMap

在添加数据时与HashMap不同，将键值对添加进数组或链表时，创建了新的Entry对象（重写了HashMap的newNode方法），这个Entry类是带有before和after两个指针指向前后的元素，形成双向链表。

十三、TreeMap

向TreeMap中添加key-value，要求key必须都是同一个类的对象，因为要按照key排序（自然排序、定制排序）

void showTreeMap(TreeMap tm){if(tm == null)	return;Set keyset = tm.keySet();for(Iterator it=keyset.iterator(); it.hasNext(); ){Student key = (Student) it.next();System.out.println(key + " --> " + tm.get(key));}
}@Test
public void TreeMapTest(){//自然排序TreeMap map1 = new TreeMap();map1.put(new Student("wanfeng", 23), 11);map1.put(new Student("jingyu", 21), 55);map1.put(new Student("wanwan", 25), 44);map1.put(new Student("fengfeng", 18), 22);showTreeMap(map1);//定制排序（与TreeSet原理相同，此处用的是Comparator接口的匿名实现类的匿名对象）TreeMap map2 = new TreeMap(new Comparator() {@Overridepublic int compare(Object o1, Object o2) {if(o1 instanceof Student && o2 instanceof Student){Student s1 = (Student) o1;Student s2 = (Student) o2;// name倒序return -s1.getName().compareTo(s2.getName());}throw new RuntimeException("类型不匹配");}});map2.put(new Student("wanfeng", 23), 11);map2.put(new Student("jingyu", 21), 55);map2.put(new Student("wanwan", 25), 44);map2.put(new Student("fengfeng", 18), 22);showTreeMap(map2);
}

十四、Properties

Hashtable的子类，处理属性文件。键值对都是String类型

@Test
public void propertiesTest(){FileInputStream fis = null;FileOutputStream fos = null;try {Properties properties = new Properties();// 得到文件输入流fis = new FileInputStream("src/com/lzh/Map/mypro.properties");// 将文件输入流加载进Properties对象中properties.load(fis);// 获取属性System.out.println(properties.getProperty("username"));System.out.println(properties.getProperty("password"));//设置属性properties.setProperty("id", "27");fos = new FileOutputStream("src/com/lzh/Map/mypro.properties");properties.store(fos, "comment");} catch (IOException e) {e.printStackTrace();} finally {try {if(fis != null)	fis.close();if(fos != null) fos.close();} catch (IOException e) {e.printStackTrace();}}
}

十五、Collections工具类

@Test
public void test1(){ArrayList list = new ArrayList(10);list.add("wanfeng");list.add("zhipeng");list.add("jingyu");list.add("xinxin");System.out.println(list.size());System.out.println(list);//reverse(list)	反转ListCollections.reverse(list);System.out.println("reverse: " + list);// shuffle(list)	随机排序ListCollections.shuffle(list);System.out.println("shuffle: "+ list);// sort(list)	自然排序，升序Collections.sort(list);System.out.println("自然排序："+list);// sort(list, Comparator c)	定制排序Collections.sort(list, new Comparator<Object>() {@Overridepublic int compare(Object o1, Object o2) {if(o1 instanceof String && o2 instanceof String){String s1 = (String) o1;String s2 = (String) o2;return -s1.compareTo(s2);}throw new RuntimeException("类型不匹配");}});System.out.println("定制排序："+list);// swap(index1, index2)	交换两个索引位置的元素Collections.swap(list, 0, 2);System.out.println("swap："+list);// max(Collection)	获取最大值（自然排序）// max(Collection, Comparator)	获取最大值（定制排序）// min(Collection)	获取最小值（自然排序）// min(Collection, Comparator)	获取最小值（定制排序）//frequency(Collection, Object)	返回集合中指定元素的出现次数System.out.println(Collections.frequency(list, "wanfeng"));// copy(List list1, List list2)	将list2对应索引位置的元素复制到list1中// 		list2.size() > list1.size()	抛出IndexOutOfBoundsExceptionArrayList list2 = new ArrayList();list2.add("345");list2.add("111");Collections.copy(list, list2);System.out.println(list);// replaceAll(List list, Object oldVal, Object newVal)	将list中的所有旧值改为新值Collections.replaceAll(list, "zhipeng", "newval");System.out.println(list);// Collection同步控制// synchronizedCollection(Collection)// synchronizedList(List)	ArrayList线程不安全// synchronizedMap(Map)		HashMap线程不安全List syncList = Collections.synchronizedList(list);	//返回线程安全的List
}