Java:集合(List、Map、Set)

1. Collection集合

本身为一个接口。


包括List、Set集合两种。其中List集合添加的元素有序、可重复、有索引，下面有两个实现类，分别为ArrayList、LinkedList。而Set集合添加的元素是无序的、不重复的、无索引的。它的实现类有HashSet、LinkedHashSet、TreeSet，需要注意的是LinkedHashSet中的元素是有序的，TreeSet中的元素是按照大小默认升序进行排序的。

1-1. 迭代器遍历方式

package jh_study;import java.util.*;public class JHStudy {public static void main(String[] args) {Collection<String> c = new ArrayList<>();for (int i = 0; i < 4; i++) {c.add(String.valueOf(i+1));}Iterator<String> iterator = c.iterator();while(iterator.hasNext()){System.out.println(iterator.next());}}
}

通过集合对象".iterator()"获取其迭代器对象，然后通过“迭代器对象.hasNext()”方法来判断是否已经到末尾；没有到末尾的话，可以通过“迭代器对象.next()”获取对应的元素值，不过获取到元素值之后，其对应的索引(或者指针节点)会指向下一个位置。

1-2. 通过for循环进行遍历

package jh_study;import java.util.*;public class JHStudy {public static void main(String[] args) {Collection<String> c = new ArrayList<>();for (int i = 0; i < 4; i++) {c.add(String.valueOf(i+1));}for (String s : c) {System.out.println(s);}}
}

这种方式遍历集合，本质上就是迭代器遍历集合的简化写法。

1-3. forEach遍历

package jh_study;import java.util.*;
import java.util.function.Consumer;public class JHStudy {public static void main(String[] args) {Collection<String> c = new ArrayList<>();for (int i = 0; i < 4; i++) {c.add(String.valueOf(i+1));}// 匿名内部类写法c.forEach(new Consumer<String>() {@Overridepublic void accept(String s) {System.out.println(s);}});// 简化c.forEach((e)->{System.out.println(e);});// 再简化c.forEach((e)-> System.out.println(e));// 再简化c.forEach(System.out::println);}
}

Collection是一个接口，因此实现了该接口对应的类都具备其下的方法。

2. List集合

遍历元素方式除了上述三种之外，还可以通过下标索引进行遍历，当然需要使用到for循环

package jh_study;import java.util.*;public class JHStudy {public static void main(String[] args) {List<Integer> l = new ArrayList<>();l.add(12);l.add(0);for (int i = 0; i < l.size(); i++) {System.out.println(l.get(i));}}
}

2-1. ArrayList底层实现原理

底层实现是基于数组实现的，查看源代码可以发现。


根据索引查询速度快（查询数据通过地址值和索引进行定位，查询任意数据耗时相同），删除效率低（可能需要把后面很多的数据进行前移），添加效率低（可能需要把后面很多的数据后移，再添加元素；或者也可能需要进行数组扩容。）

ArrayList底层实现原理：
1.利用无参构造器创建的集合，会在底层创建一个默认长度为0的数组；
2.添加第一个元素时，底层会创建一个新的长度为10的数组；


3.存满时，会扩容1.5倍；

如果一次添加多个元素，1.5倍还放不下，则新创建的数组的长度以实际为准；

2-2. LinkedList底层实现原理

底层实现是双向链表。


LinkedList的应用场景：实现栈(后进先出)、队列(先进先出)。

3. Set集合

正如上述所说，常见的set集合类型有HashSet、LinkedHashSet、TreeSet。其中，HashSet特点为无序、不重复、无索引；LinkedHashSet特点为有序、不重复、无索引；TreeSet特点为升序、不重复、无索引。

package jh_study;import java.util.*;public class JHStudy {public static void main(String[] args) {Set<Integer> set = new HashSet<>();Set<Integer> set1 = new LinkedHashSet<>();Set<Integer> set2 = new TreeSet<>();System.out.println("HashSet集合");set.add(333);set.add(2222);set.add(1111);set.add(2333);System.out.println(set);System.out.println("LinkedHashSet集合");set1.add(333);set1.add(2222);set1.add(1111);set1.add(2333);System.out.println(set1);System.out.println("TreeSet集合");set2.add(333);set2.add(2222);set2.add(1111);set2.add(2333);System.out.println(set2);}
}

3-1. HashSet 底层实现

关于hash值，就是一个int类型的数值，Java中每一个对象都有一个hash值；Java中所有的对象，都可以通过调用Object类提供的hashCode方法，返回该对象自己的hash值。
hash值的特点：同一个对象多次调用hashCode方法返回的hash值是相同的；不同对象，它们的hash值一般不相同，但是也有可能相同（hash碰撞）。

HashSet底层原理：是基于hash表实现的，hash表是一种增删改查数据性能都较好的数据结构。在jdk8之前，hash表的实现是基于数组+链表实现的；jdk8之后，hash表的实现是基于数组+链表+红黑树实现的。
jdk8之前的哈希表底层实现为：创建一个默认长度为16的数组，默认加载因子为0.75（也就是当长度为12时，会进行扩容操作，原数组中的元素会添加到新数组当中去）；使用元素的哈希值对数组长度求余计算出应存入的位置；判断当前位置是否为null，如果为null直接存入，如果不为null，表示该位置有元素，则调用equals方法进行比较，相等，则不存，不相等，则存入数组，也就是在数组对应的位置上创建链表，元素存入到链表中进行存储。在jdk8之后，当链表长度超过8，并且数组长度大于或等于64时，自动将链表转换为红黑树。

jdk8之前的Hash表结构。

jdk8之后的Hash表结构。
如果在HashSet中有两个内容相同但是它们hash值不同，此时如果我们想去重的话，需要重写其hashCode和equals方法。

package jh_study;import java.util.HashSet;
import java.util.Objects;
import java.util.Set;class User{private String name;private Integer age;public User(String name, Integer age) {this.name = name;this.age = age;}@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;User user = (User) o;return Objects.equals(name, user.name) && Objects.equals(age, user.age);}@Overridepublic int hashCode() {return Objects.hash(name, age);}@Overridepublic String toString() {return "User{" +"name='" + name + '\'' +", age=" + age +'}';}
}public class JHStudy2 {public static void main(String[] args) {Set<User> users = new HashSet<>();users.add(new User("张三",20));users.add(new User("张三",20));System.out.println(users);}
}

