概念

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

和数组区别

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

Collection体系

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

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

ArrayList 【重点】

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

Vector

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

LinkedList

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

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("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");

//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("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(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

特点

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

存储过程（重复依据）

根据hashCode计算保存的位置，如果位置为空，直接保存，若不为空，进行第二步
再执行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("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

特点

张三是人，李四也是人。

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

常用方法

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，通常用于配置文件的读取

集合总结

概念

和数组区别

Collection体系

Collection父接口

常用方法

List子接口

常用方法

List实现类

ArrayList

常用方法

源码分析

LinkedList

常用方法与List一致

vector

常用方法

Set接口

HashSet

特点

不理解

SortedSet接口

TreeSet

特点

常用方法

Map接口

特点

常用方法

HashMap【重点】

常用方法与map一致

存储结构：

基本属性

元素结构--Node

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

扩容介绍

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

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

扩容结构--

treeifyBin方法--扩容判断

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

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

为什么要进行二次 hash？

HashMap 的 put 流程

TreeMap

Hashtable

Properties

热门文章

最新文章

相关课程

相关电子书

相关实验场景