List接口和常用方法

区别于collection方法，list接口方法只能list及其子接口能调用，collection、set等无法调用

List接口是Collection接口的子接口

1. List集合类中元素有序且可重复（即添加顺序和取出顺序一致）；

2. List集合中的每个元素都有对应的顺序索引，即支持索引；get(i)；

3. JDK API中List接口的实现类很多，ArrayList、LinkedList和Vector只是常用实现类；

• void add(int index , Object ele)：在index位置插入elel元素；后续元素整体后移

• boolean addAll(int index , Collection eles)：在list集合的index位置开始将eles中的所有元素添加进来

• Object get(int intdex)：获取指定index位置的元素

• int indexOf(Object obj)：获取obj在集合中首次出现的位置；不包含返回-1

• int lastIndexOf(Object obj)：返回obj在集合中末次出现的位置；不包含返回-1

• Object remove(int index)：移除指定index位置的元素，并返回此元素；

• Object set(int index , Object ele)：设置指定index位置的元素为ele，等同替换；

• List subList(int fromIndex , int toIndex)：返回从fromIndex到toIndex位置的子集合；不包括toIndex

• ListIterator<E> listIterator(int index)：从列表中的index位置开始，返回列表中的元素（按正确顺序）的列表迭代器。

• int sort(Comparator<? super E> c)：使用指定的c（匿名内部类）排序方式对集合元素进行排序。

• Comparator是一个接口，提供一个方法：int compare(Object o1 , Object o2)；
  • o1- o2，代表升序；o2- o1，代表降序；
  • 如果o1、o2是引用类型，则需要重写此方法

List接口遍历元素方式

• 方式一：使用iterator，同collection使用

• 方式二：增强for循环，同collection使用

• 方式三：普通for循环：长度为list.size()；输出list.get(i)；

  for (int i = 0; i < list.size(); i++) {
                  System.out.println(list.get(i));
              }

ArrayList底层结构和源码分析

ArrayList注意事项

1. 能容纳所有类型对象，包括null，并且可放多个

2. ArrayList是由数组来实现数据存储的；

3. ArrayList基本等同于Vector，除了ArrayList是线程不安全（执行效率高，在多线程情况下，不建议使用ArrayList）

ArrayList的底层操作机制源码分析

底层是数组，频繁进行添加、删除，不建议使用

1. ArrayList中维护了一个Object类型的数组elementData：transient Object[] elementData；transient表示瞬时、短暂的；表示该属性不会被序列化，不会存入硬盘；

2. 当创建ArrayList对象时，如果使用的是无参构造器，则初始elementData的容量为0，第一次添加，扩容为elementData为10，如需再次扩容，则扩容为原来的1.5倍；即15--->22--->33--->49

3. 如果使用的是指定大小的构造器，则初始elementData容量为指定大小，如需扩容，则直接扩容为原来的1.5倍；0510韩顺平Java_ArrayList底层源码1哔哩哔哩_bilibili

Vector底层结构和源码分析

1. vector类的定义说明：

   public class Vector<E>
   extends AbstractList<E>
   implements List<E>, RandomAccess, Cloneable, Serializable

2. Vector底层也是一个对象数组，protected Object[] elementData；

3. 创建对象：如果使用无参构造器，默认容量为10，添加时，扩容为原来的2倍；指定容器大小，添加时，扩容为原来的2倍；0513韩顺平Java_Vector源码解读哔哩哔哩_bilibili

4. Vector是线程同步的，即线程安全，Vector类的操作方法带有synchronized；

5. 在开发中，需要线程同步安全时，考虑使用Vetor；

LinkedList底层结构

LinkedList的全面说明：

1. LinkedList底层实现了双向链表和双端队列特点；

2. 不需要初始化容量

3. 可以添加任意元素（元素可以重复），包括null；

4. 有序，没有索引

5. 线程不安全，没有实现同步；

6. 封装了大量对于首、尾结点操作的API；

• 常用API：

  • void addFirst(E e)在该列表开头插入指定的元素；

  • void addLast(E e)在该列表结尾添加指定的元素；

  详见API

LinkedList的底层操作机制：

1. LinkedList底层维护了一个双向链表；

2. LinkedList中维护了两个属性first和last分别指向首节点和尾结点

3. 每个结点（Note对象），里面又维护了prev、next、item三个属性，其中通过prev指向前一个，通过next指向后一个结点。最终实现双向链表；

4. LinkedList元素的添加和删除依靠链表，不是通过数组完成的，相对来说效率较高；

0515韩顺平Java_LinkedList源码图解哔哩哔哩_bilibili

ArrayList和LinkedList比较

