概念

集合：对象容器，实现对对象常用的操作

和数组区别

1. 数组长度固定，集合长度不固定
2. 数组可以存储基本类型和引用类型，集合只能存储引用类型

Collection体系

• Collection：代表一组任意类型的对象

• List：有序、有下标、元素可重复

• ArrayList 【重点】

• 数组结构实现，必须要连续空间，查询快、增删慢
• jdk1.2版本，运行效率块、线程不安全

• Vector

• 数组结构实现，查询快、增删慢
• jdk1.0版本，运行

• LinkedList

• 双向链表结构实现，无需连续空间，增删快，查询慢

• Set

Collection父接口

特点：代表一组任意类型的对象

删除时只能靠元素，不能靠下标

常用方法

/**

* @author 伍六七

* @date 2022/8/12 19:37

*/

public class collection_demo {

   public static void main(String[] args) {

       //0创建集合

       Collection collection = new ArrayList();

       System.out.println(collection);//[]

       

       

       //1添加元素

       collection.add("1");

       collection.add("1");

       collection.add("2");

       System.out.println(collection);//[1, 1, 2]

       

       

       //2删除元素

       collection.remove("1");

       System.out.println(collection);//[1, 2]

       collection.clear();//[]

       System.out.println(collection);

       

       

       //3遍历

       //增强遍历

       for(Object o : collection){

           System.out.println(o);

       }

       

       //迭代器

       Iterator iterator = collection.iterator();

       while (iterator.hasNext()){

           String o = (String) iterator.next();

           System.out.println(o);

       }

       

       //4判断

       System.out.println(collection.contains("1"));//true

       System.out.println(collection.isEmpty());//false

   }

}

List子接口

特点：有序、有下标、元素可重复

删除时区别下标(int)与元素(String)

常用方法

/**

* @author 伍六七

* @date 2022/8/12 20:26

*/

public class list_demo {

   public static void main(String[] args) {

       //0新建[]

       ArrayList list = new ArrayList();

       //1添加[4, 3, 2, 1, s, s]

       list.add("4");

       list.add("3");

       list.add("2");

       list.add(1);

       list.add("s");

       list.add("s");

       //2删除按照下标(int)按照参数(String)

       list.remove(1);//[4, 2, 1, s, s]

       list.remove("s");//[4, 2, 1, s]

       //3遍历

       //3.1for遍历

       for (int i = 0; i < list.size(); i++) {

           System.out.print(list.get(i)+" ");//4 2 1 s

       }

       //3.2增强for

       for (Object l:list) {

           System.out.print(l+" ");//4 2 1 s

       }

       //3.3迭代器

       Iterator it = list.iterator();

       while (it.hasNext()){

           Object o =  it.next();

           System.out.print(o+" ");//4 2 1 s

           //可以使用it.remove(); 进行移除元素

           //不能使用collection其他方法 会报并发修改异常

           //it.remove();

       }

       //3.4列表迭代器

       ListIterator li = list.listIterator();

       while (li.hasNext()){

           System.out.printf(li.nextIndex()+":"+li.next()+" ");//0:4 1:2 2:1 3:s

       }

       while (li.hasPrevious()){

           System.out.printf(li.previousIndex()+":"+li.previous()+" ");//3:s 2:1 1:2 0:4

       }

       //4获取对应下标

       int i = list.indexOf(1);

       System.out.println(i);//2

       //5返回子集合(左闭右开)

       List list1 = list.subList(1, 3);

       System.out.println(list1);//[2, 1]

   }

}

List实现类

ArrayList

删除与List子接口方法一致

常用方法

/**

* @author 伍六七

* @date 2022/8/12 21:03

*/

public class arraylist_demo {

   public static void main(String[] args) {

       //0新建[]

       ArrayList arrayList  = new ArrayList<>();

       System.out.println(arrayList);//[]

       //1添加

       arrayList.add(1);

       arrayList.add("1");//会自动转化为int

       arrayList.add("s");

       arrayList.add("s");

       arrayList.add("l");

       System.out.println(arrayList);//[1, 1, s, s, l]

       //2删除按照下标(int)按照参数(String)

       arrayList.remove(1);

       System.out.println(arrayList);//[1, s, s, l]

       //3遍历

       //3.1迭代器

       Iterator it = arrayList.iterator();

       while(it.hasNext()){

           Object o = it.next();

           System.out.print(o+" ");//1 s s l

       }

       //3.1列表迭代器

       ListIterator li = arrayList.listIterator();

       //正序

       while(li.hasNext()){

           Object o = li.next();

           System.out.print(o+" ");//1 s s l

       }

       //倒序

       while(li.hasPrevious()){

           Object o = li.previous();

           System.out.printf(o+" ");//l s s 1

       }

       //4判断

       System.out.println(arrayList.contains(1));//true

       System.out.println(arrayList.isEmpty());//false

       //5获得下标

       System.out.println(arrayList.indexOf(1));//0

       System.out.println(arrayList.indexOf("s"));//1

   }

}

