Java 集合可分为Collection(存储元素集合)；Map(存储键/值对映射).

9.1 Collection接口

image.png
JDK不提供Collection接口的直接实现，所有实现了该接口的方法都将具有如下方法。

  1. add(Object obj)
  2. addAll(Collection coll)
  3. int size()
  4. void clear()
  5. boolean isEmpty()
  6. boolean contains(Object obj) // 通过元素的equals方法来判断是否包含该对象 
  7. boolean containsAll(Collection c)
  8. boolean remove(Object obj) // 通过元素的equals方法删除找到的第一个元素 
  9. boolean removeAll(Collection coll) // 取当前集合的差集 
  10. boolean retainAll(Collection c) // 把交集的结果存在当前集合中，不影响c 
  11. boolean equals(Object obj) // 集合是否相等 
  12. Object[] toArray() // 转成对象数组
  13. hashCode() // 获取集合对象的哈希值
  14. iterator() // 返回迭代器对象

9.1.1 Iterator迭代器接口

Iterator用于遍历Collection集合中的元素。

  1. Iterator iter = coll.iterator(); // 获取迭代器对象，默认游标在集合的第一个元素之前。
  2. while(iter.hasNext()){ 
  3.     Object obj = iter.next(); // 先移动游标，再获取元素
  4.     if(obj.equals("Tom")){ // 删除迭代器所指位置元素。
  5.          iter.remove();
  6.      } 
  7. }
  1. // for-each遍历集合的底层调用Iterator完成，修改person对象不影响persons数据
  2. for(Person person: persons)

9.1.2 Collection子接口——List接口

List除了从Collection集合继承的方法外，还添加了一些根据索引来操作集合元素的方法。

  1. void add(int index, Object ele)
  2. boolean addAll(int index, Collection eles)
  3. Object get(int index)
  4. int indexOf(Object obj):返回obj在集合中首次出现的位置
  5. int lastIndexOf(Object obj):返回obj在集合中末次出现的位置
  6. Object remove(int index)
  7. Object set(int index, Object ele)
  8. List subList(int fromIndex, int toIndex)

9.1.2.1 ArrayList变长数组

其一开始创建一个长度为0的数组，当添加第一个元素时将数组的容量改为10。方法Arrays.asList(T…a) 可将传入的可变参数a封装为ArrayList并返回固定长度的 List 集合。

9.1.2.2 LinkedList双向链表

对于频繁插入或删除元素的情况建议使用LinkedList类，效率较高。其内部以Node为节点，并使用双向链表实现。

  1. void addFirst(Object obj) 
  2. void addLast(Object obj) 
  3. Object getFirst() 
  4. Object getLast() 
  5. Object removeFirst()

9.1.2.3 Vector线程安全变长数组

Vector大多数操作与ArrayList 相同，区别之处在于Vector是线程安全的。

  1. void addElement(Object obj) 
  2. void insertElementAt(Object obj,int index) 
  3. void setElementAt(Object obj,int index) 
  4. void removeElement(Object obj) 
  5. void removeAllElements()

9.1.2.4 三者的异同

ArrayList和LinkedList的异同:二者都线程不安全，相对Vector执行效率高。ArrayList基于动态数组，LinkedList基于双向链表。对于随机访问ArrayList优，因为LinkedList要移动指针。对于插入和删除，LinkedList优，因为ArrayList要移动数据。

ArrayList和Vector的区别:Vector是强同步的，因此开销比ArrayList要大。大多数情况下使用 ArrayList，因为同步完全可以由程序员自己来控制。Vector每次扩容请求其大小的2倍空间，而ArrayList是1.5倍。Vector还有一个子类Stack。

扩容的底层操作是创建预定大小的新数组，并将原数据复制到新数组中。因此若已经知道数组长度，则在创建时最好指明长度，防止中间扩容降低效率。优先使用ArrayList，当插入、删除频繁时， 使用LinkedList；Vector总是比ArrayList慢，所以尽量避免使用。

9.1.3 Collection子接口——Set接口

Set不允许包含相同的元素。Set存储的数据在底层数组中根据数据的哈希值存储。

9.1.3.1 HashSet：数组哈希集合

HashSet 按 Hash 算法来存储集合中的元素，因此具有很好的存取、查找、删除性能。其具有不能保证元素的排列顺序 、线程不安全、集合元素可以是 null三个特点。底层也是数组，初始容量为16，如果使用率超过0.75，就会扩大容量为原来的2倍。hashSet底层是由hashMap实现的，hashMap是由哈希表实现的。

