Java面试题
转载自:https://blog.csdn.net/qq_30379689/article/details/72550701
概念相关面试题
1、进程和线程
- 地址空间和其他资源:进程间相互独立,进程中包括多个线程,线程间共享进程资源,某进程内的线程在其他进程内不可见
- 通信:进程间通信通过IPC机制,线程间通信通过数据段(如:全局变量)的读写,需要进程同步和互斥手段的辅助,以保证数据的一致性
- 调度和切换:进程是资源分配单位,线程是cpu调度单位,跟cpu真正打交道的是线程,线程上下文切换比进程上下文切换要快得多
2、内存溢出和内存泄漏
- 内存溢出:指程序在申请内存时,没有足够的空间供其使用
- 内存泄漏:指程序分配出去的内存不再使用,无法进行回收
3、面向对象和面向过程
1、面向过程
- 优点:性能比面向对象高,因为类的调用需要实例化,开销比较大
- 缺点:没有面向对象的易维护、易复用、易拓展
2、面向对象
- 优点:易维护、易复用、易拓展,由于面向对象有封装、继承、多态的特性,可以设计出低耦合的程序
- 缺点:性能比面向过程低
4、Java的四个基本特性
- 抽象:把现实生活某一类东西提取出来,成为该类东西的共有特性。抽象一般分为数据抽象和过程抽象,数据抽象是对象的属性,过程抽象是对象的行为特征
- 封装:把客观事物进行封装成抽象类,该类的数据和方法只让可信的类操作,对不可信的类隐藏。封装分为属性的封装和方法的封装
- 继承:从已有的类中派生出新的类,新的类能吸收已有类的数据属性和行为,并能扩展新的能力
- 多态:同一个行为具有多个不同表现形式或形态的能力,多态的前提是类与类之间必须存在关系,要么继承,要么实现
5、抽象类和接口的联系和区别
1、接口和抽象类的相似性
(1) 接口和抽象类都不能被实例化,它们都位于继承树的顶端,用于被其他类实现和继承。
(2)接口和抽象类都可以包含抽象方法,实现接口或继承抽象类的普通子类都必须实现这些抽象方法。
2、接口和抽象类的区别
(1)接口里只能包含抽象方法,静态方法和默认方法,不能为普通方法提供方法实现,抽象类则完全可以包含普通方法。
(2) 接口里只能定义静态常量,不能定义普通成员变量,抽象类里则既可以定义普通成员变量,也可以定义静态常量。
(3) 接口不能包含构造器,抽象类可以包含构造器,抽象类里的构造器并不是用于创建对象,而是让其子类调用这些构造器来完成属于抽象类的初始化操作。
(4)接口里不能包含初始化块,但抽象类里完全可以包含初始化块。
(5)一个类最多只能有一个直接父类,包括抽象类,但一个类可以直接实现多个接口,通过实现多个接口可以弥补Java单继承不足。
6、自动装箱与拆箱
Java采用了自动装箱和拆箱机制,节省了常用数值的内存开销和创建对象的开销,提高了效率
- 装箱:将基本数据类型包装成它们的引用类型 例:Integer i = 2;
- 拆箱:将包装类型转换成基本数据类型 例:int b = i;
7、序列化与反序列化
对象的序列化:是把对象转换成字节序列的过程
对象的反序列化:是把字节序列恢复为对象的过程
对象序列化的主要用途:
- 可以将字节序列永久的保存在硬盘中,通常放在文件中
- 可以在网络上传送字节序列
- 两个线程在进行远程通信时,彼此可以发送各种类型。发送方需要把这个Java对象转换为字节序列,接收方则需要把字节序列再恢复为Java对象
8、编译和运行
1、编译时和运行时
- 编译时:将Java文件编译成.class文件的过程,不涉及到内存的分配
- 运行时:将虚拟机执行.class文件的过程,涉及到内存的分配
2、编译时类型和运行时类型
- 编译时类型:由声明该变量时使用的类型决定
- 运行时类型:由实际赋给该变量的对象决定
3、编译时和运行时的动态绑定
- 在编译时,调用的是声明类型的成员方法
- 在运行时,调用的是实际类型的成员方法
- 对于调用引用实例的成员变量,无论是编译还是运行时,均是编译时类型的成员变量
9、GC简述
当程序员创建对象时,GC就开始监控这个对象的地址、大小以及使用情况。通常,GC采用有向图的方式记录和管理堆(heap)中的所有对象,通过这种方式确定哪些对象是”可达的”,哪些对象是”不可达的”。当GC确定一些对象为”不可达”时,GC就有责任回收这些内存空间。但是,为了保证 GC能够在不同平台实现的问题,Java规范对GC的很多行为都没有进行严格的规定
10、Java中4种引用类型
- StrongReference(强引用):从不回收,对象一直存在,当JVM停止的时候才被终止
- SoftReference(软引用):可以和引用队列(ReferenceQueue)联合使用,当内存不足时被终止
- WeakReference(弱引用):可以和引用队列(ReferenceQueue)联合使用,当内存不足时,通过GC后被终止
- PhantomReference(虚引用):必须和引用队列(ReferenceQueue)联合使用,随时会被回收,GC后被终止
字符串相关面试题
1、String、StringBuffer和StringBuilder
1、可变性
- String类是用字符数组保存字符串,即private final char value[],所以String对象不可变
- StringBuffer类与StringBuilder类都是继承AbstractStringBuilder类,AbstractStringBuilder是用字符数组保存字符串,即char value[],所以StringBuffer与StringBuilder对象是可变的
2、线程安全性
- String类对象不可变,所以理解为常量,线程安全
- StringBuffer类对方法加了同步锁,线程安全
- StringBuilder类对方法未加同步锁,线程不安全
3、性能
- String类进行改变的时候,都会产生新的String对象,然后将指针指向新的String对象
- StringBuffer进行改变的时候,都会复用自身对象,性能比String高
- StringBuilder行改变的时候,都会复用自身对象,相比StringBuffer能获得10%~15%左右的性能提升,但是得承担多线程的不安全的风险
2、构造器Constructor是否可被override
- 构造器不能被重写
- 构造器不能被static修饰
- 构造器只能用private、protected、public修饰
- 构造器不能有返回值
3、String类是否可以继承
String类由final类,故不可以继承,凡是由final修饰的类都不能继承
集合相关面试题
可查看我的博客,按顺序阅读,需要您具备数据结构基础,且基于JDK1.7
————————————————————————————————————–- Java基础——HashMap源码分析及面试题解答
- HashMap是基于哈希表的Map接口的非同步实现
- HashMap中元素的key是唯一的、value值可重复
- HashMap允许使用null值和null键
- HashMap中的元素是无序的
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 如果key存在,key不会覆盖,新的value会代替旧的value,该方法返回的是旧的 value
- 如果key不存在,该方法返回的是null
- 根据key的hashCode重新计算hash值,根据hash值得到这个元素在数组中的位置(即下标)
- 如果数组该位置上已经存放有其他元素,那么在这个位置上的元素将以链表的形式存放,新加入的放在链头,最先加入的放在链尾
- 如果数组该位置上没有元素,就直接将该元素放到此数组中的该位置上
- 根据计算出的hash值,找到数组table对应的i索引位置,取出数组table的i索引处的key-value(旧的)
- 将新的key-value放在数组table的i索引处,并将新的key-value的next指向旧的key-value,从而形成链表
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 从HashMap中get元素时,首先计算key的hashCode,找到数组中对应位置的某一元素
- 通过key的equals方法在对应位置的链表中找到需要的元素
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 1
- 2
- 3
- 1
- 2
- 3
- HashMap():构建一个初始容量为 16,负载因子为 0.75 的 HashMap
- HashMap(int initialCapacity):构建一个初始容量为 initialCapacity,负载因子为 0.75 的 HashMap
- HashMap(int initialCapacity, float loadFactor):以指定初始容量、指定的负载因子创建一个 HashMap
- 1
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 1
- 2
- 3
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 1
- 2
- 3
- 4
- 5
- 6
- Java基础——HashSet源码分析
- HashSet是无序的
- HashSet将对象存储在key中,且不允许key重复
- HashSet的Value是固定的
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- Java基础——HashTable源码分析
- HashTable是基于哈希表的Map接口的同步实现
- HashTable中元素的key是唯一的,value值可重复
- HashTable中元素的key和value不允许为null,如果遇到null,则返回NullPointerException
- HashTable中的元素是无序的
- 1
- 2
- 3
- Dictionary类是任何可将键映射到相应值的类的抽象父类,每个键和值都是对象
- Dictionary源码注释指出 Dictionary 这个类过时了,新的实现类应该实现Map接口
- table:一个Entry[]数组类型,而Entry(在 HashMap 中有讲解过)就是一个单向链表。哈希表的”key-value键值对”都是存储在Entry数组中的
- count:Hashtable的大小,它是Hashtable保存的键值对的数量
- threshold:Hashtable的阈值,用于判断是否需要调整Hashtable的容量,threshold的值 = (容量 * 负载因子)
- loadFactor:负载因子
- modCount:用来实现fail-fast机制的
- public Hashtable(int initialCapacity, float loadFactor): 用指定初始容量和指定加载因子构造一个新的空哈希表
- public Hashtable(int initialCapacity):用指定初始容量和默认的加载因子 (0.75) 构造一个新的空哈希表
- public Hashtable():默认构造函数,容量为 11,加载因子为 0.75
- public Hashtable(Map< ? extends K, ? extends V> t):构造一个与给定的Map具有相同映射关系的新哈希表
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 判断value是否为空,为空则抛出异常
- 计算key的hash值,并根据hash值获得key在table数组中的位置index
- 如果table[index]元素为空,将元素插入到table[index]位置
- 如果table[index]元素不为空,则进行遍历链表,如果遇到相同的key,则新的value替代旧的value,并返回旧 value,否则将元素插入到链头,返回null
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 通过 hash()方法求得key的哈希值
- 根据hash值得到index索引
- 迭代链表,返回匹配的key的对应的value,找不到则返回null
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 如果涉及到多线程同步时,建议采用HashTable
- 没有涉及到多线程同步时,建议采用HashMap
- Collections 类中存在一个静态方法:synchronizedMap(),该方法创建了一个线程安全的 Map 对象,并把它作为一个封装的对象来返回
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- Java基础——LinkedHashMap源码分析
- LinkedHashMap是基于哈希表的Map接口的非同步实现
- LinkedHashMap是HashMap的子类
- LinkedHashMap是有序的
- LinkedHashMap中元素的key是唯一的、value值可重复
- LinkedHashMap允许null键和null值
- 按插入顺序的链表:在LinkedHashMap调用get方法后,输出的顺序和输入时的相同,这就是按插入顺序的链表,默认是按插入顺序排序
- 按访问顺序的链表:在LinkedHashMap调用get方法后,会将这次访问的元素移至链表尾部,不断访问可以形成按访问顺序排序的链表。简单的说,按最近最少访问的元素进行排序(类似LRU算法)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 1
- 2
- 3
- 4
- 1
- 1
- 2
- 3
- 4
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 替换了LinkedHashMap的构造函数,使用三个参数的构造函数,第三个参数传进true就是表明用访问顺序来排序,默认是false(即插入顺序)
- 增加了两句LinkedHashMap的get方法,来表示最近已经访问过这两个元素了
- 1
- 2
- 3
- 4
- 5
- 1
- 2
- 3
- 4
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 1
- 2
- 3
- 4
- 1
- 2
- 3
- 4
- 5
- 6
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- removeEldestEntry(Map.Entry< K,V> eldest):该方法可以提供在每次添加新条目时移除最旧条目的实现程序,默认返回 false,即永远不能移除最旧的元素
- Java基础——LinkedHashSet源码分析
- LinkedHashSet是非同步的
- LinkedHashSet是有序的,分别是插入顺序和访问顺序,LinkedHashSet的有序性可参考LinkedHashMap的有序性,可以举一反三
- LinkedHashSet继承于HashSet,内部基于LinkedHashMap实现的,也就是说LinkedHashSet和HashSet一样只存储一个值,LinkedHashSet和LinkedHashMap一样维护着一个运行于所有条目的双向链表
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- Java基础——ArrayList源码分析
- ArrayList可以理解为动态数组,它的容量能动态增长,该容量是指用来存储列表元素的数组的大小,随着向ArrayList中不断添加元素,其容量也自动增长
- ArrayList允许包括null在内的所有元素
- ArrayList是List接口的非同步实现
- ArrayList是有序的
- 1
- 2
- 3
- 4
- 5
- ArrayList实现了List接口、底层使用数组保存所有元素,其操作基本上是对数组的操作
- ArrayList继承了AbstractList抽象类,它是一个数组队列,提供了相关的添加、删除、修改、遍历等功能
- ArrayList实现了RandmoAccess接口,即提供了随机访问功能,RandmoAccess是java中用来被List实现,为List提供快速访问功能的,我们可以通过元素的序号快速获取元素对象,这就是快速随机访问
- ArrayList实现了Cloneable接口,即覆盖了函数clone(),能被克隆
- ArrayList实现了java.io.Serializable接口,意味着ArrayList支持序列化
- public ArrayList():可以构造一个默认初始容量为10的空列表
- public ArrayList(int initialCapacity):构造一个指定初始容量的空列表
- public ArrayList(Collection< ? extends E> c):构造一个包含指定collection的元素的列表,这些元素按照该collection的迭代器返回它们的顺序排列的
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 删除数组中index位置下的元素
- 删除数组中相同对象的元素
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- Java基础——LinkedList源码分析
- LinkedList基于链表的List接口的非同步实现
- LinkedList允许包括null在内的所有元素
- LinkedList是有序的
- LinkedList是fail-fast的
- 1
- 2
- 3
- 4
- 5
- 6
- LinkedList实现了 List 接口、底层基于链表实现的,所以它的插入和删除操作比ArrayList更加高效,但链表的随机访问的效率要比ArrayList差
- LinkedList继承自AbstractSequenceList抽象类,提供了List接口骨干性的实现以减少实现 List 接口的复杂度
- LinkedList实现了Deque接口,定义了双端队列的操作,双端队列是一种具有队列和栈的性质的数据结构,双端队列中的元素可以从两端弹出,其限定插入和删除操作在表的两端进行
- LinkedList实现了Cloneable接口,即覆盖了函数clone(),能被克隆
- LinkedList实现了java.io.Serializable接口,意味着ArrayList支持序列化
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- void addFirst(E e):添加元素到链头
- void addLast(E e):添加元素到链尾
- E removeFirst():移除链头元素
- E removeLast():移除链尾元素
- 对于随机访问的两个方法,get和set,ArrayList优于LinkedList,因为LinkedList要移动指针
- 对于新增和删除两个方法,add和remove,LinedList比较占优势,因为ArrayList要移动数据
- Java基础——ConcurrentHashMap源码分析
- ConcurrentHashMap基于双数组和链表的Map接口的同步实现
- ConcurrentHashMap中元素的key是唯一的、value值可重复
- ConcurrentHashMap不允许使用null值和null键
- ConcurrentHashMap是无序的
- Hashtable
- Collections.synchronizedMap(hashMap)
- Segment的数组(final Segment< K,V>[] segments),Segment 是ConcurrentHashMap的内部类
- Segment 类中,包含了一个HashEntry的数组(transient volatile HashEntry< K,V>[] table), HashEntry也是ConcurrentHashMap的内部类
- HashEntry中,包含key和value以及next指针(类似于HashMap中 Entry),所以HashEntry可以构成一个链表
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- table:链表数组,数组中的每个元素代表链表的头部
- count:Segment中元素的数量
- modCount:对table大小造成影响的操作数量(比如put和remove)
- threshold:阈值,Segment里面元素超过这个值就会对Segment进行扩容
- loadFactor:负载因子,用于确定threshold
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 除了value以外,其他几个变量都是final的,这样做为了防止链表结构被破坏,出现ConcurrentModification的情况。
- next域被final修饰,说明每次往链表添加元素时,只能添加在链头,这样next才能不够被修改
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 用分离锁实现多个线程间的更深层次的共享访问,减小了请求同一个锁的频率
- 用HashEntery对象的不变性来降低执行读操作的线程在遍历链表期间对加锁的需求
- 通过对同一个Volatile变量的写 / 读访问,协调不同线程间读 / 写操作的内存可见性
- Java基础——Vector源码分析
HashMap是什么
HashMap的数据结构
HashMap是一个“链表散列”的数据结构,即数组和链表的结合体,如图所示
从图中看出,HashMap底层就是一个数组结构,数组中的每一项又是一个链表,当新建一个 HashMap 的时候,就会初始化一个数组,我们可以查看HashMap源码,在构造函数中
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
init();
}
第18行代码table = new Entry[capacity];
创建了一个 Entry 的数组,也就是图中的table数组,那么 Entry 又是什么结构呢?
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;
……
}
Entry是一个static class,其中包含了 key 和 value,也就是键值对,另外还包含了一个next的Entry指针。我们可以总结出Entry就是数组中的元素,每个Entry其实就是一个key-value对,它持有一个指向下一个元素的引用,这就构成了链表
HashMap的存储
知道HashMap的数据结构之后,下面就来研究如何把元素存进HashMap中
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V put(K key, V value) {
//其允许存放null的key和null的value,当其key为null时,调用putForNullKey方法,放入到table[0]的这个位置
if (key == null)
return putForNullKey(value);
//通过调用hash方法对key进行哈希,得到哈希之后的数值。该方法实现可以通过看源码,其目的是为了尽可能的让键值对可以分不到不同的桶中
int hash = hash(key);
//根据上一步骤中求出的hash得到在数组中是索引i
int i = indexFor(hash, table.length);
//如果i处的Entry不为null,则通过其next指针不断遍历e元素的下一个元素。
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
在官方注释中提到:当调用我们put方法的时候
在源代码中可以看出:当我们往HashMap中put元素的时候
addEntry(hash, key, value, i)方法的作用:
void addEntry(int hash, K key, V value, int bucketIndex) {
//如果数组大小不够,会扩充数组大小,后面会讲到
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
// 获取指定 bucketIndex 索引处的 Entry
Entry<K,V> e = table[bucketIndex];
// 将新创建的 Entry 放入 bucketIndex 索引处,并让新的 Entry 指向原来的 Entr
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
当系统决定存储HashMa 中的key-value时,完全没有考虑Entry中的value,仅仅只是根据key来计算并决定每个Entry的存储位置。我们完全可以把Map集合中的value当成key的附属,当系统决定了key的存储位置之后,value随之保存在那里
HashMap的读取
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
final Entry<K,V> getEntry(Object key) {
int hash = (key == null) ? 0 : hash(key);
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
从上面的源代码中可以看出:
HashMap简单归纳
简单地说,HashMap在底层将key-value当成一个整体进行处理,这个整体就是一个Entry对象。HashMap底层采用一个 Entry[]数组来保存所有的key-value,当需要存储一个Entry对象时,会根据 hash 算法来决定其在数组中的存储位置,在根据equals方法决定其在该数组位置上的链表中的存储位置;当需要取出一个Entry时,也会根据hash算法找到其在数组中的存储位置,再根据equals方法从该位置上的链表中取出该Entry
HashMap的hash算法
在HashMap的存储和读取中,都用到了hash()这个算法,hash(int h)方法是根据key的hashCode重新计算一次散列。此算法加入了高位计算,防止低位不变,高位变化时,造成的hash冲突
final int hash(Object k) {
int h = 0;
if (useAltHashing) {
if (k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h = hashSeed;
}
//得到k的hashcode值
h ^= k.hashCode();
//进行计算
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
我们知道HashMap中要找到某个元素时,需要根据key的hash值来求得对应数组中的位置。如何计算这个位置就是hash算法。前面说过HashMap的数据结构是数组和链表的结合,所以我们当然希望这个HashMap里面的元素位置尽量分布均匀些,尽量使得每个位置上的元素数量只有一个,那么当我们用hash算法求得这个位置的时候,马上就可以知道对应位置的元素就是我们要读取的,而不用再去遍历链表,这样就大大优化了查询的效率
HashMap的容量
对于任意给定的对象,只要它的hashCode()返回值相同,那么程序调用hash(int h)方法所计算得到的hash码值总是相同的。我们首先想到的就是把hash值对数组长度取模运算,这样一来,元素的分布相对来说是比较均匀的。但是,“模”运算的消耗还是比较大的,在HashMap中是这样做的,调用 indexFor(int h, int length) 方法来计算该对象应该保存在table数组的哪个索引处
static int indexFor(int h, int length) {
return h & (length-1);
}
这个方法非常巧妙,它通过 h & (table.length -1) 来得到该对象的保存位,而HashMap底层数组的长度总是 2 的 n 次方,这是HashMap在速度上的优化。在HashMap构造器中有如下代码:
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
这段代码保证初始化时HashMap的容量总是 2 的 n 次方,即底层数组的长度总是为 2 的 n 次方。当length总是 2 的 n 次方时,h& (length-1)运算等价于对 length 取模,也就是 h%length,但是 & 比 % 具有更高的效率。这看上去很简单,其实比较有玄机的,我们举个例子来说明,假设数组长度分别为 15 和 16,优化后的 hash 码分别为 8 和 9,那么 & 运算后的结果如下:
h & (table.length-1) | hash | table.length-1 | 结果 | |
---|---|---|---|---|
8 & (15-1) | 0100 | & | 1110 | = 0100 |
9 & (15-1) | 0101 | & | 1110 | = 0100 |
8 & (16-1) | 0100 | & | 1111 | = 0100 |
9 & (16-1) | 0101 | & | 1111 | = 0101 |
从上面的例子中可以看出:当它们和 15-1(1110)“与”的时候,产生了相同的结果,也就是说它们会定位到数组中的同一个位置上去,这就产生了碰撞,8 和 9 会被放到数组中的同一个位置上形成链表,那么查询的时候就需要遍历这个链表,得到8或者9,这样就降低了查询的效率。同时,我们也可以发现,当数组长度为 15 的时候,hash 值会与 15-1(1110)进行“与”,那么最后一位永远是 0,而 0001,0011,0101,1001,1011,0111,1101 这几个位置永远都不能存放元素了,空间浪费相当大,更糟的是这种情况中,数组可以使用的位置比数组长度小了很多,这意味着进一步增加了碰撞的几率,减慢了查询的效率!而当数组长度为16时,即为2的n次方时,2n-1 得到的二进制数的每个位上的值都为 1,这使得在低位上&时,得到的和原 hash 的低位相同,加之 hash(int h)方法对 key 的 hashCode 的进一步优化,加入了高位计算,就使得只有相同的 hash 值的两个值才会被放到数组中的同一个位置上形成链表。所以说,当数组长度为 2 的 n 次幂的时候,不同的 key 算得得 index 相同的几率较小,那么数据在数组上分布就比较均匀,也就是说碰撞的几率小,相对的,查询的时候就不用遍历某个位置上的链表,这样查询效率也就较高了
HashMap的resize(rehash)
当 HashMap 中的元素越来越多的时候,hash冲突的几率也就越来越高,因为数组的长度是固定的,所以为了提高查询的效率,就要对HashMap的数组进行扩容,在HashMap数组扩容之后,最消耗性能的点是:原数组中的数据必须重新计算其在新数组中的位置,并放进去,这就是 resize(rehash)
那么HashMap什么时候进行扩容呢?当HashMap中的元素个数超过(数组大小 *loadFactor)时,就会进行数组扩容,loadFactor指的是负载因子,从字面上理解就是HashMap能够承受住自身负载(大小或容量)的因子,loadFactor的默认值为 0.75,这是一个折中的取值。也就是说,默认情况下,数组大小为 16,那么当HashMap中元素个数超过 16*0.75=12 的时候,就把数组的大小扩展为 2*16=32,即扩大一倍,然后重新计算每个元素在数组中的位置,而这是一个非常消耗性能的操作,所以如果我们已经预知 HashMap 中元素的个数,那么预设元素的个数能够有效的提高 HashMap 的性能
负载因子 loadFactor 衡量的是一个散列表的空间的使用程度,负载因子越大表示散列表的装填程度越高,反之愈小。对于使用链表法的散列表来说,查找一个元素的平均时间是 O(1+a),因此如果负载因子越大,对空间的利用更充分,然而后果是查找效率的降低;如果负载因子太小,那么散列表的数据将过于稀疏,对空间造成严重浪费
HashMap的构造方法
HashMap 包含如下几个构造器:
HashMap 的实现中,通过 threshold 字段来判断 HashMap 的最大容量:
threshold = (int)(capacity * loadFactor);
threshold就是在loadFactor和capacity对应下允许的最大元素数目,默认的的负载因子 0.75 是对空间和时间效率的一个平衡选择,当容量超出此最大容量时,就会发生resize,resize后的 HashMap 容量是容量的两倍,这点可以从addEntry方法看出
void addEntry(int hash, K key, V value, int bucketIndex) {
//如果数组大小不够,会扩充数组大小
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
HashMap的Fail-Fast机制
HashMap不是线程安全的,因此在使用迭代器的过程中有其他线程修改了map,那么将抛出 ConcurrentModificationException,这就是所谓 fail-fas机制,fail-fast机制是 java 集合(Collection)中的一种错误机制,当多个线程对同一个集合的内容进行操作时,就可能会产生fail-fast事件。这一机制在源码中的实现是通过modCount域(修改次数),对 HashMap 内容进行修改时都将增加这个值,那么在迭代器初始化过程中会将这个值赋给迭代器的 expectedModCount
HashIterator() {
expectedModCount = modCount;
if (size > 0) { // advance to first entry
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
}
在迭代过程中,判断 modCount 跟 expectedModCount 是否相等,如果不相等就表示已经有其他线程修改了 Map。同时, modCount 声明为 volatile,保证了线程之间修改的可见性
final Entry<K,V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
在 HashMap 的 API 中指出:
由所有 HashMap 类的“collection 视图方法”所返回的迭代器都是快速失败的:在迭代器创建之后,如果从结构上对映射进行修改,除非通过迭代器本身的 remove 方法,其他任何时间任何方式的修改,迭代器都将抛出 ConcurrentModificationException。因此,面对并发的修改,迭代器很快就会完全失败,而不冒在将来不确定的时间发生任意不确定行为的风险
注意,迭代器的快速失败行为不能得到保证,一般来说,存在非同步的并发修改时,不可能作出任何坚决的保证。快速失败迭代器尽最大努力抛出 ConcurrentModificationException。因此,编写依赖于此异常的程序的做法是错误的,正确做法是:迭代器的快速失败行为应该仅用于检测程序错误
解决方案:
在上文中也提到,fail-fast 机制,是一种错误检测机制。它只能被用来检测错误,因为 JDK 并不保证 fail-fast 机制一定会发生。若在多线程环境下使用 fail-fast 机制的集合,建议使用“java.util.concurrent 包下的类”去取代“java.util 包下的类”
HashMap的两种遍历方式
第一种,效率高,建议使用
Map map = new HashMap();
Iterator iter = map.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
Object key = entry.getKey();
Object val = entry.getValue();
}
第二种,效率低,建议不要使用
Map map = new HashMap();
Iterator iter = map.keySet().iterator();
while (iter.hasNext()) {
Object key = iter.next();
Object val = map.get(key);
}
HashMap的面试题解答
1、你用过HashMap吗?什么是HashMap?你为什么用到它?
用过,HashMap是基于哈希表的Map接口的非同步实现,它允许null键和null值,且HashMap依托于它的数据结构的设计,存储效率特别高,这是我用它的原因
2、你知道HashMap的工作原理吗?你知道HashMap的get()方法的工作原理吗?
上面两个问题属于同一答案的问题
HashMap是基于hash算法实现的,通过put(key,value)存储对象到HashMap中,也可以通过get(key)从HashMap中获取对象。当我们使用put的时候,首先HashMap会对key的hashCode()的值进行hash计算,根据hash值得到这个元素在数组中的位置,将元素存储在该位置的链表上。当我们使用get的时候,首先HashMap会对key的hashCode()的值进行hash计算,根据hash值得到这个元素在数组中的位置,将元素从该位置上的链表中取出
3、当两个对象的hashcode相同会发生什么?
hashcode相同,说明两个对象HashMap数组的同一位置上,接着HashMap会遍历链表中的每个元素,通过key的equals方法来判断是否为同一个key,如果是同一个key,则新的value会覆盖旧的value,并且返回旧的value。如果不是同一个key,则存储在该位置上的链表的链头
4、如果两个键的hashcode相同,你如何获取值对象?
遍历HashMap链表中的每个元素,并对每个key进行hash计算,最后通过get方法获取其对应的值对象
5、如果HashMap的大小超过了负载因子(load factor)定义的容量,怎么办?
负载因子默认是0.75,HashMap超过了负载因子定义的容量,也就是说超过了(HashMap的大小*负载因子)这个值,那么HashMap将会创建为原来HashMap大小两倍的数组大小,作为自己新的容量,这个过程叫resize或者rehash
6、你了解重新调整HashMap大小存在什么问题吗?
当多线程的情况下,可能产生条件竞争。当重新调整HashMap大小的时候,确实存在条件竞争,如果两个线程都发现HashMap需要重新调整大小了,它们会同时试着调整大小。在调整大小的过程中,存储在链表中的元素的次序会反过来,因为移动到新的数组位置的时候,HashMap并不会将元素放在LinkedList的尾部,而是放在头部,这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了,那么就死循环了
7、我们可以使用自定义的对象作为键吗?
可以,只要它遵守了equals()和hashCode()方法的定义规则,并且当对象插入到Map中之后将不会再改变了。如果这个自定义对象时不可变的,那么它已经满足了作为键的条件,因为当它创建之后就已经不能改变了。
HashSet是什么
HashSet是基于HashMap实现的,底层采用HashMap来保存元素,本篇文章需要在HashMap的基础上进行阅读,对于HashMap的工作原理请阅读我上一篇文章:Java基础——HashMap详细解析及面试题解答
HashSet的构造函数
private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();
/**
* 默认的无参构造器,构造一个空的HashSet。
*
* 实际底层会初始化一个空的HashMap,并使用默认初始容量为16和加载因子0.75。
*/
public HashSet() {
map = new HashMap<E,Object>();
}
/**
* 构造一个包含指定collection中的元素的新set。
*
* 实际底层使用默认的加载因子0.75和足以包含指定collection中所有元素的初始容量来创建一个HashMap。
* @param c 其中的元素将存放在此set中的collection。
*/
public HashSet(Collection<? extends E> c) {
map = new HashMap<E,Object>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
/**
* 以指定的initialCapacity和loadFactor构造一个空的HashSet。
*
* 实际底层以相应的参数构造一个空的HashMap。
* @param initialCapacity 初始容量。
* @param loadFactor 加载因子。
*/
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<E,Object>(initialCapacity, loadFactor);
}
/**
* 以指定的initialCapacity构造一个空的HashSet。
*
* 实际底层以相应的参数及加载因子loadFactor为0.75构造一个空的HashMap。
* @param initialCapacity 初始容量。
*/
public HashSet(int initialCapacity) {
map = new HashMap<E,Object>(initialCapacity);
}
/**
* 以指定的initialCapacity和loadFactor构造一个新的空链接哈希集合。此构造函数为包访问权限,不对外公开,
* 实际只是是对LinkedHashSet的支持。
*
* 实际底层会以指定的参数构造一个空LinkedHashMap实例来实现。
* @param initialCapacity 初始容量。
* @param loadFactor 加载因子。
* @param dummy 标记。
*/
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
}
HashSet的构造方法基于HashMap的构造方法,如果熟悉HashMap的同学,请先学习完HashMap再来看HashSet
HashSet的存储
/**
* @param e 将添加到此set中的元素。
* @return 如果此set尚未包含指定元素,则返回true。
*/
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
由于HashMap的put方法添加key-value时,当新放入HashMap的Entry中key与集合中原有Entry的key相同(hashCode()返回值相等,通过 equals 比较也返回 true),新添加的Entry的value会将覆盖原来Entry的value(HashSet 中的 value 都是PRESENT),但key不会有任何改变,因此向HashSet中添加一个已经存在的元素时,新添加的集合元素将不会被放入HashMap中,原来的元素也不会有任何改变,这也就满足了 Set 中元素不重复的特性
该方法如果添加的是在HashSet中不存在的,则返回true;如果添加的元素已经存在,返回false。其原因在于我们之前提到的关于HashMap的put方法。该方法在添加key不重复的键值对的时候,会返回null
HashSet的其他API
/**
* 如果此set包含指定元素,则返回true。
* 更确切地讲,当且仅当此set包含一个满足(o==null ? e==null : o.equals(e))的e元素时,返回true。
*
* 底层实际调用HashMap的containsKey判断是否包含指定key。
* @param o 在此set中的存在已得到测试的元素。
* @return 如果此set包含指定元素,则返回true。
*/
public boolean contains(Object o) {
return map.containsKey(o);
}
/**
* 如果指定元素存在于此set中,则将其移除。更确切地讲,如果此set包含一个满足(o==null ? e==null : o.equals(e))的元素e,
* 则将其移除。如果此set已包含该元素,则返回true
*
* 底层实际调用HashMap的remove方法删除指定Entry。
* @param o 如果存在于此set中则需要将其移除的对象。
* @return 如果set包含指定元素,则返回true。
*/
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
/**
* 返回此HashSet实例的浅表副本:并没有复制这些元素本身。
*
* 底层实际调用HashMap的clone()方法,获取HashMap的浅表副本,并设置到HashSet中。
*/
public Object clone() {
try {
HashSet<E> newSet = (HashSet<E>) super.clone();
newSet.map = (HashMap<E, Object>) map.clone();
return newSet;
} catch (CloneNotSupportedException e) {
throw new InternalError();
}
}
HashMap与HashSet的区别
HashMap | HashSet |
---|---|
HashMap实现了Map接口 | HashSet实现了Set接口 |
HashMap储存键值对 | HashSet仅仅存储对象 |
使用put()方法将元素放入map中 | 使用add()方法将元素放入set中 |
HashMap中使用键对象来计算hashcode值 | HashSet使用成员对象来计算hashcode值 |
HashMap比较快,因为是使用唯一的键来获取对象 | HashSet较HashMap来说比较慢 |
HashTable是什么
public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable{}
HashTable跟HashMap一样,同样是链表散列的数据结构,从源码中我们可以看出,Hashtable 继承于Dictionary类,实现了Map, Cloneable,Serializable接口
Hashtable成员变量
Hashtable构造方法
Hashtable 一共提供了 4 个构造方法
Hashtable的存储
public synchronized V put(K key, V value) {
//确保value不为null
if (value == null) {
throw new NullPointerException();
}
//确保key不在hashtable中
//首先,通过hash方法计算key的哈希值,并计算得出index值,确定其在table[]中的位置
//其次,迭代index索引位置的链表,如果该位置处的链表存在相同的key,则替换value,返回旧的value
Entry tab[] = table;
int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
V old = e.value;
e.value = value;
return old;
}
}
modCount++;
if (count >= threshold) {
//如果超过阀值,就进行rehash操作
rehash();
tab = table;
hash = hash(key);
index = (hash & 0x7FFFFFFF) % tab.length;
}
//将值插入,返回的为null
Entry<K,V> e = tab[index];
// 创建新的Entry节点,并将新的Entry插入Hashtable的index位置,并设置e为新的Entry的下一个元素
tab[index] = new Entry<>(hash, key, value, e);
count++;
return null;
}
存储的流程如下:
Hashtable的获取
public synchronized V get(Object key) {
Entry tab[] = table;
int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return e.value;
}
}
return null;
}
获取的流程如下:
Hashtable遍历方式
Hashtable有4种遍历方式:
//1、使用keys()
Enumeration<String> en1 = table.keys();
while(en1.hasMoreElements()) {
en1.nextElement();
}
//2、使用elements()
Enumeration<String> en2 = table.elements();
while(en2.hasMoreElements()) {
en2.nextElement();
}
//3、使用keySet()
Iterator<String> it1 = table.keySet().iterator();
while(it1.hasNext()) {
it1.next();
}
//4、使用entrySet()
Iterator<Entry<String, String>> it2 = table.entrySet().iterator();
while(it2.hasNext()) {
it2.next();
}
Hashtable与HashMap的区别
Hashtable | HashMap |
---|---|
方法是同步的 | 方法是非同步的 |
基于Dictionary类 | 基于AbstractMap,而AbstractMap基于Map接口的实现 |
key和value都不允许为null,遇到null,直接返回 NullPointerException | key和value都允许为null,遇到key为null的时候,调用putForNullKey方法进行处理,而对value没有处理 |
hash数组默认大小是11,扩充方式是old*2+1 | hash数组的默认大小是16,而且一定是2的指数 |
多线程存在的问题
synchronizedMap()其实就是对Map的方法加层同步锁,从源码中可以看出
//Collections.synchronizedMap(Map<K, V>)
public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {
return new SynchronizedMap<K,V>(m);
}
private static class SynchronizedMap<K,V> implements Map<K,V>, Serializable {
private static final long serialVersionUID = 1978198479659022715L;
private final Map<K,V> m; // Backing Map
//同步锁
final Object mutex; // Object on which to synchronize
SynchronizedMap(Map<K,V> m) {
if (m==null)
throw new NullPointerException();
this.m = m;
//把this本身作为锁监视器, 这样任何线程访问他的方法都要获取该监视器.
mutex = this;
}
SynchronizedMap(Map<K,V> m, Object mutex) {
this.m = m;
this.mutex = mutex;
}
public int size() {
synchronized(mutex) {return m.size();}
}
//重写map的emty方法
public boolean isEmpty() {
synchronized(mutex) {return m.isEmpty();}
}
public boolean containsKey(Object key) {
synchronized(mutex) {return m.containsKey(key);}
}
public boolean containsValue(Object value) {
synchronized(mutex) {return m.containsValue(value);}
}
public V get(Object key) {
synchronized(mutex) {return m.get(key);}
}
public V put(K key, V value) {
synchronized(mutex) {return m.put(key, value);}
}
public V remove(Object key) {
synchronized(mutex) {return m.remove(key);}
}
public void putAll(Map<? extends K, ? extends V> map) {
synchronized(mutex) {m.putAll(map);}
}
public void clear() {
synchronized(mutex) {m.clear();}
}
private transient Set<K> keySet = null;
private transient Set<Map.Entry<K,V>> entrySet = null;
private transient Collection<V> values = null;
//重写keySet方法
public Set<K> keySet() {
synchronized(mutex) {
if (keySet==null)
//mutex传给SynchronizedSet, 这样对于set内部操作也需要获取锁.
keySet = new SynchronizedSet<K>(m.keySet(), mutex);
return keySet;
}
}
public Set<Map.Entry<K,V>> entrySet() {
synchronized(mutex) {
if (entrySet==null)
entrySet = new SynchronizedSet<Map.Entry<K,V>>(m.entrySet(), mutex);
return entrySet;
}
}
public Collection<V> values() {
synchronized(mutex) {
if (values==null)
values = new SynchronizedCollection<V>(m.values(), mutex);
return values;
}
}
public boolean equals(Object o) {
synchronized(mutex) {return m.equals(o);}
}
public int hashCode() {
synchronized(mutex) {return m.hashCode();}
}
public String toString() {
synchronized(mutex) {return m.toString();}
}
private void writeObject(ObjectOutputStream s) throws IOException {
synchronized(mutex) {s.defaultWriteObject();}
}
}
LinkedHashMap是什么
LinkedHashMap的有序性
LinkedHashMap底层使用哈希表与双向链表来保存所有元素,它维护着一个运行于所有条目的双向链表(如果学过双向链表的同学会更好的理解它的源代码),此链表定义了迭代顺序,该迭代顺序可以是插入顺序或者是访问顺序
我们可以通过例子来理解我们上面所说的LinkedHashMap的插入顺序和访问顺序
public static void main(String[] args) {
Map<String, String> map = new HashMap<String, String>();
map.put("apple", "苹果");
map.put("watermelon", "西瓜");
map.put("banana", "香蕉");
map.put("peach", "桃子");
Iterator iter = map.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
System.out.println(entry.getKey() + "=" + entry.getValue());
}
}
上面是简单的HashMap代码,通过控制台的输出,我们可以看到HashMap是没有顺序的
banana=香蕉
apple=苹果
peach=桃子
watermelon=西瓜
我们现在将HashMap换成LinkedHashMap,其他代码不变
Map<String, String> map = new LinkedHashMap<String, String>();
看一下控制台的输出
apple=苹果
watermelon=西瓜
banana=香蕉
peach=桃子
我们可以看到,其输出顺序是完成按照插入顺序的,也就是我们上面所说的保留了插入的顺序。下面我们修改一下代码,通过访问顺序进行排序
public static void main(String[] args) {
Map<String, String> map = new LinkedHashMap<String, String>(16,0.75f,true);
map.put("apple", "苹果");
map.put("watermelon", "西瓜");
map.put("banana", "香蕉");
map.put("peach", "桃子");
map.get("banana");
map.get("apple");
Iterator iter = map.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
System.out.println(entry.getKey() + "=" + entry.getValue());
}
}
代码与之前的相比
//修改的代码
Map<String, String> map = new LinkedHashMap<String, String>(16,0.75f,true);
......
map.get("banana");
map.get("apple");
看一下控制台的输出结果
watermelon=西瓜
peach=桃子
banana=香蕉
apple=苹果
我们可以看到,顺序是先从最少访问的元素开始遍历(西瓜、桃子),而香蕉、苹果是因为分别调用了get方法,香蕉是最先访问的,所以它的比苹果更少用一些。这也就是我们之前提到过的,LinkedHashMap可以选择按照访问顺序进行排序
LinkedHashMap的成员变量
LinkedHashMap采用的hash算法和HashMap相同,但是它重新定义了数组中保存的元素Entry,该Entry除了保存当前对象的引用外,还保存了其上一个元素before和下一个元素after的引用,从而在哈希表的基础上又构成了双向链接列表
/**
* 如果为true,则按照访问顺序;如果为false,则按照插入顺序。
*/
private final boolean accessOrder;
/**
* 双向链表的表头元素。
*/
private transient Entry<K,V> header;
/**
* LinkedHashMap的Entry元素。
* 继承HashMap的Entry元素,又保存了其上一个元素before和下一个元素after的引用。
*/
private static class Entry<K,V> extends HashMap.Entry<K,V> {
Entry<K,V> before, after;
……
}
LinkedHashMap的初始化
对于LinkedHashMap而言,它可以通过重写父类相关的方法,来实现自己的链接列表特性。通过源代码可以看出,在LinkedHashMap的构造方法中,实际调用了父类HashMap的相关构造方法来构造一个底层存放的table数组,但额外可以增加accessOrder这个参数,如果不设置,默认为false,代表按照插入顺序进行迭代,当然可以显式设置为true,代表以访问顺序进行迭代
public LinkedHashMap(int initialCapacity, float loadFactor,boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
我们已经知道 LinkedHashMap的Entry元素继承HashMap的Entry,提供了双向链表的功能。在上述HashMap的构造器中,最后会调用init() 方法,进行相关的初始化,这个方法在HashMap的实现中并无意义,只是提供给子类实现相关的初始化调用,但在LinkedHashMap重写了 init() 方法,在调用父类的构造方法完成构造后,进一步实现了对其元素Entry的初始化操作
@Override
void init() {
header = new Entry<>(-1, null, null, null);
//双向链表的空实现
header.before = header.after = header;
}
LinkedHashMap的存储
LinkedHashMap并未重写父类HashMap的 put 方法,而是重写了父类HashMap的put方法调用的子方法void recordAccess(HashMap m) ,void addEntry(int hash, K key, V value, int bucketIndex) 和void createEntry(int hash, K key, V value, int bucketIndex),提供了自己特有的双向链接列表的实现
首先先看下HashMap的put方法
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
重写方法
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
}
void addEntry(int hash, K key, V value, int bucketIndex) {
// 调用create方法,将新元素以双向链表的的形式加入到映射中。
createEntry(hash, key, value, bucketIndex);
// 删除最近最少使用元素的策略定义
Entry<K,V> eldest = header.after;
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
} else {
if (size >= threshold)
resize(2 * table.length);
}
}
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMap.Entry<K,V> old = table[bucketIndex];
Entry<K,V> e = new Entry<K,V>(hash, key, value, old);
table[bucketIndex] = e;
// 调用元素的addBrefore方法,将元素加入到哈希、双向链接列表。
e.addBefore(header);
size++;
}
private void addBefore(Entry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}
LinkedHashMap的读取
LinkedHashMap重写了父类HashMap的get方法,实际在调用父类getEntry()方法取得查找的元素后,再判断当排序模式accessOrder为true时,记录访问顺序,将最新访问的元素添加到双向链表的表头,并从原来的位置删除。由于的链表的增加、删除操作是常量级的,故并不会带来性能的损失
public V get(Object key) {
// 调用父类HashMap的getEntry()方法,取得要查找的元素。
Entry<K,V> e = (Entry<K,V>)getEntry(key);
if (e == null)
return null;
// 记录访问顺序。
e.recordAccess(this);
return e.value;
}
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
// 如果定义了LinkedHashMap的迭代顺序为访问顺序,
// 则删除以前位置上的元素,并将最新访问的元素添加到链表表头。
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
}
private void remove() {
before.after = after;
after.before = before;
}
/**clear链表,设置header为初始状态*/
public void clear() {
super.clear();
header.before = header.after = header;
}
LinkedHashMap其他API
LinkedHashMap与HashMap的区别
LinkedHashMap | HashMap |
---|---|
有序的,有插入顺序和访问顺序 | 无序的 |
内部维护着一个运行于所有条目的双向链表 | 内部维护着一个单链表 |
LinkedHashSet是什么
LinkedHashSet的构造函数
LinkedHashSet底层使用LinkedHashMap来保存所有元素,它继承于HashSet,其所有的方法操作上又与HashSet相同,因此LinkedHashSet的实现上非常简单,只提供了四个构造方法,并通过传递一个标识参数,调用父类的构造器,底层构造一个LinkedHashMap来实现,在相关操作上与父类HashSet的操作相同,直接调用父类HashSet的方法即可
public class LinkedHashSet<E>
extends HashSet<E>
implements Set<E>, Cloneable, java.io.Serializable {
private static final long serialVersionUID = -2851667679971038690L;
/**
* 构造一个带有指定初始容量和加载因子的新空链接哈希set。
*
* 底层会调用父类的构造方法,构造一个有指定初始容量和加载因子的LinkedHashMap实例。
* @param initialCapacity 初始容量。
* @param loadFactor 加载因子。
*/
public LinkedHashSet(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor, true);
}
/**
* 构造一个带指定初始容量和默认加载因子0.75的新空链接哈希set。
*
* 底层会调用父类的构造方法,构造一个带指定初始容量和默认加载因子0.75的LinkedHashMap实例。
* @param initialCapacity 初始容量。
*/
public LinkedHashSet(int initialCapacity) {
super(initialCapacity, .75f, true);
}
/**
* 构造一个带默认初始容量16和加载因子0.75的新空链接哈希set。
*
* 底层会调用父类的构造方法,构造一个带默认初始容量16和加载因子0.75的LinkedHashMap实例。
*/
public LinkedHashSet() {
super(16, .75f, true);
}
/**
* 构造一个与指定collection中的元素相同的新链接哈希set。
*
* 底层会调用父类的构造方法,构造一个足以包含指定collection
* 中所有元素的初始容量和加载因子为0.75的LinkedHashMap实例。
* @param c 其中的元素将存放在此set中的collection。
*/
public LinkedHashSet(Collection<? extends E> c) {
super(Math.max(2*c.size(), 11), .75f, true);
addAll(c);
}
}
上面的代码都在调用super(16, .75f, true);
三个参数的方法,这个方法对应到其父类HashSet的三个参数的构造方法,我们可以通过HashSet的此构造方法中看到它是如何基于LinkedHashMap实现的
/**
* 以指定的initialCapacity和loadFactor构造一个新的空链接哈希集合。
* 此构造函数为包访问权限,不对外公开,实际只是是对LinkedHashSet的支持。
*
* 实际底层会以指定的参数构造一个空LinkedHashMap实例来实现。
* @param initialCapacity 初始容量。
* @param loadFactor 加载因子。
* @param dummy 标记。
*/
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
}
该方法为包访问权限,并未对外公开。由上述源代码可见,LinkedHashSet通过继承HashSet,底层使用LinkedHashMap,以很简单明了的方式来实现了其自身的所有功能
总结
以上就是关于 LinkedHashSet 的内容,我们只是从概述上以及构造方法这几个方面介绍了,并不是我们不想去深入其读取或者写入方法,而是其本身没有实现,只是继承于父类 HashSet 的方法
文章这么短我也没办法,我努力总结干货,是时候在这里先对前面所学到的知识总结一波,用图说话
ArrayList是什么
注意:自动增长会带来数据向新数组的重新拷贝,因此,如果可预知数据量的多少,可在构造 ArrayList 时指定其容量。在添加大量元素前,应用程序也可以使用ensureCapacity操作来增加ArrayList实例的容量,这可以减少递增式再分配的数量
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
}
ArrayList的构造函数
ArrayList 提供了三种方式的构造器
private transient Object[] elementData;
public ArrayList() {
this(10);
}
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
ArrayList的存储
1、set(int index, E element)
该方法首先调用rangeCheck(index)来校验index变量是否超出数组范围,超出则抛出异常如果没有超出,则取出原index位置的值,并且将新的element放入index位置,返回oldValue
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
2、add(E e)
该方法是将指定的元素添加到列表的尾部,当容量不足时,会调用grow方法增长容量
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
3、add(int index, E element)
在 index 位置插入 element
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
4、addAll(Collection< ? extends E> c) 和 addAll(int index, Collection< ? extends E> c)
将特定Collection中的元素添加到Arraylist末尾
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
ArrayList的读取
ArrayList 能够支持随机访问的原因也是很显然的,因为它内部的数据结构是数组,而数组本身就是支持随机访问,该方法首先会判断输入的index值是否越界,然后将数组的index位置的元素返回即可
public E get(int index) {
rangeCheck(index);
return (E) elementData[index];
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
ArrayList的删除
ArrayList 提供了根据下标或者指定对象两种方式的删除功能,需要注意点是:从数组中移除元素的操作,也会导致被移除的元素以后的所有元素的向左移动一个位置
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // Let gc do its work
return oldValue;
}
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
ArrayList调整数组容量
从上面介绍的向ArrayList中存储元素的代码中,我们看到,每当向数组中添加元素时,都要去检查添加后元素的个数是否会超出当前数组的长度,如果超出,数组将会进行扩容,以满足添加数据的需求
数组扩容有两个方法,其中开发者可以通过一个public的方法ensureCapacity(int minCapacity)来增加ArrayList的容量,而在存储元素等操作过程中,如果遇到容量不足,会调用priavte方法private void ensureCapacityInternal(int minCapacity)实现
public void ensureCapacity(int minCapacity) {
if (minCapacity > 0)
ensureCapacityInternal(minCapacity);
}
private void ensureCapacityInternal(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
从上述代码中可以看出,数组进行扩容时,会将老数组中的元素重新拷贝一份到新的数组中,每次数组容量的增长是其原容量的 1.5倍(从int newCapacity = oldCapacity + (oldCapacity >> 1)这行代码得出),这种操作的代价是很高的,因此在实际使用时,我们应该尽量避免数组容量的扩张。当我们可预知要保存的元素的多少时,要在构造 ArrayList 实例时,就指定其容量,以避免数组扩容的发生,或者根据实际需求,通过调用ensureCapacity方法来手动增加ArrayList实例的容量
ArrayListFail-Fast机制
ArrayList 也采用了快速失败的机制,通过记录modCount参数来实现,在面对并发的修改时,迭代器很快就会完全失败,而不是冒着在将来某个不确定时间发生任意不确定行为的风险。 关于Fail-Fast的介绍,可以查看我之前的HashMap的文章Java基础——HashMap详细解析及面试题解答
总结
复习一下之前所学的内容和今天所学的内容,用图说话
LinkedList是什么
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
}
LinkedList的数据结构
LinkedList是基于链表结构实现,在类中包含了first和last两个指针,表示上一个节点和下一个节点的引用,这样就构成了双向的链表
transient int size = 0;
transient Node<E> first; //链表的头指针
transient Node<E> last; //尾指针
//存储对象的结构 Node, LinkedList的内部类
private static class Node<E> {
E item;
Node<E> next; // 指向下一个节点
Node<E> prev; //指向上一个节点
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
LinkedList的存储
1、add(E e)
该方法是在链表的末尾添加元素,其调用了自己的方法linkLast(E e),linkLast(E e)将last的Node引用指向了一个新的Node(l),然后根据l新建了一个newNode,其中的元素就为要添加的e,而后,我们让 last 指向了 newNode。简单的说就是双向链表的添加操作
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
2、add(int index, E element)
该方法是在指定index位置插入元素,如果 index 位置正好等于 size,则调用linkLast(element)将其插入末尾,否则调用linkBefore(element, node(index))方法进行插入。简单的说就是双向链表的添加删除操作
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
LinkedList的其他API
这里个人经验告诉你们。当问到贪吃蛇是怎么实现的,LinkedList绝对是首选
LinkedList与ArrayList的区别
LinkedList | ArrayList |
---|---|
底层是双向链表 | 底层是可变数组 |
不允许随机访问,即查询效率低 | 允许随机访问,即查询效率高 |
插入和删除效率快 | 插入和删除效率低 |
解释一下:
总结
对目前学习到的知识进行总结,看图说话
ConcurrentHashMap是什么
为什么使用ConcurrentHashMap
我们在之前的博文中了解到关于HashMap和Hashtable这两种集合,HashMap是非线程安全的,当我们只有一个线程在使用HashMap的时候,自然不会有问题,但如果涉及到多个线程,并且有读有写的过程中,HashMap就会fail-fast。要解决HashMap同步的问题,我们的解决方案有
这两种方式基本都是对整个hash表结构加上同步锁,这样在锁表的期间,别的线程就需要等待了,无疑性能不高,所以我们引入ConcurrentHashMap,既能同步又能多线程访问
ConcurrentHashMap的数据结构
ConcurrentHashMap的数据结构为一个Segment数组,Segment的数据结构为HashEntry的数组,而HashEntry存的是我们的键值对,可以构成链表。可以简单的理解为数组里装的是HashMap
从上面的结构我们可以了解到,ConcurrentHashMap定位一个元素的过程需要进行两次Hash操作,第一次Hash定位到Segment,第二次Hash定位到元素所在的链表的头部,因此,这一种结构的带来的副作用是Hash的过程要比普通的HashMap要长,但是带来的好处是写操作的时候可以只对元素所在的Segment进行加锁即可,不会影响到其他的Segment。正是因为其内部的结构以及机制,ConcurrentHashMap在并发访问的性能上要比Hashtable和同步包装之后的HashMap的性能提高很多。在理想状态下,ConcurrentHashMap 可以支持 16 个线程执行并发写操作(如果并发级别设置为 16),及任意数量线程的读操作
ConcurrentHashMap的成员变量
ConcurrentHashMap的成员变量有
① Segment类继承于ReentrantLock类,使得Segment对象可以充当锁的角色
static final class Segment<K,V> extends ReentrantLock implements Serializable {
transient volatile HashEntry<K,V>[] table;
transient int count;
transient int modCount;
transient int threshold;
final float loadFactor;
}
Segment的成员变量意义
② HashEntry类
static final class HashEntry<K,V> {
final int hash;
final K key;
volatile V value;
final HashEntry<K,V> next;
HashEntry(int hash, K key, V value, HashEntry<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
...
...
}
可以看到HashEntry
ConcurrentHashMap的存储
在ConcurrentHashMap中,当执行put方法的时候,会需要加锁来完成,且ConcurrentHashMap不允许空值
@SuppressWarnings("unchecked")
public V put(K key, V value) {
Segment<K,V> s;
if (value == null)
throw new NullPointerException();
int hash = hash(key);
int j = (hash >>> segmentShift) & segmentMask;
if ((s = (Segment<K,V>)UNSAFE.getObject // nonvolatile; recheck
(segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment
s = ensureSegment(j);
return s.put(key, hash, value, false);
}
我们可以看到,首先有一个Segment的引用,然后会通过hash()方法对key进行计算,得到哈希值,确定元素在Segment的位置后,通过调用Segment的put()方法,将元素存储到该Segment的HashEntry数组中
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
//加锁,这里是锁定的Segment而不是整个ConcurrentHashMap
HashEntry<K,V> node = tryLock() ? null :scanAndLockForPut(key, hash, value);
V oldValue;
try {
HashEntry<K,V>[] tab = table;
//得到hash对应的table中的索引index
int index = (tab.length - 1) & hash;
//找到hash对应的是具体的哪个桶,也就是哪个HashEntry链表
HashEntry<K,V> first = entryAt(tab, index);
for (HashEntry<K,V> e = first;;) {
if (e != null) {
K k;
if ((k = e.key) == key ||
(e.hash == hash && key.equals(k))) {
oldValue = e.value;
if (!onlyIfAbsent) {
e.value = value;
++modCount;
}
break;
}
e = e.next;
}
else {
if (node != null)
node.setNext(first);
else
node = new HashEntry<K,V>(hash, key, value, first);
int c = count + 1;
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
rehash(node);
else
setEntryAt(tab, index, node);
++modCount;
count = c;
oldValue = null;
break;
}
}
} finally {
//解锁
unlock();
}
return oldValue;
}
需要注意的是
加锁操作是针对的 hash 值对应的某个Segment,而不是整个ConcurrentHashMap,因为put操作只是在这个Segment中完成,所以并不需要对整个ConcurrentHashMap加锁。此时,其他的线程也可以对另外的Segment进行put操作,因为虽然该Segment被锁住了,但其他的Segment并没有加锁。
ConcurrentHashMap的读取
ConcurrentHashMap中的读方法不需要加锁,所有的修改操作在进行结构修改时都会在最后一步写count 变量,通过这种机制保证get操作能够得到几乎最新的结构更新
V get(Object key, int hash) {
if(count != 0) { // 首先读 count 变量
HashEntry<K,V> e = getFirst(hash);
while(e != null) {
if(e.hash == hash && key.equals(e.key)) {
V v = e.value;
if(v != null)
return v;
// 如果读到 value 域为 null,说明发生了重排序,加锁后重新读取
return readValueUnderLock(e);
}
e = e.next;
}
}
return null;
}
ConcurrentHashMap 的高并发性主要来自于三个方面:
ConcurrentHashMap与HashTable最大的区别
总结
对目前学习到的知识进行总结,看图说话
Vector是什么
- Vector是基于可变数组的List接口的同步实现
- Vector是有序的
- Vector允许null键和null值
- Vector已经不建议使用了
public class Vector<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
}
- 1
- 2
- 3
- 4
- 5
- Vector实现了List接口、底层使用数组保存所有元素,其操作基本上是对数组的操作
- Vector继承了AbstractList抽象类,它是一个数组队列,提供了相关的添加、删除、修改、遍历等功能
- Vector实现了RandmoAccess接口,即提供了随机访问功能,RandmoAccess是java中用来被List实现,为List提供快速访问功能的,我们可以通过元素的序号快速获取元素对象,这就是快速随机访问
- Vector实现了Cloneable接口,即覆盖了函数clone(),能被克隆
- Vector实现了java.io.Serializable接口,意味着ArrayList支持序列化
Vector的成员变量
// 保存Vector中数据的数组
protected Object[] elementData;
// 实际数据的数量
protected int elementCount;
// 容量增长系数
protected int capacityIncrement;
// Vector的序列版本号
private static final long serialVersionUID = -2767605614048989439L;
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
Vector的构造方法
Vector共有4个构造函数
- Vector():默认构造函数
- Vector(int capacity):capacity是Vector的默认容量大小,当由于增加数据导致容量增加时,每次容量会增加一倍
- Vector(int capacity, int capacityIncrement):capacity是Vector的默认容量大小,capacityIncrement是每次Vector容量增加时的增量值
- Vector(Collection< ? extends E> collection):创建一个包含collection的Vector
// Vector构造函数。默认容量是10。
public Vector() {
this(10);
}
// 指定Vector容量大小的构造函数
public Vector(int initialCapacity) {
this(initialCapacity, 0);
}
// 指定Vector"容量大小"和"增长系数"的构造函数
public Vector(int initialCapacity, int capacityIncrement) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
// 新建一个数组,数组容量是initialCapacity
this.elementData = new Object[initialCapacity];
// 设置容量增长系数
this.capacityIncrement = capacityIncrement;
}
// 指定集合的Vector构造函数。
public Vector(Collection<? extends E> c) {
// 获取“集合(c)”的数组,并将其赋值给elementData
elementData = c.toArray();
// 设置数组长度
elementCount = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
Vector的存储
1、setElementAt(E obj, int index)或add(int index, E element)
更新index位置元素,此方法无返回值
public synchronized void setElementAt(E obj, int index) {
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index + " >= " +
elementCount);
}
elementData[index] = obj;
}
//另一种写法
public void add(int index, E element) {
insertElementAt(element, index);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
2、set(int index, E element)
更新index位置元素,此方法返回index位置上的旧值
public synchronized E set(int index, E element) {
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
3、add(E e)或addElement(E obj)
尾部添加元素
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
public synchronized void addElement(E obj) {
modCount++;
ensureCapacityHelper(elementCount + 1); // 确保可以插入元素,当到达最大容量,进行扩容
elementData[elementCount++] = obj;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
4、insertElementAt(E obj, int index)
index位置插入元素 o
public synchronized void insertElementAt(E obj, int index) {
modCount++;
if (index > elementCount) { // 越界
throw new ArrayIndexOutOfBoundsException(index
+ " > " + elementCount);
}
ensureCapacityHelper(elementCount + 1); // 确保可以插入元素
// index - elementCount 之间的元素 后移一位
System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
elementData[index] = obj; // 插入元素
elementCount++; // 元素个数 + 1
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
Vector的获取
1、firstElement()
获取第一个元素
public synchronized E firstElement() {
if (elementCount == 0) {
throw new NoSuchElementException();
}
return elementData(0);
}
- 1
- 2
- 3
- 4
- 5
- 6
2、lastElement()
获取最后一个元素
public synchronized E lastElement() {
if (elementCount == 0) {
throw new NoSuchElementException();
}
return elementData(elementCount - 1);
}
- 1
- 2
- 3
- 4
- 5
- 6
3、elementData(int index)或get(int index)
获取index位置元素,两个方式最大区别于是否抛出异常
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
//另一种方式
public synchronized E get(int index) {
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
return elementData(index);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
Vector的删除
1、remove(int index)或removeElementAt(int index)
删除index位置元素,两种方式区别于有无返回值
public synchronized E remove(int index) {
modCount++;
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
E oldValue = elementData(index);
int numMoved = elementCount - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--elementCount] = null; // Let gc do its work
return oldValue;
}
//另一种方式
public synchronized void removeElementAt(int index) {
modCount++;
if (index >= elementCount) { // 越界
throw new ArrayIndexOutOfBoundsException(index + " >= " +
elementCount);
}
else if (index < 0) { // 越界
throw new ArrayIndexOutOfBoundsException(index);
}
int j = elementCount - index - 1; // 需要移动元素个数
if (j > 0) { // elementData数组,从index+1开始复制j个元素,到该数组的index开始位置
System.arraycopy(elementData, index + 1, elementData, index, j);
}
elementCount--; // 元素个数-1
elementData[elementCount] = null; // 空,有利于垃圾回收
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
2、removeElement(Object obj)或remove(Object o)
删除元素obj
public synchronized boolean removeElement(Object obj) {
modCount++;
int i = indexOf(obj);
if (i >= 0) {
removeElementAt(i);
return true;
}
return false;
}
//另一种方式
public boolean remove(Object o) {
return removeElement(o);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
3、removeAllElements()
删除所有元素
public synchronized void removeAllElements() {
modCount++;
// Let gc do its work
for (int i = 0; i < elementCount; i++)
elementData[i] = null;
elementCount = 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
Vector调整数组容量
数组扩容有两个方法,其中开发者可以通过一个public的方法ensureCapacity(int minCapacity)来增加Vector的容量,而在存储元素等操作过程中,如果遇到容量不足,会调用priavte方法private void ensureCapacityHelper(int minCapacity)实现,且每次数组容量的增长是其原容量的2倍
public synchronized void ensureCapacity(int minCapacity) {
if (minCapacity > 0) {
modCount++;
ensureCapacityHelper(minCapacity);//是否需要增加容量
}
}
private void ensureCapacityHelper(int minCapacity) {
// overflow-conscious code
if (minCapacity - elementData.length > 0)// true 增加容量
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
Vector的遍历方式
- 通过迭代器遍历,即通过Iterator去遍历
- 随机访问,通过索引值去遍历
- Enumeration遍历
Vector和ArrayList的区别
Vector | ArrayList |
---|---|
同步、线程安全的 | 异步、线程不安全 |
需要额外开销来维持同步锁,性能慢 | 性能快 |
可以使用Iterator、foreach、Enumeration输出 | 只能使用Iterator、foreach输出 |
总结
复习一下之前所学的内容和今天所学的内容,用图说话
1、TreeMap和HashMap
TreeMap | HashMap |
---|---|
有序的 | 无序的 |
不允许null | 允许null |
实现Comparable接口 | 不实现Comparable接口 |
底层是红黑二叉树,线程不同步 | 底层是哈希表,线程不同步 |
2、TreeSet和HashSet
TreeSet | HashSet |
---|---|
有序的 | 无序的 |
不允许null | 允许null |
底层是红黑二叉树,线程不同步 | 底层是哈希表,线程不同步 |
TreeSet是通过TreeMap实现的,用的只是Map的key | HashSet是通过HashMap实现的,用的只是Map的key |
3、Collection和Collections
- Collection:是一个集合接口,它提供了对集合对象进行基本操作的通用接口方法
- Collections:是一个集合的工具类,它包含有各种有关集合操作的静态方法
4、hashCode和equals
equals相等,hashCode必相等;hashCode相等,equals不一定相等
**注意**:对于需要大量并且快速的对比的话如果都用equals()去做显然效率太低,所以解决方式是,每当需要对比的时候,首先用hashCode()去对比,如果hashCode()不一样,则表示这两个对象肯定不相等(也就是不必再用equals()去再对比了),如果hashCode()相同,此时再对比他们的equasl(),如果equal()也相同,则表示这两个对象是真的相同了,这样既能大大提高了效率也保证了对比的绝对正确性!
5、equals和==的区别
(1)==: 比较的是变量(栈)内存中存放的对象的(堆)内存地址,用来判断两个对象的地址是否相同,即是否是指相同一个对象。比较的是真正意义上的指针操作。
(2)equals:用来比较的是两个对象的内容是否相等,由于所有的类都是继承自java.lang.Object类的,所以适用于所有对象,如果没有对该方法进行覆盖的话,调用的仍然是Object类中的方法,而Object中的equals方法返回的却是==的判断。String、Integer等类对equals进行了重写。
错误相关面试题
1、Error和Exception
Error类和Exception类的父类都是throwable类
- Error:一般指与虚拟机相关的问题,如系统崩溃,虚拟机错误,内存空间不足,方法调用栈溢等。对于这类错误导致的应用程序中断,仅靠程序本身无法恢复和和预防,遇到这样的错误,建议让程序终止
- Exception:表示程序可以处理的异常,可以捕获且可能恢复。遇到这类异常,应该尽可能处理异常,使程序恢复运行,而不应该随意终止异常
2、Unchecked Exception和Checked Exception
1、Unchecked Exception
- 指的是不可被控制的异常,或称运行时异常,主要体现在程序的瑕疵或逻辑错误,并且在运行时无法恢复
- 包括Error与RuntimeException及其子类,如:OutOfMemoryError,IllegalArgumentException, NullPointerException,IllegalStateException,IndexOutOfBoundsException等
- 语法上不需要声明抛出异常也可以编译通过
2、Checked Exception
- 指的是可被控制的异常,或称非运行时异常
- 除了Error和RuntimeException及其子类之外,如:ClassNotFoundException, NamingException, ServletException, SQLException, IOException等
- 需要try catch处理或throws声明抛出异常
数据相关面试题
1、xml解析方式
- Dom解析:将XML文件的所有内容读取到内存中(内存的消耗比较大),然后允许您使用DOM API遍历XML树、检索所需的数据
- Sax解析:Sax是一个解析速度快并且占用内存少的xml解析器,Sax解析XML文件采用的是事件驱动,它并不需要解析完整个文档,而是按内容顺序解析文档的过程
- Pull解析:Pull解析器的运行方式与 Sax 解析器相似。它提供了类似的事件,可以使用一个switch对感兴趣的事件进行处理
详细可见我的博客:Android基础——XML数据的三种解析方式
Android基础——XML数据的三种解析方式
本篇文章包含以下内容:
- XML数据的Dom解析
- XML数据的Sax解析
- XML数据的Pull解析
- Activity中使用三种解析
- Sax解析与Pull解析区别
三种解析方式的步骤:
- 在Assets文件夹中模拟创建XML数据
- 创建对应XML的Bean对象
- 开始解析
XML数据的Dom解析
DOM解析XML文件时,会将XML文件的所有内容读取到内存中(内存的消耗比较大),然后允许您使用DOM API遍历XML树、检索所需的数据
一、在Assets文件夹中模拟创建XML文件
<students>
<student>
<name sex="man">小明</name>
<nickName>明明</nickName>
</student>
<student>
<name sex="woman">小红</name>
<nickName>红红</nickName>
</student>
<student>
<name sex="man">小亮</name>
<nickName>亮亮</nickName>
</student>
</students>
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
二、创建对应XML的Bean对象
public class Student {
private String name;
private String sex;
private String nickName;
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String getSex() {
return sex;
}
public void setSex(String sex) {
this.sex = sex;
}
public String getNickName() {
return nickName;
}
public void setNickName(String nickName) {
this.nickName = nickName;
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
", sex='" + sex + '\'' +
", nickName='" + nickName + '\'' +
'}';
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
三、Dom解析
public List<Student> dom2xml(InputStream is) throws Exception {
//一系列的初始化
List<Student> list = new ArrayList<>();
DocumentBuilderFactory factory = DocumentBuilderFactory.newInstance();
DocumentBuilder builder = factory.newDocumentBuilder();
//获得Document对象
Document document = builder.parse(is);
//获得student的List
NodeList studentList = document.getElementsByTagName("student");
//遍历student标签
for (int i = 0; i < studentList.getLength(); i++) {
//获得student标签
Node node_student = studentList.item(i);
//获得student标签里面的标签
NodeList childNodes = node_student.getChildNodes();
//新建student对象
Student student = new Student();
//遍历student标签里面的标签
for (int j = 0; j < childNodes.getLength(); j++) {
//获得name和nickName标签
Node childNode = childNodes.item(j);
//判断是name还是nickName
if ("name".equals(childNode.getNodeName())) {
String name = childNode.getTextContent();
student.setName(name);
//获取name的属性
NamedNodeMap nnm = childNode.getAttributes();
//获取sex属性,由于只有一个属性,所以取0
Node n = nnm.item(0);
student.setSex(n.getTextContent());
} else if ("nickName".equals(childNode.getNodeName())) {
String nickName = childNode.getTextContent();
student.setNickName(nickName);
}
}
//加到List中
list.add(student);
}
return list;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
XML数据的Sax解析
SAX是一个解析速度快并且占用内存少的xml解析器,SAX解析XML文件采用的是事件驱动,它并不需要解析完整个文档,而是按内容顺序解析文档的过程
由于前面一和二的步骤是一样的,这里就省略了
三、Sax解析
public List<Student> sax2xml(InputStream is) throws Exception {
SAXParserFactory spf = SAXParserFactory.newInstance();
//初始化Sax解析器
SAXParser sp = spf.newSAXParser();
//新建解析处理器
MyHandler handler = new MyHandler();
//将解析交给处理器
sp.parse(is, handler);
//返回List
return handler.getList();
}
public class MyHandler extends DefaultHandler {
private List<Student> list;
private Student student;
//用于存储读取的临时变量
private String tempString;
/**
* 解析到文档开始调用,一般做初始化操作
*
* @throws SAXException
*/
@Override
public void startDocument() throws SAXException {
list = new ArrayList<>();
super.startDocument();
}
/**
* 解析到文档末尾调用,一般做回收操作
*
* @throws SAXException
*/
@Override
public void endDocument() throws SAXException {
super.endDocument();
}
/**
* 每读到一个元素就调用该方法
*
* @param uri
* @param localName
* @param qName
* @param attributes
* @throws SAXException
*/
@Override
public void startElement(String uri, String localName, String qName, Attributes attributes) throws SAXException {
if ("student".equals(qName)) {
//读到student标签
student = new Student();
} else if ("name".equals(qName)) {
//获取name里面的属性
String sex = attributes.getValue("sex");
student.setSex(sex);
}
super.startElement(uri, localName, qName, attributes);
}
/**
* 读到元素的结尾调用
*
* @param uri
* @param localName
* @param qName
* @throws SAXException
*/
@Override
public void endElement(String uri, String localName, String qName) throws SAXException {
if ("student".equals(qName)) {
list.add(student);
}
if ("name".equals(qName)) {
student.setName(tempString);
} else if ("nickName".equals(qName)) {
student.setNickName(tempString);
}
super.endElement(uri, localName, qName);
}
/**
* 读到属性内容调用
*
* @param ch
* @param start
* @param length
* @throws SAXException
*/
@Override
public void characters(char[] ch, int start, int length) throws SAXException {
tempString = new String(ch, start, length);
super.characters(ch, start, length);
}
/**
* 获取该List
*
* @return
*/
public List<Student> getList() {
return list;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
XML数据的Pull解析
Pull解析器的运行方式与 SAX 解析器相似。它提供了类似的事件,可以使用一个switch对感兴趣的事件进行处理
三、Pull解析
public List<Student> pull2xml(InputStream is) throws Exception {
List<Student> list = null;
Student student = null;
//创建xmlPull解析器
XmlPullParser parser = Xml.newPullParser();
///初始化xmlPull解析器
parser.setInput(is, "utf-8");
//读取文件的类型
int type = parser.getEventType();
//无限判断文件类型进行读取
while (type != XmlPullParser.END_DOCUMENT) {
switch (type) {
//开始标签
case XmlPullParser.START_TAG:
if ("students".equals(parser.getName())) {
list = new ArrayList<>();
} else if ("student".equals(parser.getName())) {
student = new Student();
} else if ("name".equals(parser.getName())) {
//获取sex属性
String sex = parser.getAttributeValue(null,"sex");
student.setSex(sex);
//获取name值
String name = parser.nextText();
student.setName(name);
} else if ("nickName".equals(parser.getName())) {
//获取nickName值
String nickName = parser.nextText();
student.setNickName(nickName);
}
break;
//结束标签
case XmlPullParser.END_TAG:
if ("student".equals(parser.getName())) {
list.add(student);
}
break;
}
//继续往下读取标签类型
type = parser.next();
}
return list;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
Activity中使用三种解析
public class XmlActivity extends AppCompatActivity implements View.OnClickListener {
private TextView tv;
private Button bt_dom, bt_sax, bt_pull;
private XmlUtils xmlUtils;
private List<Student> students;
@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_xml);
tv = (TextView) findViewById(R.id.tv);
bt_dom = (Button) findViewById(R.id.bt_dom);
bt_sax = (Button) findViewById(R.id.bt_sax);
bt_pull = (Button) findViewById(R.id.bt_pull);
bt_dom.setOnClickListener(this);
bt_sax.setOnClickListener(this);
bt_pull.setOnClickListener(this);
xmlUtils = new XmlUtils();
}
@Override
public void onClick(View v) {
switch (v.getId()) {
case R.id.bt_dom:
try {
students = xmlUtils.dom2xml(getResources().getAssets().open("student.xml"));
tv.setText(students.toString());
} catch (Exception e) {
e.printStackTrace();
}
break;
case R.id.bt_sax:
try {
students = xmlUtils.sax2xml(getResources().getAssets().open("student.xml"));
tv.setText(students.toString());
} catch (Exception e) {
e.printStackTrace();
}
break;
case R.id.bt_pull:
try {
students = xmlUtils.pull2xml(getResources().getAssets().open("student.xml"));
tv.setText(students.toString());
} catch (Exception e) {
e.printStackTrace();
}
break;
}
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
三种解析方式的效果图是一样的
Sax解析与Pull解析区别
SAX和Pull的区别:SAX解析器的工作方式是自动将事件推入事件处理器进行处理,因此你不能控制事件的处理主动结束;而Pull解析器的工作方式为允许你的应用程序代码主动从解析器中获取事件,正因为是主动获取事件,因此可以在满足了需要的条件后不再获取事件,结束解析。
源码下载
线程相关面试题
1、线程实现的方式
继承Thread类、实现Runnable接口、使用ExecutorService、Callable、Future实现有返回结果的线程
2、如何停止一个线程
- 创建一个标识(flag),当线程完成你所需要的工作后,可以将标识设置为退出标识
- 使用Thread的stop()方法,这种方法可以强行停止线程,不过已经过期了,因为其在停止的时候可能会导致数据的紊乱
- 使用Thread的interrupt()方法和Thread的interrupted()方法,两者配合break退出循环,或者return来停止线程,有点类似标识(flag)
- (推荐)当我们想要停止线程的时候,可以使用try-catch语句,在try-catch语句中抛出异常,强行停止线程进入catch语句,这种方法可以将错误向上抛,使线程停止事件得以传播
3、线程的状态转换
1、新建(new):创建了一个线程对象
2、可运行(runnable):线程对象创建后,线程调用start()方法。该状态的线程位于可运行线程池中,等待被线程调度选中,获取cpu的使用权
3、运行(running):可运行状态(runnable)的线程获得了cpu使用权,执行程序代码
4、阻塞(block):线程因为某种原因放弃了cpu使用权,即让出了cpu使用权,暂时停止运行,直到线程进入可运行(runnable)状态,才有机会再次获得cpu使用权转到运行(running)状态。阻塞的情况分三种:
- 等待阻塞:运行(running)的线程执行o.wait()方法,JVM会把该线程放入等待队列(waitting queue)中
- 同步阻塞:运行(running)的线程在获取对象的同步锁时,若该同步锁被别的线程占用,则JVM会把该线程放入锁池(lock pool)中
- 其他阻塞:运行(running)的线程执行Thread.sleep(long ms)或t.join()方法,或者发出了I/O请求时,JVM会把该线程置为阻塞状态。当sleep()状态超时、join()等待线程终止或者超时、或者I/O处理完毕时,线程重新转入可运行(runnable)状态
5、死亡(dead):线程run()、main() 方法执行结束,或者因异常退出了run()方法,则该线程结束生命周期,且死亡的线程不可再次复生
4、什么是线程安全
在多线程访问同一代码的时候,不会出现不确定的结果
5、如何保证线程安全
- 对非安全的代码进行加锁操作
- 使用线程安全的类
- 不要跨线程访问共享变量
- 使用final类型作为共享变量
- 对共享变量加锁操作
6、Synchronized如何使用
Synchronized是Java的关键字,是一种同步锁,它可以修饰的对象有以下几种
- 修饰代码块:该代码块被称为同步代码块,作用的主要对象是调用这个代码块的对象
- 修饰方法:该方法称为同步方法,作用的主要对象是调用这个方法的对象
- 修饰静态方法:作用范围为整个静态方法,作用的主要对象为这个类的所有对象
- 修饰类:作用范围为Synchronized后面括号括起来的部分,作用的主要对象为这个类的所有对象
7、Synchronized和Lock的区别
相同点:Lock能完成Synchronized所实现的所有功能
不同点:
- Synchronized是基于JVM的同步锁,JVM会帮我们自动释放锁。Lock是通过代码实现的,Lock要求我们手工释放,必须在finally语句中释放。
- Lock锁的范围有局限性、块范围。Synchronized可以锁块、对象、类
- Lock功能比Synchronized强大,可以通过tryLock方法在非阻塞线程的情况下拿到锁
8、多线程的等待唤醒主要方法
- void notify():唤醒在此对象监视器上等待的单个线程
- void notifyAll():唤醒在此对象监视器上等待的所有线程
- void wait():导致当前的线程等待,直到其他线程调用此对象的notify()方法或notifyAll()方法
- void wait(long timeout):导致当前的线程等待,直到其他线程调用此对象的notify()方法或notifyAll()方法,或者超过指定的时间量
- void wait(long timeout, int nanos):导致当前的线程等待,直到其他线程调用此对象的notify()方法或notifyAll()方法,或者其他某个线程中断当前线程,或者已超过某个实际时间量
9、sleep和wait的区别
sleep() | wait() |
---|---|
是Thread类的方法 | 是Object类中的方法 |
调用sleep(),在指定的时间里,暂停程序的执行,让出CPU给其他线程,当超过时间的限制后,又重新恢复到运行状态,在这个过程中,线程不会释放对象锁 | 调用wait()时,线程会释放对象锁,进入此对象的等待锁池中,只有此对象调用notify()时,线程进入运行状态 |
10、多线程中的死锁
死锁:指两个或两个以上的线程在执行的过程中,因抢夺资源而造成互相等待,导致线程无法进行下去
产生死锁的4个必要条件
- 循环等待:线程中必须有循环等待
- 不可剥夺:线程已获得资源,再未使用完成之前,不可被剥夺抢占
- 资源独占:线程在某一时间内独占资源
- 申请保持:线程因申请资源而阻塞,对已获得的资源保持不放
11、什么叫守护线程,用什么方法实现守护线程
守护线程:指为其他线程的运行提供服务的线程,可通过setDaemon(boolean on)方法设置线程的Daemon模式,true为守护模式,false为用户模式
12、Java中的BIO,NIO,AIO分别是什么,应用场景是什么
- BIO:同步并阻塞,服务器实现模式是一个连接对应一个线程,即客户端有连接请求时,服务器就会开启一个线程进行处理,如果这个连接不做任何事情时,会造成不必要的线程开销,可以使用线程池进行改善。其应用场景适用于连接数目比较小且固定的架构,这种方式对服务器资源要求较高,对线程并发有局限性
- NIO:同步非阻塞,服务器实现模式是一个请求对应一个线程,即客户端的连接请求都会注册在多路复用器上,当多路复用器轮询到有I/O请求时才启动一个线程进行处理。其应用场景适用于连接数目多且连接短的架构,对线程并发有局限性
- AIO:异步非阻塞,服务器实现模式是一个有效请求对应一个线程,即客户端的I/O请求完成之后,再通知服务器去启动一个线程进行处理。其应用场景适用于连接数目多且连接长的架构,充分体现出并发性
13、Java中的IO和NIO的区别
- IO是面向流的,NIO是面向缓冲区的
- IO的各种流是阻塞的,NIO是非阻塞模式
14、volatile关键字
用volatile修饰的变量,线程在每次使用变量的时候,都会读取变量修改后的值,可以简单的理解为volatile修饰的变量保存的是变量的地址。volatile变量具有synchronized的可见性特性,但是不具备原子特性。可见性指的是在确保释放锁之前,对共享数据做出的更改,可以在随后获得该锁的另一个线程中是可见的。要使volatile变量提供理想的线程安全,必须同时满足下面两个条件
- 对变量的写操作不依赖于当前值
- 该变量没有包含在具有其他变量的不变式中
比如增量操作(x++)看上去类似一个单独操作,实际上它是一个由读取-修改-写入操作序列组成的组合操作,必须以原子方式执行,而volatile不能提供必须的原子特性。实现正确的操作需要使 x 的值在操作期间保持不变,而 volatile 变量无法实现这点
反射相关面试题
1、什么是反射
在运行状态中,对于任意一个类,都可以获得这个类的所有属性和方法,对于任意一个对象,都能够调用它的任意一个方法和属性
2、反射使用步骤
- 获取类的字节码(getClass()、forName()、类名.class)
- 根据类的方法名或变量名,获取类的方法或变量
- 执行类的方法或使用变量,如果不使用,也可以创建该类的实例对象(通过获取构造函数执行newInstance方法)
进程相关面试题
1、进程的优先级
优先级从低到高排列,优先级最高的进程,最先获取资源,最后释放
1、空进程
这是Android系统优先杀死的,因为此时该进程已经没有任何用途
2、后台进程
包含不可见的Activity,即跳转到其他Activity后,由于资源不足,系统会将原来的Activity杀死(即跳转的来源)
3、服务进程
即Service,当系统资源不足时,系统可能会杀掉正在执行任务的Service,因此在Service执行比较耗时的操作,并不能保证一定能执行完毕
4、可见进程
当前屏幕上可以看到的Activity,例如显示一个对话框的Activity,那么对话框变成了前台进程,而调用他的Activity是可见进程,但并不是前台的
5、前台进程
当前处于最前端的Activity,也就是Android最后考虑杀死的对象,一般来说,前台进程Android系统是不会杀死的,只有当前4个都杀掉资源依旧不够才可能会发生
2、IPC机制
类加载器相关面试题
1、什么是类加载器
ClassLoader是用来动态加载class文件到内存中
2、类加载器类型
- App ClassLoader(应用类加载器或系统加载器):这个加载器使用java实现,使用广泛,负责加载classPath中指定的类。具体的使用场合,在加载classPath中指定的而扩展类加载器没有加载的类,若扩展类加载器加载了classPath中的类,则系统类加载器则没有机会加载。用户定义的类一般都是系统类加载器加载的。可以通过:ClassLoader.getSystemClassLoader()获得
- Extension ClassLoader(扩展类加载器):它负责加载Java的标准扩展,一般使用Java实现的,负责加载jre/lib/ext中的类。和普通的类加载器一样。可以通过:ClassLoader.getSystemClassLoader().getParent()获得
- BootStrap ClassLoader(引导类加载器):纯C++实现的加载器,没有对应的Java类,它负责加载jdk中jre/lib目录下的系统核心库。对于java程序无法获得它,像上文中获得扩展类加载器的父类加载器是null。像String,Integer,Double类都是由引导类加载器加载的
3、双亲委托模型(父委托加载机制)
当加载一个类时,首先会判断当前类是否已经被加载,如果被加载直接返回当前类加载器,如果没有被加载,则把机会让给父类,先让父类加载,若是父类中不能加载,则会去找到Bootstrap加载器,如果Bootstrap加载器加载失败,则会退回上层,自己通过findClass自己去加载对应的路径(这是孝顺型的,先想到父类,但是他们不是通过继承来实现的)
具体实现代码在ClassLoader类中的loadClass方法中,API19和API24加载过程有少许区别(以下是API24的源码),但大部分是一致的,下面执行的逻辑与我们上面所说的一致
protected Class<?> loadClass(String name, boolean resolve)
throws ClassNotFoundException
{
//首先会判断当前类是否已经被加载
Class c = findLoadedClass(name);
if (c == null) {
long t0 = System.nanoTime();
try {
if (parent != null) {
//把机会让给父类,先让父类加载
c = parent.loadClass(name, false);
} else {
//如果父类无法加载,则会去找Bootstrap加载器
c = findBootstrapClassOrNull(name);
}
} catch (ClassNotFoundException e) {
}
if (c == null) {
long t1 = System.nanoTime();
//如果前面的都加载失败,则调用findClass用自己的加载器加载
c = findClass(name);
}
}
return c;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
优点:
- 父委托机制会先去加载系统自带的class,而不会去加载我们自定义的高仿的系统class(比如ArrayList),可以保证我们的程序的安全而不会被恶意注入
4、类加载过程
- 加载:将类的信息从文件中获取并且载入到JVM内存中
- 验证:检查读入的结构是否符合JVM规范的描述
- 准备:分配一个结构用来存储类信息
- 解析:把这个类的常量池的所有符号引用改变成直接引用
- 初始化:执行静态初始化程序、类构造器方法的过程
5、自定义类加载器
public class MyClassLoader extends DexClassLoader {
public MyClassLoader(String dexPath, String optimizedDirectory, String librarySearchPath, ClassLoader parent) {
super(dexPath, optimizedDirectory, librarySearchPath, parent);
}
@Override
protected Class<?> findClass(String name) throws ClassNotFoundException {
byte[] classData = getClassData(name);
if (classData != null) {
return defineClass(name, classData, 0, classData.length);
} else {
throw new ClassNotFoundException();
}
}
/**
* 读取文件的字节数组
*
* @param name
* @return
*/
private byte[] getClassData(String name) {
try {
InputStream inputStream = new FileInputStream(name);
ByteArrayOutputStream baos = new ByteArrayOutputStream();
int buffSize = 4096;
byte[] buffer = new byte[buffSize];
int bytesRead = -1;
while ((bytesRead = inputStream.read(buffer)) != -1) {
baos.write(buffer, 0, bytesRead);
}
return baos.toByteArray();
} catch (Exception e) {
e.printStackTrace();
}
return null;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
6、类加载主要方法的区别
- findClass():查找指定路径下的class文件
- loadClass():加载class字节码文件
- defineClass():将字节数组流转换成字节码
易错题
1、静态代码块、构造代码块、构造方法的执行顺序
class Fu{
static {
System.out.println("父静态代码块");
}
{
System.out.println("父代码块");
}
public Fu(){
System.out.println("父构造函数");
}
}
class Zi extends Fu{
static {
System.out.println("子静态代码块");
}
{
System.out.println("子代码块");
}
public Zi(){
System.out.println("子构造函数");
}
}
public class Text{
public static void main(String[] args) {
Zi zi = new Zi();
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
输出结果
父静态代码块
子静态代码块
父代码块
父构造函数
子代码块
子构造函数
- 1
- 2
- 3
- 4
- 5
- 6
上一篇: Java匿名内部类访问的局部变量为什么必须要用final修饰
下一篇: springboot快速入门