源码分析

DEFAULT_CAPACITY = 10; //默认容量

//注意：如果没有向集合中添加任何元素时，容量0，添加一个后，容量为10

//每次扩容是原来的1.5倍

elementData//存放元素的数组

size //实际元素个数

LinkedList

创建链表集合

LinkedList li = new LinkedList<>();

常用方法与List一致

vector

常用方法

增加、删除、判断同上

/**

* @author 伍六七

* @date 2022/8/12 21:31

*/

public class vector_demo {

   public static void main(String[] args) {

       //创建集合

       Vector vector = new Vector<>();

       //增加、删除、判断同上

       vector.add(1);

       vector.add(1);

       vector.add(2);

       vector.add("s");

       vector.add("l");//[1, 1, 2, s, l]

       vector.remove(4);//[1, 1, 2, s]

       vector.contains("s");//true

       vector.isEmpty();//false

       vector.indexOf("s");//3

       //遍历中枚举器遍历

       Enumeration en = vector.elements();

       while (en.hasMoreElements()){

           Object o = en.nextElement();

           System.out.printf(o+" ");//1 1 2 s

       }

   }

}

Set接口

特点：无序、无下标、元素不可重复

方法：全部继承自Collection中的方法

增、删、遍历、判断与collection一致

HashSet

特点

存储结构：哈希表（数组+链表+红黑树）

存储过程（重复依据）

1. 根据hashCode计算保存的位置，如果位置为空，直接保存，若不为空，进行第二步
2. 再执行equals方法，如果equals为true，则认为是重复，否则形成链表

不理解

• 基于HashCode计算元素存放位置

• 利用31这个质数，减少散列冲突

• 31提高执行效率31 * i = (i << 5) - i 转为移位操作

• 当存入元素的哈希码相同时，会调用equals进行确认，如果结果为true，则拒绝后者存入

/**

* @author 伍六七

* @date 2022/8/12 21:49

*/

public class hashset_demo {

   public static void main(String[] args) {

       //新建集合

       HashSet<String> hashSet = new HashSet<String>();

       //添加元素

       hashSet.add("1");

       hashSet.add("1");

       hashSet.add("1");

       hashSet.add("2");

       hashSet.add("3");

       System.out.println(hashSet);//[1, 2, 3]

       //删除元素

       hashSet.remove("1");

       System.out.println(hashSet);//[2, 3]

       //遍历操作

       //1. 增强for

       for(String set:hashSet){

           System.out.print(set);//23

       }

       //2. 迭代器

       Iterator<String> it = hashSet.iterator();

       while(it.hasNext()){

           String s = it.next();

           System.out.printf(s+" ");//2 3

       }

       //判断

       System.out.println(hashSet.contains("2"));//true

       System.out.println(hashSet.isEmpty());//false

   }

}

SortedSet接口

TreeSet

特点

• 基于排列顺序实现元素不重复
• 实现SortedSet接口(如果实现该接口需要重写方法)，对集合元素自动排序
• 元素对象的类型必须实现Comparable接口，指定排序规则，默认升序
• 通过CompareTo方法确定是否为重复元素

存储结构：红黑树

常用方法

还是set方法

//创建集合

TreeSet<String> treeSet = new TreeSet<>();

//添加元素

treeSet.add();

//删除元素

treeSet.remove();

//遍历 1. 增强for 2. 迭代器

//判断

treeSet.contains();

补充：TreeSet集合的使用

Comparator 实现定制比较（比较器）

Comparable 可比较的

// 重写compare，算法也用到，也可以用Lambda表达式

@override

public int compare(Person o1, Person o2){

 int n1 = o1.getAge()-o2.getAge();

 int n2 = o1.getName().comareTo(o2.getName());

 return n1 == 0 ? n2 : n1;

}

Map接口

https://www.cnblogs.com/coderzjz/p/13587167.html

特点

张三是人，李四也是人。

1. 用于存储任意键值对（key - value）
2. 键：无序、无下标、不允许重复（唯一）
3. 值：无序、无下标、允许重复

常用方法

map.put()增加（如果之前有对应的健，则直接覆盖）

map.get()获取

map.remove()删除

map.keySet()返回所有健

map.values()返回包含所有值的Collection集合

map.entrySet()键值匹配的Set集合

