JavaSE之集合篇

---

前言

由于在刷题过程中，经常遇到map的使用，顺便一起回忆一波

---

一、集合概述

数组其实就是一个集合，
集合不能直接存储基本数据类型，另外集合也不能直接存储Java对象，集合中存储的都是Java对象的内存地址。（或者说集合中存储的是引用）

在Java中每一个不同的集合，底层会对应不同的数据结构。往不同的集合中存储数据元素，等于将数据放到了不同的数据结构当中。

集合在Java JDK中哪个包下？
java.util.* 所有的集合类和集合接口都在java.util包下

集合继承结构图

在Java中集合分为两大类：

• 一类是单个方式存储元素：这一类集合中超级父接口 java.util.Collection
  

Collection下有主要的两大类：List和Set【常用的】
list集合的特点：有序可重复，存储的元素有下标【有序实际上是说存进去是这个顺序，取出来还是这个顺序，不是按照大小顺序排序】，有序是因为list集合都有下标，下标从0开始 以1递增

ArrayList、LinkedList、Vector【常用的】
ArrayList底层采用了数组这种数据结构【非线程安全的】
LinkedList底层采用了双向链表数据结构
Vector底层采用了数组这种数据结构【线程安全的，所有的方法都有synchronized关键词修饰，但是效率较低。现在保证线程安全有别的方案，因此使用较少】

Set集合存储元素的特点：无序，表示存进去是这个顺序，取出来就不一定是这个顺序了，不可重复，没有下标。

HashSet：实际上HashSet在new的时候底层实际创建了一个HashMap集合。向HashSet集合中存储元素实际上是存储到HashMap集合中了。HashMap集合是一个哈希表数据结构
TreeSet的父接口：SortedSet 【SortedSet的父接口Set】，TreeSet集合底层实际上是TreeMap，new TreeSet集合实际上是new了一个TreeMap集合，TreeMap底层采用了二叉树的数据结构

• 一类是以键值对的方式存储元素：java.util.Map

1、Map集合和Collection没有关系
2、Map集合以key和value的方式存储
3、key和value豆豆hi存储Java对象的内存地址
4、所有map集合的key都是无序不可重复的
map集合的key和set集合存储元素特点相同【给set集合添加元素实际上是加到了map集合的key部分】

HashMap:【非线程安全的】底层是哈希表数据结构，无序不可重复
HashTable:【线程安全的】底层是哈希表数据结构，效率较低，现在使用较少
Properties【属性类】继承了HashTable，线程安全的
SortedMap【接口】无需不可重复，另外放在SortedMap key部分的元素会自动按照大小排序，称为可排序的集合---->TreeMap是它的实现类，TreeMap集合底层的数据结构是一个二叉树

总结（所有的实现类）：
ArrayList：底层是数组
LinkedList：底层是双向链表
Vector：底层是数组，线程安全的，效率较低，使用较少。
HashSet：底层是HashMap，放到HashSet集合中的元素等同于放到HashMap集合key部分了
TreeSet：底层是TreeMap，放到TreeSet集合中的元素等同于放到TreeMap集合key部分了
HashMap：底层是哈希表
Hashtable：底层是哈希表，线程安全的，效率较低，使用较少
Properties：线程安全的，key和value只能存储字符串
TreeMap：底层是二叉树，TreeMap集合的key可以自动按照大小排序

List集合存储元素的特点：有序（有下标）可重复（存进去的元素和取出的元素顺序相同）
Set（Map）集合存储元素的特点：无序不可重复
SortedSet（SortedMap）集合存储元素的特点：无序不可重复，但是SortedSet集合中的元素的可排序（可以按照大小顺序排列）的。

二、Collection接口中常用方法

2.1Collection中存放什么元素？

没有使用“泛型”之前，Collection中可以存放Object的所有子类型
使用泛型之后，Collection中只能存储某个具体类型

2.2常用方法

创建一个集合对象：
【多态，父类型引用指向子类型对象】

Collection<> c = new ArrayList<>();

向集合中添加元素：

c.add(1200)//自动装箱 实际上是放进去了一个对象的内存地址。
c.add(3.14)
c.add("hello")
c.add(new Object());
c.add(true)

获取集合中的元素个数：

c.size();//5

清空集合：

c.clear();

判断集中中是否包含某个元素o

注意：在没有重写equals之前 会比较内存地址 结果是false

底层调用的是 equals() 方法【比较的是内容不是内存地址】

存放在集合中的类型，一定要重写equals方法

c.contains("hello")

public static void main(){Collection c = new ArrayList();User u1 = new User("jack");c.add(u1);User u2 = new USer("jack");//注意：在没有重写equals之前 会比较内存地址 结果是falsec.contains(u2);
}Class User{private String name;public User(){};public User(String name){this.name = name;}
}

删除集合中某个元素
remove底层也调用了equals方法

c.remove()
String s1 = "hello";
Strign s2 = "hello";
c.add(s1);
c.add(s2);
c.remove(s2);//会不会把s1也删除掉？ --->会

判断集合是否为空

c.isEmpty();

把集合转化为数组

c.toArray();

2.3迭代器

迭代器是所有Collection通用的一种方式，在Map集合中不能用，在所有的Collection以及子类中使用

一定要注意：集合结构只要发生改变【添加一个元素或者删除元素】迭代器都必须重新获取，如果没有重新获取迭代器就会出现异常，根本原因在于：集合中元素删除了，但是没有更新迭代器
迭代器去删除时，会自动更新迭代器，并且更新集合 【删除集合中元素】

	Collection c = new ArrayList();c.add("hello");c.add("bwy");c.add(100);c.add(new Object());Iterator it = c.iterator();while(it.hasNext()){Object o = it.next();}

