List集合/Set集合/Map集合

Love The Way You Lie 2023-09-24 14:31 308阅读 0赞

**List和Set都是Collection集合的子级接口.**

> List是序列的，有下标, 主要表现为其中的各元素在内存中是存在顺序规则的；另外，List中的元素是可以重复的，即可以向同一个List集合中反复添加相同的数据,可以存在多个null值,还可以使用get(int index)获取指定下标元素；

> Set是散列的，没有下标, 主要表现为其中的各元素在内存中的位置是散列的，如果使用不同的实现类来存储数据，最终在显示Set集合中的所有元素时，显示结果可能是无序的(HashSet)，或根据排序规则进行排列的(TreeSet)，或根据添加顺序进行排列的(LinkedHashSet)；另外，Set中的元素是不可重复的，即不可以向同一个Set集合中反复添加相同的数据，只能存在一个null值,关于“是否相同”，取决于equals()的对比结果与hashCode()值的对比，如果2个对象的equals()对比为true，并且hashCode()值相等，则视为“相同”！

map集合是双列集合

> 而Map集合是以**键值对**的方式存储元素，**所有Map集合的Key是无序不可重复的**，key和value都是引用数据类型，存的都是内存的地址。

#### 1、List的实现类 ####

*  List的常用实现类有ArrayList(线程不安全)、LinkedList(线程不安全)和Vector(线程安全)。
 *  ArrayList的底层是数组，LinkedList的底层是链表，前者查询快，后者增删快。`ArrayList`是使用数组结构来存储的，数组结构要求数据在内存中必须是连续的，存在查询效率高，(因为数组可以根据索引快速访问)但修改效率低的问题；而`LinkedList`是使用链表结构来存储的，链表添加或者删除不会造成数据的移动,所以存在查询效率低，但修改效率高的问题！
 *  Vector是线程安全的，Vector在一些必要的方法上都加了 synchronized关键字。

####    3、Set的实现类 ####

*  Set的常用实现类有HashSet、LinkedHashSet和TreeSet(三个实现类都是线程非安全的)。
 *  HashSet的底层是哈希表，是数组和链表的结合，其数据是完全散列的, 根据元素的hashCode值来决定元素的存储位置，比较两个HashSet是否相同，要equals和hashcode都相同，重写hashcode方法可以去除HashSet里面的重复元素。
 *  LinkedHashSet底层维护了一个数组+双向链表,LinkedHashSet 加入顺序和取出元素/数据的顺序一致,但同样不允许重复
 *  TreeSet的内部实现是红黑树，可以确保元素在排序状态，TreeSet 还实现了 SortedSet 接口，可以通过实现Comparator接口重写compare方法来定制排序。

#### 4. Map集合常用实现类 ####

① HashMap  
HashMap底层采用哈希表（数组+单向链表+红黑树）)的数据结构, 非线程安全的, 是无序的, 所以，当我们**需要存储的元素有序拿出**，那就使用LinkedHashMap。

② HashTable  
HashTable底层采用哈希表的数据结构，线程安全的，效率太低，使用较少，现在控制线程安全有其他的方式。

③ Properties  
Properties是HashTable下的一个实现类，由于继承了HashTable，所以Properties也是线程安全的，Properties的key和value只支持String数据类型。

④ TreeMap  
TreeMap是SortedMap的实现类，底层采用二叉树的数据结构，无序不可重复，但存入key的元素会按照大小排列。

#### 5、list遍历方式 ####

//方法一 普通for循环遍历
        System.out.println("普通for循环遍历");
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
    
        //方法二 增强for (也称for each循环)是JDK1.5以后出来的一个高级for循环，专门用来遍历数组和集合的。
        //内部原理其实是个Iterator迭代器，所以在遍历的过程中，不能对集合中的元素进行增删操作。
        System.out.println("增强for");
        for (int i : list) {
            System.out.println(i);
        }
      //方法三 迭代器遍历
        System.out.println("迭代器遍历");
        Iterator<Integer> it = list.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }
    
        //方法四 List集合自带迭代器
        System.out.println("List集合自带迭代器");
        ListIterator<Integer> listIterator = list.listIterator();
        while(listIterator.hasNext()){
            System.out.println(listIterator.next())
     //方法五Lambda
        System.out.println("Lambda");
        list.forEach(e -> {
            System.out.println(e);
        });
    
        list.stream().forEach(e -> {
            System.out.println(e);
        });

#### 6、Set遍历方式 ####

因为Set集合没有索引方法,所以不能用普通的for循环去遍历,也不能通过索引去获取、删除Set集合里面的元素，就需要通过[迭代器][Link 1]去遍历获取。所有的集合都可以用迭代器去遍历。下面是用三种方法去遍历Set集合：

// 迭代器
            Iterator<String> iterator = set.iterator();
            while (iterator.hasNext()){
                System.out.println(iterator.next());
            }
            System.out.println("---------------------");
            //增强for
            for (String s : set) {
                System.out.println(s);
            }
            System.out.println("---------------------");
            //forEach
            set.forEach((String s)->{
                System.out.println(s);
            });
             //lambda表达式
             //第一种
             list.forEach(n->System.out.println(n));
      
             //第二种
             list.forEach(System.out::println);
        }