当向 HashSet 中存入元素时，HashSet 首先通过 hashCode() 获得对象的hashCode值，再通过某种散列函数决定该对象在 HashSet 底层数组中的存储位置，若该位置无元素则插入。否则比较两个对象的hashCode数值，不等再比较两个对象 equals() 方法返回值，若不等则用链表的方式链接到该位置。 因此，使用Set容器的类一定要重写equals()和hashCode(Object obj)方法(推荐使用IDEA自动生成的)。若不重写类的hashCode方法，则默认调用Object的此方法，该方法所生成的hashCode数值是随机的。

9.1.3.2 LinkedHashSet：双向链表哈希集合

LinkedHashSet 是 HashSet 的子类，其根据元素的 hashCode 值来决定元素的存储位置，但它同时使用双向链表维护元素的次序，这使得在遍历时，可以按照添加的顺序遍历。由于使用了链表，LinkedHashSet插入性能略低于 HashSet，但在迭代访问全部元素时有很好的性能。
image.png

9.1.3.3 TreeSet：红黑树集合

TreeSet 是 SortedSet 接口的实现类，可以确保集合元素处于排序状态，其查询速度比List快。其可以按照添加对象的指定属性进行排序，自定义的对象必须实现相应的自然排序或定制排序方法。它判断两个对象是否相等的唯一标准是：两个对象通过比较方法比较的返回值。因此必须重写 equals() 和compareTo(Object obj) ，且要保证 equals() 与 compareTo(Object obj) 有一致的结果， 否则，让人难以理解。

9.2 Map接口

image.png
Map 中的key 用Set来存放，不允许重复，因此key对象所对应的类须重写hashCode()和equals()方法。

  1. 添加、删除、修改操作:
  2. Object put(Object key,Object value):将指定key-value添加或修改当前map对象中
  3. void putAll(Map m)
  4. Object remove(Object key):移除指定key的key-value对，并返回value
  5. void clear()
  7. 元素查询的操作:
  8. Object get(Object key):获取指定key对应的value
  9. boolean containsKey(Object key)
  10. boolean containsValue(Object value)
  11. int size()
  12. boolean isEmpty()
  13. boolean equals(Object obj):判断当前map和参数对象obj是否相等
  15. 元视图操作的方法:
  16. Set keySet():返回所有key构成的Set集合
  17. Collection values():返回所有value构成的Collection集合
  18. Set entrySet():返回所有key-value对构成的Set集合
  1. // 映射关系的类型是Map.Entry类型，它是Map接口的内部接口
  2. Set mappings = map.entrySet();
  3. for (Object mapping : mappings) {
  4.     Map.Entry entry = (Map.Entry) mapping;
  5.     System.out.println("key是：" + entry.getKey() + "，value是：" + entry.getValue());
  6. }

9.2.1 HashMap：数组哈希映射