• 如何选择ArrayList和LinkedList：

  1. 改查的操作多，选择ArrayList

  2. 增删的操作多，选择LinkedList

  3. 一般来说，在程序中80%~90%都是查询，因此大部分选择ArrayList

  4. 在一个项目中，有可能一个模块使用的是ArrayList，另一个模块使用LinkedList；主要根据业务灵活选择

set接口和常用方法

set接口介绍

1. 无序(添加和取出的顺序不一致)，没有索引；但取出的顺序是固定的，不会改变

2. 不允许重复元素，所以最多包含一个null

3. JDK API中Set接口的实现类有：

set接口的常用方法

和List接口一样，Set接口也是Collection的子接口，因此常用方法和Collection接口一样；

• 将set集合中元素转换成指定类型的数组；

Set<Integer> set = map.keySet();
Integer[] toArray = set.toArray(new Integer[0]);

Set接口的遍历方式

• 同Collection的遍历方式一样，因为Set接口是Collection接口的子接口：

  1. 迭代器；

  2. 增强for；

  3. 不能使用索引的方式获取；

HashSet

HashSet的全面说明

1. HashSet实现了Set接口；

2. HashSet底层是哈希表结构，实际上是HashMap，(看源码)；

   public HashSet() {
       map = new HashMap<>();
       }

3. 不能有重复元素/对象；详见：HashSet01.java

4. 无索引

5. 可以存放null，但只能有一个；

6. HashSet元素无序，位置取决于hash后，再确定索引的结果（无序的）；

HashSet底层机制

添加元素，判断是否重复：详见HashSet_01

1. HashSet底层机制是HashMap，HashMap底层是（数组+单向链表+红黑树）；数组链表模拟见HashSetStructure.java；

2. 添加一个元素时，先得到hash值----转换成----->索引值，确定保存在哪个链表中；

3. 找到存储数据表table，看这个索引位置是否已存放元素；如果没有，直接加入

4. 如果有，调用equals比较此索引位置链表的每个元素，如果相同，就放弃添加；如果遍历链表没有相同的，则添加到链表的最后；

5. 在Java 8中，如果一个链表的元素个数到达 TREEIFY_THRESHOLD（默认是8），并且table的大小>=MIN_TREEIFY_CAPACITY（默认64），就会进行树化（红黑树）；

0521韩顺平Java_HashSet源码解读1哔哩哔哩_bilibili

不同的对象（即使是一样的两个对象）HashCode值一般不同，可以通过重写类的hashCode方法，实现两个一样的对象的HashCode值相同，重写equals方法，实现对象部分属性相同即相同，从而做到集合内自定义不重复

LinkedHashSet

• LinkedHashSet是HashSet的子类

• LinkedHashSet底层是一个LinkedHashMap，底层维护了一个数组+双向链表；

• LinkedHashSet根据元素的hashCode值来决定元素的存储位置，同时使用双向链表维护元素的次序，（有序）

• LinkedHashSet不允许重复；

LinkedHashSet底层机制

0528韩顺平Java_LHashSet源码解读哔哩哔哩_bilibili

数据结构

• 数据结构是程序中组织和存储数据的一种方式；数据结构和算法组成程序

• 常见的数据结构有8种：

  • 数组：有序的元素序列，一块连续的空间，查改快，增删满；

  • 链表：一系列结点Node，结点可以在程序的运行中动态生成；每个结点包含item、next、prev；链表结构不存在扩容机制

    常见：单向链表、双向链表、循环链表

  • 栈（堆栈）：一种受限的线性表结构，仅可从一端添加、取出元素；不需要初始化容量，不需要扩容

  • 堆

  • 树：一对多，以结点形式存储数据；

    1. 每个结点可以有0~n个子节点；

    2. 没有父节点的结点称为根节点；没有子节点的为叶子结点；

    3. 每个非根节点有且仅有一个父节点；

    4. 根节点除外，每个子节点可以分为多个互不交叉的子树；

  ---

  红黑树：一种特殊的二叉树，

  1. 每个结点标记为黑色或红色，

  2. 根节点、叶子结点为黑色，

  3. 红色结点的子节点必须为黑色，

  4. 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点，

  特点：搜索速度非常快

  ---

  • 图

  • 哈希表(hash Table)：数组+链表+红黑树结构；同时具有数组检索快、链表增删快的特性；底层存储机制详见HashMap部分；

  • 队列：先进先出；只能从入口位置添加元素，只能从出口位置删除、取出元素；取出、删除受限

• 链表与数组优缺点：

  1. 不需要初始化容器大小

  2. 可以添加任意元素

  3. 插入和删除只需更新prev和next引用即可

  缺：

  1. 占用内存空间较大，因为有大量引用

  2. 查找元素需要遍历整个链表，效率低