/**

* @author 伍六七

* @date 2022/8/13 14:50

* map接口特点

* 1. 用于存储任意键值对（key - value）

* 2. 键：无序、无下标、不允许重复（唯一）

* 3. 值：无序、无下标、允许重复

* 4.键值对这里可以理解为张三是人，李四也是人，前键后值

*/

public class map_demo {

   public static void main(String[] args) {

       //创建Map集合

       Map<String, String> map = new HashMap<>();

       // 1. 添加元素

       map.put("cike","wuliuqi");

       map.put("lifashi","wuliuqi");

       map.put("cike","wuliuqi1hao");//会替换前面的值

       map.put("lvshi","luoxiang");//{lvshi=luoxiang, cike=wuliuqi1hao, lifashi=wuliuqi}

       System.out.println(map);

       // 2. 删除

       map.remove("cike");

       System.out.println(map);//{lvshi=luoxiang, lifashi=wuliuqi}

       // 3.根据健返回值

       map.get("lifashi");//wuliuqi

       // 4. 遍历

       // 4.1 使用KeySet()所有Key的set集合

       Set<String> keyset = map.keySet(); // [lvshi, lifashi]

       // 4.2获取值的集合

       Collection<String> values = map.values();//[luoxiang, wuliuqi]

       // 4.3 使用entrySet()

       Set<Map.Entry<String, String>> entries = map.entrySet();//[lvshi=luoxiang, lifashi=wuliuqi]

   }

}

删除必须有健

HashMap【重点】

常用方法与map一致

基于哈希表对Map接口的实现，允许空值传入，但是遍历顺序不确定

线程不安全，多个线程同时写入HashMap，可能导致数据的不一致

存储结构：

• 1.7 数组 + 链表----链表就是解决 hash 值冲突的，使用的是头插法。
• 1.8 数组 + （链表 | 红黑树）--hashmap 的初始容量是 16，加载因子是 0.75,就是 16x0.75=12,超过就需要扩容为原来的两倍，当数组扩容大于 等于64,且链表长度大于阈值 8，链表就会转成红黑树，查询较快，在链表小于阈值 8 时，使用的是尾插法

基本属性

元素结构--Node

HashMap类中的元素是Node类，翻译过来就是节点，是定义在HashMap中的一个内部类

• hash：key的哈希值
• key：节点的key，类型和定义HashMap时的key相同
• value：节点的value，类型和定义HashMap时的value相同
• next：该节点的下一节点

HashMap 的索引--Node的存储位置

对16取余

扩容介绍

• 1.7 数组 + 链表----链表就是解决 hash 值冲突的，使用的是头插法。
• 1.8 数组 + （链表 | 红黑树）--hashmap 的初始容量是 16，加载因子是 0.75,就是 16x0.75=12,超过就需要扩容为原来的两倍，当数组扩容大于 等于64,且链表长度大于阈值 8，链表就会转成红黑树，查询较快，在链表小于阈值 8 时，使用的是尾插法

树化----链表与红黑树的转换

链表--->红黑树是链表长度达到阈值是8，红黑树--->链表阈值为6。

链表长度设置为8和6的原因

基于泊松分布，因为经过计算，在hash函数设计合理的情况下，发生hash碰撞8次的几率为百万分之6，用概率证明。因为8够用了，至于为什么转回来是6，因为如果hash碰撞次数在8附近徘徊，会一直发生链表和红黑树的互相转化，为了预防这种情况的发生，设置为6

扩容结构--

• size------------------HashMap中实际存在的键值对数量
• modCount----------记录HashMap内部结构发生变化的次数
• threshold-----------阈值，表示能容纳的键值对的临界值，等于数组长度*负载因子
• loadFactor----------负载因子，默认0.75
• HashMap默认容量--16

/**

* 默认初始化容量16

    */

   static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

   /**

    *  最大容量，如果其中一个带参数的构造函数隐式指定更高的值，则使用该最大容量。

    *  必须是2的幂次方

    */

   static final int MAXIMUM_CAPACITY = 1 << 30;

   /**

    * 默认负载因子，负责管理HashMap在何时开始扩容

    */

   static final float DEFAULT_LOAD_FACTOR = 0.75f;

   /**

    * 转为树的阈值

    */

   static final int TREEIFY_THRESHOLD = 8;

   /**

    * 取消树的值

    */

   static final int UNTREEIFY_THRESHOLD = 6;

   /**

    * 冲突严重时转为红黑树之前的最小阈值

    */

   static final int MIN_TREEIFY_CAPACITY = 64;

   

   

   /**

   *  存储数据的Node数组

   */

   transient Node<K,V>[] table;

   /**

    * Holds cached entrySet(). Note that AbstractMap fields are used

    * for keySet() and values().

    */

   transient Set<Map.Entry<K,V>> entrySet;

  /**

   *  大小

     */

   transient int size;

   /**

    * fail-fast.  (See ConcurrentModificationException).

    */

   transient int modCount;

   /**

    * 下一次应该扩容的大小 (capacity * load factor).

    * 如果尚未扩容，则该字段保存初始entry数组的容量，或用零表示

    */

   int threshold;

   /**

    * 负载因子

    */

   final float loadFactor;