HashMap允许使用null键和null值，不保证映射的顺序。一个key-value构成一个特殊类对象Node。所有的Node构成的集合是Set。当两个key通过equals()方法返回true,hashCode值也相等时，两个key才相等。当两个value通过equals()方法返回true时，两个value才相等。
image.png

  1. HashMap底层实现(1.8)：数组+链表+红黑树
  2. HashMap map  = new HashMap();
  3. map.put(key1, value1); // 首次调用put时创建长度为16的数组
  4. /*put流程：
  5. * 首先,调用key1所在类的hashCode()计算key1哈希值,此哈希值经过某种算法计算以后,得到在Node数组中的存放位置。
  6. * 如果此位置上的数据为空,此时的key1-value1添加成功
  7. * 如果此位置上的数据不为空,比较key1和已经存在的一个或多个数据的哈希值:
  8. *     如果key1的哈希值与已经存在的数据的哈希值都不相同,key1-value1添加成功---情况2
  9. *     如果key1的哈希值和已经存在的某一个数据(key2-value2)的哈希值相同,调用key1所在类的 equals(key2)
  10. *         如果 equals()返回faLse:此的key1-vaue1添加成功---情况3
  11. *         如果 equals()返回true:使用value1替换 value2。
  12. * 
  13. * 当数组的某一个索引位置上的元素以链表形式存在的数据个数>8且当前数组的长度>64时,此时此索引位置上的所有数据改为使用红黑树存储。如果当映射关系被移除后，下次resize方法时判断树的结点个数低于6个，也会把树再转为链表。
  14. * 默认扩容为原来容量的2倍,并将原有的数据复制过来。这是非常消耗性能的，所以如果我们已知HashMap中元素的个数，预设元素的个数能够有效的提高HashMap的性能。*/
  16. Map<Integer, Integer> map = new HashMap<Integer, Integer>();
  17. for(Map.Entry<Integer, Integer> entry : map.entrySet()){
  18.     System.out.println("key = " + entry.getKey() + ", value = " + entry.getValue())
  19. }
  21. Map<Integer, Integer> map = new HashMap<Integer, Integer>();
  22. Iterator<Map.Entry<Integer, Integer>> entries = map.entrySet().iterator();
  23. while (entries.hasNext()) {
  24.     Map.Entry<Integer, Integer> entry = entries.next();
  25.     System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());
  26. }
  1. HashMap源码中的重要常量：
  2. DEFAULT_INITIAL_CAPACITY : HashMap的默认容量，16
  3. DEFAULT_LOAD_FACTOR：HashMap的默认加载因子为0.75，统计学显示该种情况比较好
  4. TREEIFY_THRESHOLD：转化为红黑树的阈值
  5. threshold：扩容的阈值 = 容量 * 填充因子
  6. loadFactor：填充因子
  1. // 负载因子值得大小对HashMap有什么影响？
  2. 负载因子的大小决定了HashMap的数据密度。
  3. 负载因子越大密度越大，发生碰撞的几率越高，数组中的链表越容易长,造成查询或插入时的比较次数增多，性能会下降。
  4. 负载因子越小，就越容易触发扩容，数据密度也越小，意味着发生碰撞的几率越小，数组中的链表也就越短，查询和插入时比较的次数也越小，性能会更高。但是会浪费一定的内容空间。
  5. 按照其他语言的参考及研究经验，会考虑将负载因子设置为0.7~0.75，此时平均检索长度接近于常数。

9.2.2 LinkedHashMap：双向链表哈希映射

LinkedHashMap是HashMap的子类。在HashMap存储结构的基础上，对每个结点增加了双向指针来记录添加元素的顺序，可以维护Map的迭代顺序:迭代顺序与Key-Value对的插入顺序一致。

9.2.3 TreeMap：红黑树映射

TreeMap存储Key-Value对时，可保证所有Key-Value处于有序状态。

  1. TreeMap的Key的排序,判断标准是比较函数的返回值：
  2. ➢自然排序: 所有的Key必须实现Comparable接口，而且所有的Key应该是同一个类的对象
  3. ➢定制排序: 创建TreeMap时，传入一个Comparator对象，该对象负责对TreeMap中的所有key进行排序。

9.2.4 HashTable及其子类Properties(线性安全)

Hashtable不同于HashMap，是线程安全的。实现原理、功能均与HashMap相同。与HashMap不同的是，Hashtable 不允许使用 null 作为 key 和 value。

Properties 类是 Hashtable 的子类，该对象用于处理配置文件（.properties)。由于属性文件里的 key、value 都是字符串类型，所以 Properties 里的 key 和 value 都是字符串类型。存取数据时，使用setProperty(String key,String value)方法和 getProperty(String key)方法。

  1. // 属性文件内容
  2. name=Tom
  3. password=123
  4. // Java访问代码
  5. Properties pros = new Properties();
  6. pros.load(new FileInputStream("jdbc.properties"));
  7. String user = pros.getProperty("name");
  8. String password = pros.getProperty("password");

9.3 Collections工具类

Collections是一个操作集合的工具类，其提供了一系列静态方法。

  1. reverse(List)
  2. shufle(List)
  3. sort(List)
  4. sort(List, Comparator)
  5. swap(List，int，int):将指定list集合中的i处元素和j处元素进行交换查
  6. Object max(Collection):根据元素的自然顺序，返回给定集合中的最大元素
  7. Object max(Collection，Comparator): 根据Comparator 指定的顺序，返回给定集合中的最大元素
  8. int frequency(Collection，Object);
  9. void copy(List dest,List src)
  10. boolean replaceAll(List list, Object oldVal，Object newVal)

Collections类可使得不支持线程同步的集合变得线程安全。
image.png