3-2. LinkedHashSet 底层实现

LinkedHashSet为HashSet的子类，底层实现依旧是基于哈希表(数组、链表、红黑树)实现的。但是，它的每个元素都额外的多了一个双链表的机制记录它前后元素的位置。

3-3. TreeSet

底层实现基于红黑树实现的升序排序(默认情况下)，特点是不重复、无索引、可排序（默认升序排序）。如果在TreeSet中存储的数类型为自定义类型(比如Student)，此时如果打印输出结果会报错，因此TreeSet类型并不知道通过Student那个属性进行计较，此时可以在Student类下，让其实现Comparable接口，并重写方法compareTo；当然，也可以直接在定义TreeSet类型的变量时，给上参数new Comparator比较器对象，让其实现方法compare。

package jh_study;import java.util.*;public class JHStudy3 {public static void main(String[] args) {Set<Integer> set = new TreeSet<>(new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o2-o1;}});// 简化写法/*Set<Integer> set = new TreeSet<>((a,b)->{return b - a;});*/set.add(3);set.add(1);set.add(2);System.out.println(set);}
}

如果上述两种都设置了，类对象实现了Comparable接口，定义TreeSet变量时指定了比较器，那么采用就近原则上那个（也就是比较器）来进行排序的。

4. Collection集合->总结

1. 如果希望记住元素的添加顺序，需要存储重复的元素，又要频繁的根据索引查询数据，可以采用ArrayList集合类型（底层实现基于数组，特点是有序、可重复、有索引）；
2. 如果希望记住元素的添加顺序，且增删首尾数据的情况较多，可以采用LinkedList集合类型（底层实现基于双链表，特点是有序、可重复、有索引）；
3. 如果不在意元素顺序，也没有重复元素需要存储，只希望增删查改都快，可以采用HashSet集合类型；（底层实现基于哈希表，特点是无序、不重复、无索引）
4. 如果希望记住元素的添加顺序，也没有重复元素需要存储，且希望增删改查都快，可以采用LinkedHashSet集合类型（底层实现基于哈希表和双链表，特点为有序、不重复、无索引）；
5. 如果要对元素进行排序，也没有重复元素需要存储，且希望增删改查都快，可以采用TreeSet集合类型（底层实现基于红黑树，特点为升序、不重复、无索引）；

5. Map集合

键值对集合，键不能重复，值可以重复。
常见的比如HashMap（无序、不重复、无索引）、TreeMap（有序、不重复、无索引）、LinkedHashMap（按照大小默认升序排序，不重复，无索引）。