注意！！长度扩大以后，Hash的规则也随之改变。

treeifyBin方法--扩容判断

final void treeifyBin(Node<K,V>[] tab, int hash) {

//n数组长度，index 当前下标，e当前节点

       int n, index; Node<K,V> e;

//判断数组是否为null,判断数组长度是否小于64，如果小于走扩容，不小于走链表转红黑树

       if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)

           resize(); //扩容

//数组长度减1和hash做与运算的当前下标index，取下标内元素，如果为null结束，不为null赋值给e

       else if ((e = tab[index = (n - 1) & hash]) != null) {

  //hd头节点 tl尾节点

           TreeNode<K,V> hd = null, tl = null;

           do {

  //replacementTreeNode 添加接点e 进TreeNode

               TreeNode<K,V> p = replacementTreeNode(e, null);

  //判断尾节点 为null 说明没有根节点

               if (tl == null)

    //首节点（根节点） 指向当前节点

                   hd = p;

               else {

    //当前树节点的 前一个节点指向 尾节点

                   p.prev = tl;

    //尾节点的 后一个节点指向 当前节点

                   tl.next = p;

               }

  //把当前节点设置为尾节点

               tl = p;

           } while ((e = e.next) != null); //判断当前节点的下 当前节点的下一个节点是否为null 不为null 遍历

  //目前为止 也只是把Node改为TreeNode 也就是单向链表改为双向链表

  //根节点判断是否为 null

           if ((tab[index] = hd) != null)

               hd.treeify(tab); //转红黑树

       }

   }

为什么不一开始就使用红黑树，还要有一个转换的过程

单个 TreeNode 需要占用的空间大约是普通 Node 的两倍，所以只有当包含足够多的 Nodes 时才会转成 TreeNodes，而是否足够多就是由 TREEIFY_THRESHOLD 的值决定的。而当桶中节点数由于移除或者 resize 变少后，又会变回普通的链表的形式，以便节省空间。

重新实现hash方法-----为什么HashMap重新实现hash方法，直接用hashcode不行么？

减少碰撞

当向 HashMap 中添加一个元素的时候，需要根据 key 的 hash 值，去确定其在数组中的具体位置。HashMap 为了存取高效，减少碰撞，就是要尽量把数据分配均匀，每个链表长度大致相同，这个实现的关键就在把数据存到哪个链表中的算法。我们知道Object的hashcode有32位，而HashMap扩容之前的数组初始大小才16。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算，得到的余数才能用来访问数组下标。hash % length实际就是取模，计算机中直接求余效率不如位移运算。所以源码中做了优化，使用 hash & (length - 1)，而实际上 hash % length 等于 hash & ( length - 1) 的前提是 length 是 2 的 n 次幂。这也是数组容量为何是 2 的 n 次幂。

小知识：

hash % length 等于 hash & ( length - 1)

hash % length

a=10,b=8,a%8=2

   

hash & ( length - 1)

（前提b为2的整数次幂）

a=1010,b=1000

b-1=0111（任何数&(b-1)得到的数不会大于b，也就相当于对b取余）

     a  1010 10

   b-1  0111  8

a&(b-1)  0010  2

tab[i = (n - 1) & hash])

为什么要进行二次 hash？

HashMap 的 put 流程

网上借来的图

TreeMap

• TreeMap存储 Key-Value 对时，需要根据 key-value 对进行排序。TreeMap 可以保证所有的 Key-Value 对处于有序状态。
• TreeSet底层使用红黑树结构存储数据
• TreeMap 的 Key 的排序：
• 自然排序：TreeMap 的所有的 Key 必须实现 Comparable 接口，而且所有的 Key 应该是同一个类的对象，否则将会抛出 ClasssCastException
• 定制排序：创建 TreeMap 时，传入一个 Comparator 对象，该对象负责对TreeMap 中的所有 key 进行排序。此时不需要 Map 的 Key 实现Comparable 接口
• TreeMap判断两个key相等的标准：两个key通过compareTo()方法或者compare()方法返回0。

线程安全，运行效率慢；不允许null作为key或是value

Hashtable

线程安全，运行效率慢；不允许null作为key或是value

Properties

hashtable的子类，要求key和value都是string，通常用于配置文件的读取