#### 7.Map遍历方式 ####

import java.util.*;
     
    public class Test{
         public static void main(String[] args) {
          Map<String, String> map = new HashMap<String, String>();
          map.put("1", "value1");
          map.put("2", "value2");
          map.put("3", "value3");
          
          //第一种：普遍使用，二次取值
          System.out.println("通过Map.keySet遍历key和value：");
          for (String key : map.keySet()) {
           System.out.println("key= "+ key + " and value= " + map.get(key));
          }
          
          //第二种
          System.out.println("通过Map.entrySet使用iterator遍历key和value：");
          Iterator<Map.Entry<String, String>> it = map.entrySet().iterator();
          while (it.hasNext()) {
           Map.Entry<String, String> entry = it.next();
           System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
          }
          
          //第三种：推荐，尤其是容量大时
          System.out.println("通过Map.entrySet遍历key和value");
          for (Map.Entry<String, String> entry : map.entrySet()) {
           System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
          }
        
          //第四种
          System.out.println("通过Map.values()遍历所有的value，但不能遍历key");
          for (String v : map.values()) {
           System.out.println("value= " + v);
          }
    
          //第五种使用Map的forEach方法加上Java8的lambda表达式(用起来简直不要太爽):
          map.forEach( (k,v)->{System.out.println(k+" "+v);} );
      }
    }

####  ####

#### 8、List集合扩容机制 ####

jdk1.7时初始容量为10,jdk1.8时若未指定容量则初始容量为0,第一次添加元素时容量扩容为10,当元素大于其容量进行扩容时,扩容为原来的1.5倍 ,指定容量则为指定大小.

ensureCapacityInternal（）确定添加元素后，总元素量要大于Capacity,如果总元素量大于容量，就要执行扩容grow()，不需要扩容直接返回,添加第一个元素默认容量为10，此后每次扩容，需要执行size + size >> 1 ，即为原来的1.5倍,扩容的时候需要使用arr = Array.CopyOf(arr, minCapacity) , 创建一个新的数组，并且拷贝原来数组的元素到新的数组中，然后返回新的数组，将add新元素添加到数组后面

#### 9. Set集合扩容机制 ####

初始容量定义：默认为1 << 4（16）。最大容量为1<< 30(2的30次方) , 扩容加载因子为(0.75)，第一个临界点在当HashMap中元素的数量大于table数组长度\*加载因子（16\*0.75=12），  
则按oldThr << 1（原长度\*2）扩容。数组进行扩容的阀值 ，数组的容量达到整个数组的0.75就会进行数组的扩容的操作 :每次扩容 扩大2倍 :16\*0.75=12,加载因子作用是标志一个阈值，该值为自身容量\*加载因子，若达到阈值则扩容。

#### 10.Map的扩容机制 ####

HashMap的底层有数组 + 链表(红黑树)组成，数组的大小可以在构造方法时设置，默认大小为16，数组中每一个元素就是一个链表，jdk7之前链表中的元素采用头插法插入元素，jdk8之后采用尾插法插入元素，由于插入的元素越来越多，查找效率就变低了，所以满足某种条件时，链表会转换成红黑树。随着元素的增加，HashMap的数组会频繁扩容，如果构造时不赋予加载因子默认值，那么负载因子默认值为0.75,数组扩容的情况如下:

1:当添加某个元素后，数组的总的添加元素数大于了 数组长度 \* 0.75(默认,也可自己设定),数组长度扩容为两倍。(如开始创建HashMap集合后，数组长度为16，临界值为16 \* 0.75 = 12，当加入元素后元素个数超过12，数组长度扩容为32，临界值变为24)

2：在没有红黑树的条件下，添加元素后数组中某个链表的长度超过了8，数组会扩容为两倍.(如开始创建HashMAp集合后，假设添加的元素都在一个链表中，当链表中元素为8时，再在链表中添加一个元素，此时若数组中不存在红黑树，则数组会扩容为两倍变成32，假设此时链表元素排列不变，再在该链表中添加一个元素，数组长度再扩容两倍，变为64，假设此时链表元素排列还是不变，则此时链表中存在10个元素，这是HashMap链表元素数存在的最大值，此时，再加入元素，满足了链表树化的两个条件(1:数组长度达到64, 2:该链表长度达到了8)，该链表会转换为红黑树

[Link 1]: https://so.csdn.net/so/search?q=%E8%BF%AD%E4%BB%A3%E5%99%A8&spm=1001.2101.3001.7020