三、List接口中常用的方法

list：有序可重复

1、创建list类型的集合

List list = new ArrayList();

2、添加元素

默认都是向集合末尾添加元素

list.add("A"); //默认都是向集合末尾添加元素
list.add(1,"bwy") //在指定位置插入指定元素 使用不多，效率比较低

3、根据下标获取元素
因为有下标，因此list集合有自己比较特殊的遍历方式

Object 0 = list.get(0);
//遍历方式
for(int i=0;i<list.size();i++){Object o = list.get(i); 
}

4、获取指定对象第一次以及最后一次出现处的索引

int index1 = list.indexOf("A");
int index2 = list.lastIndexOf("A");

5、根据下标删除元素

list.remove(0);

6、修改指定位置元素

list.set(2,"soft");

四、ArrayList初始化容量及扩容

ArrayList初始化容量是10；
list.size()是10还是0呢？----->0 集合中的size()方法是获取当前集合中元素的个数
容量和size两回事
ArrayList集合底层是一个Object[]数组

五、Vector

底层是一个数组，初始容量10
将不安全的ArrayList变为线程安全的：

List list = new ArrayList();
Collections.synchronizedList(list);

六、Map接口常用方法

1、map和Collection没有继承关系
2、Map集合以key和value的方式存储数据
key和value都是引用数据类型
key和value都是存储对象的内存地址

void clear();清空Map集合
boolean containsKey(Object key); 判断Map中是否包含某个key
boolean containsValue(Object value);判断Map中是否包含某个value
V get(Object key); 通过key获取value
boolean isEmpty(); 判断Map集合中元素个数是否为0
V put(K key,V value); 向Map集合总添加键值对
V remove(Object key) 通过key删除键值对
int size(); 获取Map集合中键值对的个数
Collection< V> values()； 获取Map集合中所有的value，返回一个Collection
Set<Map.Entry<K,V>> entrySet()；将Map集合转换为set集合

Map集合的遍历【重要】

• 方式一：获取所有的key，通过遍历key，来获取所有的value

Map<Integer,String> map = new HashMap<>();map.put(1,"abc");map.put(2,"bwy");map.put(3,"ccc");//遍历map集合//获取所有的key 所有的key是一个set集合Set<Integer> set = map.keySet();//遍历key//方法1：迭代器Iterator it = set.iterator();while(it.hasNext()){Integer k = (Integer) it.next();String value = map.get(k);System.out.println(k+"="+value);}//方法2：foreachfor(Integer key:set){String value = map.get(key);System.out.println(key+"="+value);}

• 方式二：Set<Map.Entry<K,V>> entrySet()；【将map集合全部转换为set集合】
  

 Map<Integer,String> map = new HashMap<>();map.put(1,"abc");map.put(2,"bwy");map.put(3,"abc");//遍历map集合//Set<Map.Entry<Integer, String>> set = map.entrySet();Set<Map.Entry<Integer, String>> set = map.entrySet();//foreach遍历for(Map.Entry<Integer,String> m : set){int k = m.getKey();String value = m.getValue();System.out.println("foreach遍历"+k+"="+value);}//迭代器遍历Iterator<Map.Entry<Integer, String>> it = set.iterator();while(it.hasNext()){Map.Entry<Integer, String> next = it.next();int k = next.getKey();String value = next.getValue();System.out.println("迭代器遍历"+k+"="+value);}

map.put(k,v)实现原理：
第一步：先将k，v封装到Node对象当中
第二部：底层会调用hashCode()方法得出hash值，然后通过哈希函数，将哈希值转换为数组的下标，下标位置上如果没有任何元素，就把Node添加到这个位置上了，如果下标对应的位置上有链表，此时会拿着k和链表上每一个结点中的k进行equals，如果所有的equals方法都是返回false，那么这个新节点将会被添加到链表的末尾，如果有其中一个返回true，那么这个节点的value将会被覆盖

v = map.get(k)实现原理：
先调用k的hashCode()方法得出的哈希值，通过哈希算法转换成数组下标，通过数组下标快速定位到某个位置上，如果这个位置上什么也没有，返回null，如果这个节点上有单向链表，那么会拿着参数k和单向链表上每个结点的k进行equals，如果所有的equals方法都返回false，那么get方法返回null，只要其中一个结点的k和参数k equals的时候返回true，那么此时这个结点value就是我们要找的value，get方法最终返回这个value

为什么哈希表的随机增删，以及查询效率都很高？
1、增删是在链表上完成的
2、查询不需要都扫描，只需要部分扫描

重点：
HashMap集合的key会先后调用两个方法，一个方法是hashCode()，一个方法是equals()，那么这两个方法都需要重写。

在JDK8之后，如果哈希表单向链表中元素超过8个，单向链表这种数据结构就会变成红黑树数据结构，当红黑树上的节点小于6会重新变成单向链表

HashMap和Hashtable的区别：
HashMap集合key部分允许为空，且只允许有一个。putVal()中有对null的处理

Hasttable集合key部分不允许为空，value也不允许为空。【空指针异常】

七、Properties

创建一个Properties对象

Properties pro = new Properties()

存：

pro.setProperty("username","root");
pro.setProperty("password","123456");

取：

pro.getPropertry(username);//root
pro.getPropertry(password);//123456

---