package jh_study;import java.util.*;public class JHStudy4 {public static void main(String[] args) {Map<String, String> map = new HashMap<>();map.put(null,null);map.put("张三","男");map.put("李四","女");map.put("嘻嘻1","MyDream");System.out.println(map);// {null=null, 李四=女, 张三=男, 嘻嘻1=MyDream}System.out.println(map.get("张三"));//男 ，获取键对应的值System.out.println(map.get("赵六"));// null ,不存在的键System.out.println(map.containsKey("李四"));// 判断是否存在某个键 true// map.clear();// 清空map中的数据Set<String> set = map.keySet();System.out.println(set);// 获取所有的键 [null, 李四, 张三, 嘻嘻1]System.out.println(map.isEmpty());// 判断map是否为空 falseSystem.out.println(map.values());// 获取map中所有的值 [null, 女, 男, MyDream]System.out.println(map.size());// 获取map的长度 4System.out.println(map.remove("张三"));// 删除某个键,并返回这个键对应的值 男}
}

5-1. 通过键找值-进行遍历

通过Map对象的 keySet() 方法获取对应的键集合，然后通过遍历键集合来获取对应的值。

package jh_study;import java.util.*;public class JHStudy4 {public static void main(String[] args) {Map<String, String> map = new HashMap<>();map.put(null,null);map.put("张三","男");map.put("李四","女");map.put("嘻嘻1","MyDream");map.put("赵六","man");Set<String> keys = map.keySet();for (String key : keys) {System.out.println(key+"->"+map.get(key));}}
}

5-2. 键值对进行遍历

通过Map对象的 entrySet() 方法获取键值对集合，然后对这个集合进行遍历即可。

package jh_study;import java.util.*;public class JHStudy4 {public static void main(String[] args) {Map<String, String> map = new HashMap<>();map.put(null,null);map.put("张三","男");map.put("李四","女");map.put("嘻嘻1","MyDream");map.put("赵六","man");Set<Map.Entry<String, String>> set = map.entrySet();for (Map.Entry<String, String> entry : set) {System.out.println(entry.getKey()+"=>"+entry.getValue());}}
}

5-3. 通过Lambda表达式进行遍历

package jh_study;import java.util.*;
import java.util.function.BiConsumer;public class JHStudy4 {public static void main(String[] args) {Map<String, String> map = new HashMap<>();map.put(null,null);map.put("张三","男");map.put("李四","女");map.put("嘻嘻1","MyDream");map.put("赵六","man");map.forEach(new BiConsumer<String, String>() {@Overridepublic void accept(String s, String s2) {System.out.println(s+" "+s2);}});// 简化map.forEach((k,v)-> System.out.println(k+" "+v));}
}

5-4. HashMap 底层实现

HashMap和HashSet的底层实现原理都是一样的，都是基于哈希表实现的。在JDK8之前，其哈希表基于数组+链表；JDK8之后，其哈希表基于数组+链表+红黑树实现。

5-5. LinkedHashMap 底层原理

LinkedHashMap 和 LinkedHashSet的底层原理是一样的。

5-6. TreeMap 底层原理

TreeMap和TreeSet的底层实现原理都是一样的。

如果要对数据进行排序，也有两种方式，和TreeSet一样，参考代码如下：
方法1：让需要排序的对象数据实现Comparable即可，并重写方法compareTo。

package jh_study;import java.util.*;public class JHStudy4 {public static void main(String[] args) {Map<User4, Integer> map = new TreeMap<>();map.put(new User4("张三",23),0);map.put(new User4("李四",12),1);map.put(new User4("王五",10),2);map.put(new User4("赵六",25),3);System.out.println(map);}
}class User4 implements Comparable<User4>{String name;Integer age;public User4(String name, Integer age) {this.name = name;this.age = age;}@Overridepublic String toString() {return "User4{" +"name='" + name + '\'' +", age=" + age +'}';}@Overridepublic int compareTo(User4 o) {return o.age - this.age;}
}

方法2：通过比较器，参考代码如下：

package jh_study;import java.util.*;public class JHStudy4 {public static void main(String[] args) {Map<User4, Integer> map = new TreeMap<>(new Comparator<User4>() {@Overridepublic int compare(User4 o1, User4 o2) {return o1.age-o2.age;}});map.put(new User4("张三",23),0);map.put(new User4("李四",12),1);map.put(new User4("王五",10),2);map.put(new User4("赵六",25),3);System.out.println(map);}
}