Java集合
Java集合框架概述
一方面,面对对象语言对事物的体现都是以对象的形式,为了方便对多个对象的操作,就要对对象进行存储。另一方面,使用Array存储对象方面具有一些弊端,而Java集合就像一种容器,可以动态地把多个对象的引用放入容器中
- 数组在内存存储方面的特点:
- 数组初始化以后,长度就确定了
- 数组声明的类型,就决定了进行元素初始化时的类型
- 数组在存储数据方面的弊端
- 数组初始化以后,长度就不可变了,不便于扩展
- 数组中提供的属性和方法少,不便于进行添加、删除、插入等操作,且效率不高。同时无法直接获取存储元素的格式
- 数组存储的数据是有序的、可以重复的,对于无序、不可重复的需求,不能满足。====> 存储数据的特点单一
- 数组在内存存储方面的特点:
Java集合类可以用于存储数量不等的多个对象,还可以用于保存具有映射关系的关联数组
集合、数组都是对多个数据进行存储操作的结构,简称Java容器
- 此时的存储,主要指的是内存层面的存储,不涉及到持久化的存储(.txt,.jpg,.数据库中)
集合可分为Collection和Map两种体系
- Collection接口:单列数据,定义了存取一组对象的方法的集合
- List:元素有序、可重复的集合
- Set:元素无序、不可重复的集合
- Map接口:双列数据,保存具有映射关系“key-value对”的集合
- Collection接口:单列数据,定义了存取一组对象的方法的集合
集合框架
Collection接口
单列集合,用来存储一个一个的对象
List接口
有序的可重复的数据 ====> “动态”数组
ArrayList、LinkedList、Vector
Set接口
- 无序的不可重复的数据 ====> 高中讲得“集合”
- HashSet、LinkHashSet、TreeSet
Map接口
双列接口,用来存储一对一对(key - value)的数据 ====> 高中函数: y = f(x) : x => key,y => value
HashMap、LinkedHashMap、TreeMap、Hashtable、Properties
Collection接口中的方法的使用
- 添加
- add(Object o)
- addAll(Collection coll)
- 获取有效元素的个数
- int size()
- 清空集合
- void clear()
- 是否是空集合
- boolean isEmpty()
- 是否包含某个元素
- boolean contains(Object obj):是通过元素的equals方法来判断是否是同一个对象
- boolean containsAll(Collection c):也是调用元素的equals方法来比较的。拿两个集合的元素挨个比较
- 删除
- boolean remove(Object o):通过元素的equals方法判断是否是要删除的那个元素。只会删除找到的第一个元素
- boolean removeAll(Collection coll):取当前集合的差集
- 去两个集合的交集
- boolean retainAll(Collection c):把交集的结果存在当前集合中,不影响c
- 集合是否相等
- boolean equals(Object o)
- 转成对象数组
- Object[] toArray()
- 获取集合对象的哈希值
- hashCode()
- 遍历
- iterator():返回迭代器对象,用于集合遍历
1 | package Intermediate.framework; |
1 | package Intermediate.framework; |
Iterator迭代器接口
使用Iterator接口遍历集合元素
- Iterator对象称为迭代器(设计模式的一种),主要用于遍历遍历Collection集合中的元素,不包括Map接口
- GOF给迭代器模式的定义为:提供一种方法访问一个容器(Container)对象中各个元素,而又不需暴露该对象的内部细节。迭代器模式,就是为容器而生。类似于“公交车上的售票员”、“火车上的乘务员”、“空姐”
- Collection接口继承了java.lang.Iterable接口,该接口有一个iterator()方法,那么所有实现了Collection接口的集合类都有一个iterator()方法,用以返回一个实现了Iterator接口的对象
- Iterator仅用于遍历集合,Iterator本身并不提供承装对象的能力。如果需要创建Iterator对象,则必须有一个被迭代的集合
- 集合对象每次调用iterator()方法都得到一个全新的迭代器对象,默认游标都在集合的第一个元素之前
Iterator接口的方法
- 在调用it.next()方法之前必须要调用it.hasNext()进行检测。若不调用,且下一条记录无效,直接调用it.next()会抛出noSuchElementException异常
迭代器的执行原理
1 | //hasNext():判断是否还有下一个元素 |
Iterator遍历集合的两种错误写法
1 | Iterator iterator = coll.iterator(); |
1 | //每次都会输出下标1 |
Iterator迭代器remove()方法的使用
Iterator可以删除集合的元素,但是是遍历过程中通过迭代器对象的remove方法,不是集合对象的remove’方法
如果还未调用next()方法或再上一次调用next()方法之后已经调用了remove()方法,再调用remove()方法都会报IllegalStateExceotion错误(向删除但是游标并没有指向对象)
内部顶一个remove()方法,可以在遍历的时候,删除集合中的元素。此方法不同于集合直接调用remove()
1 | public void test2(){ |
使用foreach循环遍历集合元素
- Java5.0提供了foreach循环迭代访问Collection和数组
- 遍历操作不许获取Collection或数组的长度,无需使用索引访问元素
- 遍历集合的底层调用Iterator完成操作
- foreach还可以用来遍历数组
- foreach内更改数据不会改变原数组,因为相当于将原数组赋给新的局部变量遍历,不是原数组
Collection子接口之一:List接口
List接口概述
鉴于Java中数组用来存储数据的局限性,我们通常使用List替代数组
List集合类中元素有序、且可重复,集合中的每个元素都有其对应的顺序索引
List容器中的元素都对应一个整数型的序号记载其再容器中的位置,可以根据序号存取容器中的元素
JDK API中List接口的实现类常用的又:ArrayList、LinkList和Vector
面试题:ArrayList、LinkedList、Vector三者的异同?
- 同:三个类都是实现了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/**
* |---Collection接口:单列集合,用来存储一个一个的对象
* |---List接口:存储有序的、可重复的数据。 -->“动态数组”,替换原有的数组
* |---ArrayList:作为List接口的主要实现类,线程不安全的,效率高,底层使用Object[]存储
* |---LinkedList:对于频繁的插入、删除操作,使用此类效率比ArrayList高,底层使用双向链表
* |---Vector:作为List接口的古老实现类,线程安全的,效率低,底层使用Object[]存储
*
* ArrayList的源码分析:
* jdk7的情况下
* ArrayList arr = new ArrayList();//底层创建了长度是10的Object[]数组elementData
* list.add(123);//elementData[0] = new Integer(123);
* ...
* list.add(11);//如果此次的添加导致底层elementData数组容量不够,则扩容
* 默认情况下,扩容为原来容量的1.5倍,同时需要将原有数组中的数据复制到新的数组中
* 结论:建议开发中使用带参的构造器:ArrayList list = new ArrayList(int initial)预设置长度
*
* jdk8中ArrayList的变化:
* ArrayList arr = new ArrayList();//底层Object[]数组elementData初始化为{},并没有创建长度为10的数组
* list.ad(123);//第一次调用add()时,底层才创建了长度10的数组,并将数据123添加到element[0]
* ...;//后续的添加和扩容操作于jdk7无异
* 小结:
* jdk7中的ArrayList的对象的创建类似于单例的饿汉式,而jdk8中的ArrayList的对象的创建类似于单例的懒汉式,延迟了数组的创建,节省内存
*
* LinkedList的源码分析:
* LinkedList list = new LinkedList();//内部生命了Node类型的first和last书行,默认值为null
* list.add(123);//将123封装到Node当中,创建了Node对象。
* 其中Node定义为:
* 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;
* }
* }
* Vector的源码分析:
* 再jdk7和jdk8中通过Vector()构造器创建对象时,底层都创建了长度为10的数组
* 在扩容方面,默认扩容为原来的数组长度的2倍
* 基本已经被淘汰,一般不会使用
**/List接口方法
List除了从Collection集合继承的方法外,List集合里添加了一些根据索引来操作集合元素的方法
- void add(int index, Object ele):在index位置插入ele元素
- boolean addAll(int index, Collection eles):从index位 置开始将eles中的所有元素添加进来
- Object get(int index):获取指定index位置的元素
- int indexOf(Object obj):返回obj在集合中首次出现的位置,如果不存在返回-1
- int lastIndexOf(Object obj):返回obj在当前集合中末次出现的位置,如果不存在返回-1
- Object remove(int index):移除指定index位置的元素,并返回此元素
- Object set(inde index, Object ele):设置指定index未知的元素ele
- List subList(int fromIndex, int toIndex):返回从fromIndex到toIndex位置的子集合,左闭右开
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
public void test1(){
ArrayList list = new ArrayList();
list.add(123);
list.add(456);
list.add("AA");
list.add(new Person("Tom",22));
list.add(456);
System.out.println(list);
//void add(int index, Object ele):在index位置插入ele元素
list.add(1,"BB");
System.out.println(list);
//boolean addAll(int index, Collection eles):从index位置开始将eles中的所有元素添加进来
List list1 = Arrays.asList(1, 2, 3);
list.addAll(list1);
System.out.println(list.size());//9
//Object get(int index):获取指定index位置的元素
System.out.println(list.get(1));
//int indexOf(Object obj):返回obj在集合中首次出现的位置,如果不存在返回-1
System.out.println(list.indexOf(456));
//int lastIndexOf(Object obj):返回obj在当前集合中末次出现的位置,如果不存在返回-1
System.out.println(list.lastIndexOf(456));
//Object remove(int index):移除指定index位置的元素,并返回此元素
Object remove = list.remove(1);
System.out.println(remove);
System.out.println(list);
//Object set(inde index, Object ele):设置指定index未知的元素ele
list.set(1,"CC");
System.out.println(list);
//List subList(int fromIndex, int toIndex):返回从fromIndex到toIndex位置的子集合,左闭右开
List list2 = list.subList(3, 6);
System.out.println(list2);
}
/*
[123, 456, AA, Person{name='Tom', age=22}, 456]
[123, BB, 456, AA, Person{name='Tom', age=22}, 456]
9
BB
2
5
BB
[123, 456, AA, Person{name='Tom', age=22}, 456, 1, 2, 3]
[123, CC, AA, Person{name='Tom', age=22}, 456, 1, 2, 3]
[Person{name='Tom', age=22}, 456, 1]
*/常用方法
- 增:add(Object obj)
- 删:remove(int index)/remove(Object obj)
- 改:set(int index, Object ele)
- 查:get(int index)
- 插:add(int index, Object obj)
- 长度:size()
- 遍历:
- Iterator迭代器方式
- 增强for循环
- 普通的循环
面试题
1
2
3
4
5
6
7
8
9
10
11
12
13
public void testListRemove() {
List list = new ArrayList();
list.add(1);
list.add(2);
list.add(3);
updateList(list);
System.out.println(list);//
}
private static void updateList(List list) {
list.remove(2);//没有自动装箱,默认是索引,所以输出1,2
list.remove(new Integer(2));//自己主动装箱,删除2,所以输出1,3
}
Collection子接口之二:Set接口
Set接口概述
- Set接口是Collection的子接口,set接口没有提供额外的方法
- Set集合不允许包含相同的元素,如果试把两个相同的元素假如同一个Set集合中,则添加操作失败
- Set判断两个对象是否相同不是使用==运算符,而是根据equals()方法
- Set接口中没有额外定义新的方法,使用的都是Collection中声明过的方法
- 向Set添加的数据,其所在的类一定要重写hashCode()和equals()
- 重写的hashCode()和equals()尽可能保持一致性:相等的对象必须具有相等的散列码
Set实现类之一:HashSet
1 |
|
Set:存储无序的、不可重复的数据(以HashSet为例说明)
- 无序性:不等于随机性。不是遍历的顺序和添加的顺序不同叫无序,而是存储的数组在底层数组中并非按照数组索引的顺序添加的,而是根据数据的哈希值决定的
- 不可重复性:保证添加的元素按照equals()判断时,不能返回true,即相同的元素不能添加进来
添加元素的过程(以HashSet为例)
- 先创建了数组,跟ArrayList一样jdk7创建对象直接创建,jdk8是添加数据才创建,长度为16
- 插的位置相同哈希值不同的时候jdk7插在头上后指原元素,jdk8是插在后面前指原元素,七上八下
- 我们向HashSet中添加元素a,首先调用元素a所在类的hashCode()方法,计算元素a的哈希值,此哈希值接着通过某种算法计算出在HashSet底层数组中的存放位置(即为:索引位置),判断数组此位之上是否已经有元素:
- 如果此位置上没有其他元素,则元素a添加成功———情况一
- 如果此位置上有其他元素b(或以链表形式存在的多个元素),则比较元素a与元素b的哈希值
- 如果哈希值不相同,则元素a添加成功——–情况二
- 如果哈希值相同,进而需要调用元素a所在类的equals()方法
- equals()返回true,元素a添加失败
- equals()返回false,则元素a添加成功———情况三
- 对于添加成功的情况二和情况三而言:元素a与已经存在指定索引位置上的数据以链表的方式存储
- jdk7:元素a放到数组中,指向原来元素
- jdk8:原来的元素在数组中,指向元素a
为什么用Eclipse/IDEA复写hashCode方法,有31这个数字?
- 选择系数的时候要选择尽量大的系数。因为如果计算出来的hash地址越大,所谓的 “冲突”就越少,查找起来效率也会提高。(减少冲突)
- 并且31只占用5bits,相乘造成数据溢出的概率较小。
- 31可以 由i*31== (i<<5)-1来表示,现在很多虚拟机里面都有做相关优化。(提高算法效 率)
- 31是一个素数,素数作用就是如果我用一个数字来乘以这个素数,那么最终出来的结 果只能被素数本身和被乘数还有1来整除!(减少冲突)
Set实现类之二:LinkedHashSet
- LinkHashSet是HashSet的子类,在添加数据的同时,没个数据还维护了两个引用,记录此数据前一个数据和后一个数据
- LinkedHashSet根据元素的hashCode值来决定元素的存储位置,但它同时使用双向链表维护元素的次序,这使得元素看起来是以插入顺序保存的
- LinkedHashSet插入性能略低于HashSet,但在迭代访问Set里的全部元素时有很好的性能
- LinkedHashSet不允许集合元素重复
- 优点:对于频繁的遍历操作,LinkHashSet效率高于Hashset
1 |
|
LinkedHashSet底层结构
Set接口之三:TreeSet
向TreeSet中添加的数据,要求是相同类的对象
两种排序方式:自然排序和定制排序
自然排序
实现compareable()接口
在自然排序中,比较两个对象是否相同的标准为:compareTo()返回0,不再是equals()
1 |
|
定制排序
- 在定制排序中,比较两个对象是否相同的标准为:compare()返回0,不再是equals()
1 |
|
Set面试题
1 | HashSet set = new HashSet(); |
先添加了两个Person对象AA和BB,当改为CC后,remove(p1)时按照哈希值找的是CC的位置,但是CC的位置没有对象,所以删除失败,输出两个对象CC和BB
然后添加CC,因为虽然AA改成了CC但是原CC位置在AA上,所以CC的位置没有对象,所以可以添加进去,输出三个CC、BB和CC
再添加一个AA时,根据哈希值找到原CC的位置了,但是通过equals()方法比较两个对象的属性并不相同,所以能够添加进去,所以输出四个对象:CC、BB、CC、AA
先看哈希值,哈希值相同再看值,先用hashCode()方法再用equals()方法
Map接口
Map接口继承树
Map接口概述
- Map与Collection并列存在。用于保存具有映射关系的数据:key-value
- Map中的key和value都可以是任何引用类型的数据
- Map中key用Set来存放,不允许重复,即同一个Map对象所对应的类,须重写hashCode()和equals()方法
- 常用String类作为Map的“键”
- key和value之间存在单向一对一的关系,即通过指定的key总能找到唯一的、确定的value
- Map接口的常用实现类:HashMao、TreeMap、LinkedHashMap和Properties。其中,HashMap是Map接口使用频率最高的实现类
1 | |----Map:双列数据,存储key-value对的数据 ---类似于高中的函数:y = f(x) |
面试题
- HashMap的底层实现原理?
- .HashMap 和 Hashtable的异同?
- Curren tHashMap 与 Hashtable的异同?
Map结构的理解
Map中的key:无序的,不可重复的,使用Set存储所有的key --->key所在的类要重写equals()和hashCode()(以HashMap为例)
Map中的value:无序的,可重复的,使用Collection存储所有的value --->value所在的类要重写equals()
一个键值对:key-value构成了一个Entry对象
- Map中的entry:无序的,不可重复的,使用Set存储所有的entry
HashMap的底层实现原理?
1 | /* |
LinkHashMap的底层实现原理
1 | 源码中: |
Map接口常用方法
- 添加、删除、修改操作:
- Object put(Object key,Object value):将指定key-value添加到(或修改)当前map对象中
- void putAll(Map m):将m中的所有key-value对存放到当前map中
- Object remove(Object key):移除指定key的key-value对,并返回value
- void clear():清空当前map中的所有数据
- 元素查询的操作:
- Object get(Object key):获取指定key对应的value
- boolean containsKey(Object key):是否包含指定的key
- boolean containsValue(Object value):是否包含指定的value
- int size():返回map中key-value对的个数
- boolean isEmpty():判断当前map是否为空
- boolean equals(Object obj):判断当前map和参数对象obj是否相等
- 元视图操作的方法:
- Set keySet():返回所有key构成的Set集合
- Collection values():返回所有value构成的Collection集合
- Set entrySet():返回所有key-value对构成的Set集合
- 总结:
- 添加:Object put(Object key,Object value)
- 删除:Object remove(Object key)
- 修改:Object put(Object key,Object value)
- 查询:Object get(Object key)
- 长度:int size()
- 遍历:keySet()/values()/entrySet()
1 | public class MapTest { |
Map实现类之一:HashMap
- HashMap是 Map 接口使用频率最高的实现类。
- 允许使用null键和null值,与HashSet一样,不保证映射的顺序。
- 所有的key构成的集合是Set:无序的、不可重复的。所以,key所在的类要重写: equals()和hashCode()
- 所有的value构成的集合是Collection:无序的、可以重复的。所以,value所在的类 要重写:equals()
- 一个key-value构成一个entry
- 所有的entry构成的集合是Set:无序的、不可重复的
- HashMap 判断两个 key 相等的标准是:两个 key 通过 equals() 方法返回 true, hashCode 值也相等。
- HashMap 判断两个 value相等的标准是:两个 value 通过 equals() 方法返回 true。
HashMap的存储结构:JDK8之前
- HashMap的内部存储结构其实是数组和链表的结合。当实例化一个HashMap时, 系统会创建一个长度为Capacity的Entry数组,这个长度在哈希表中被称为容量 (Capacity),在这个数组中可以存放元素的位置我们称之为“桶”(bucket),每个 bucket都有自己的索引,系统可以根据索引快速的查找bucket中的元素。
- 每个bucket中存储一个元素,即一个Entry对象,但每一个Entry对象可以带一个引 用变量,用于指向下一个元素,因此,在一个桶中,就有可能生成一个Entry链。 而且新添加的元素作为链表的head。
- 添加元素的过程:
- 向HashMap中添加entry1(key,value),需要首先计算entry1中key的哈希值(根据 key所在类的hashCode()计算得到),此哈希值经过处理以后,得到在底层Entry[]数 组中要存储的位置i。如果位置i上没有元素,则entry1直接添加成功。如果位置i上 已经存在entry2(或还有链表存在的entry3,entry4),则需要通过循环的方法,依次 比较entry1中key和其他的entry。如果彼此hash值不同,则直接添加成功。如果 hash值不同,继续比较二者是否equals。如果返回值为true,则使用entry1的value 去替换equals为true的entry的value。如果遍历一遍以后,发现所有的equals返回都 为false,则entry1仍可添加成功。entry1指向原有的entry元素。
HashMap的扩容
- 当HashMap中的元素越来越多的时候,hash冲突的几率也就越来越高,因为数组的 长度是固定的。所以为了提高查询的效率,就要对HashMap的数组进行扩容,而在 HashMap数组扩容之后,最消耗性能的点就出现了:原数组中的数据必须重新计算 其在新数组中的位置,并放进去,这就是resize。
那么HashMap什么时候进行扩容呢?
当HashMap中的元素个数超过数组大小(数组总大小length,不是数组中个数 size)loadFactor 时 , 就 会 进 行 数 组 扩 容 , loadFactor 的默认 值 (DEFAULT_LOAD_FACTOR)为0.75,这是一个折中的取值。也就是说,默认情况 下,数组大小(DEFAULT_INITIAL_CAPACITY)为16,那么当HashMap中元素个数 超过160.75=12(这个值就是代码中的threshold值,也叫做临界值)的时候,就把 数组的大小扩展为 2*16=32,即扩大一倍,然后重新计算每个元素在数组中的位置, 而这是一个非常消耗性能的操作,所以如果我们已经预知HashMap中元素的个数, 那么预设元素的个数能够有效的提高HashMap的性能
HashMap的存储结构:JDK 1.8
- HashMap的内部存储结构其实是数组+链表+树的结合。当实例化一个 HashMap时,会初始化initialCapacity和loadFactor,在put第一对映射关系 时,系统会创建一个长度为initialCapacity的Node数组,这个长度在哈希表 中被称为容量(Capacity),在这个数组中可以存放元素的位置我们称之为 “桶”(bucket),每个bucket都有自己的索引,系统可以根据索引快速的查 找bucket中的元素。
- 每个bucket中存储一个元素,即一个Node对象,但每一个Node对象可以带 一个引用变量next,用于指向下一个元素,因此,在一个桶中,就有可能 生成一个Node链。也可能是一个一个TreeNode对象,每一个TreeNode对象 可以有两个叶子结点left和right,因此,在一个桶中,就有可能生成一个 TreeNode树。而新添加的元素作为链表的last,或树的叶子结点。
那么HashMap什么时候进行扩容和树形化呢?
- 当HashMap中的元素个数超过数组大小(数组总大小length,不是数组中个数 size)loadFactor 时 , 就会进行数组扩容 , loadFactor 的默认 值 (DEFAULT_LOAD_FACTOR)为0.75,这是一个折中的取值。也就是说,默认 情况下,数组大小(DEFAULT_INITIAL_CAPACITY)为16,那么当HashMap中 元素个数超过160.75=12(这个值就是代码中的threshold值,也叫做临界值) 的时候,就把数组的大小扩展为 2*16=32,即扩大一倍,然后重新计算每个元 素在数组中的位置,而这是一个非常消耗性能的操作,所以如果我们已经预知 HashMap中元素的个数,那么预设元素的个数能够有效的提高HashMap的性能。
- 当HashMap中的其中一个链的对象个数如果达到了8个,此时如果capacity没有 达到64,那么HashMap会先扩容解决,如果已经达到了64,那么这个链会变成 树,结点类型由Node变成TreeNode类型。当然,如果当映射关系被移除后, 下次resize方法时判断树的结点个数低于6个,也会把树再转为链表。
关于映射关系的key是否可以修改?answer:不要修改
- 映射关系存储到HashMap中会存储key的hash值,这样就不用在每次查找时重新计算 每一个Entry或Node(TreeNode)的hash值了,因此如果已经put到Map中的映射关 系,再修改key的属性,而这个属性又参与hashcode值的计算,那么会导致匹配不上。
HashMap的存储结构总结
- HashMap map = new HashMap();//默认情况下,先不创建长度为16的数组
- 当首次调用map.put()时,再创建长度为16的数组
- 数组为Node类型,在jdk7中称为Entry类型
- 形成链表结构时,新添加的key-value对在链表的尾部(七上八下)
- 当数组指定索引位置的链表长度>8时,且map中的数组的长度> 64时,此索引位置 上的所有key-value对使用红黑树进行存储
HashMap源码中的重要常量
- DEFAULT_INITIAL_CAPACITY : HashMap的默认容量,16
- MAXIMUM_CAPACITY : HashMap的最大支持容量,2^30
- DEFAULT_LOAD_FACTOR:HashMap的默认加载因子
- TREEIFY_THRESHOLD:Bucket中链表长度大于该默认值,转化为红黑树
- UNTREEIFY_THRESHOLD:Bucket中红黑树存储的Node小于该默认值,转化为链表
- MIN_TREEIFY_CAPACITY:桶中的Node被树化时最小的hash表容量。(当桶中Node的 数量大到需要变红黑树时,若hash表容量小于MIN_TREEIFY_CAPACITY时,此时应执行 resize扩容操作这个MIN_TREEIFY_CAPACITY的值至少是TREEIFY_THRESHOLD的4 倍。)
- table:存储元素的数组,总是2的n次幂
- entrySet:存储具体元素的集
- size:HashMap中存储的键值对的数量
- modCount:HashMap扩容和结构改变的次数。
- threshold:扩容的临界值,=容量*填充因子
- loadFactor:填充因子
面试题
谈谈你对HashMap中put/get方法的认识?如果了解再谈谈 HashMap的扩容机制?默认大小是多少?什么是负载因子( 或填充比)?什么是吞吐临界值(或阈值、threshold)?
负载因子值的大小,对HashMap有什么影响
- 负载因子的大小决定了HashMap的数据密度。
- 负载因子越大密度越大,发生碰撞的几率越高,数组中的链表越容易长, 造成查询或插入时的比较次数增多,性能会下降。
- 负载因子越小,就越容易触发扩容,数据密度也越小,意味着发生碰撞的 几率越小,数组中的链表也就越短,查询和插入时比较的次数也越小,性 能会更高。但是会浪费一定的内容空间。而且经常扩容也会影响性能,建 议初始化预设大一点的空间。
- 按照其他语言的参考及研究经验,会考虑将负载因子设置为0.7~0.75,此 时平均检索长度接近于常数
Map实现类之二:LinkedHashMap
- LinkedHashMap 是 HashMap 的子类
- 在HashMap存储结构的基础上,使用了一对双向链表来记录添加 元素的顺序
- 与LinkedHashSet类似,LinkedHashMap 可以维护 Map 的迭代 顺序:迭代顺序与 Key-Value 对的插入顺序一致
HashMap中的内部类:Node
1 | static class Node<K,V> implements Map.Entry<K,V> { |
LinkedHashMap中的内部类:Entry
1 | static class Entry<K,V> extends HashMap.Node<K,V> { |
Map实现类之三: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。
1 | public class TreeMapTest { |
Map实现类之四:Hashtable
- Hashtable是个古老的 Map 实现类,JDK1.0就提供了。不同于HashMap, Hashtable是线程安全的。
- Hashtable实现原理和HashMap相同,功能相同。底层都使用哈希表结构,查询 速度快,很多情况下可以互用。
- 与HashMap不同,Hashtable 不允许使用 null 作为 key 和 value
- 与HashMap一样,Hashtable 也不能保证其中 Key-Value 对的顺序
- Hashtable判断两个key相等、两个value相等的标准,与HashMap一致。
Map实现类之五:Properties
- Properties 类是 Hashtable 的子类,该对象用于处理属性文件
- 由于属性文件里的 key、value 都是字符串类型,所以 Properties 里的 key 和 value 都是字符串类型
- 存取数据时,建议使用setProperty(String key,String value)方法和 getProperty(String key)方法
1 | Properties pros = new Properties(); |
1 | public class PropertiesTest { |
Collections工具类
- 工具类是静态方法,可以直接调用,比如以前学过的工具类:Arrays
- Collections是一个操作Set、Lsit和Map等集合的工具类
- Collections中提供了一系列静态的方法对集合元素进行排序、查询和修改等操作,还提供了对集合对象设置不可变、对集合对象实现同步控制等方法
- 排序操作:(均为static方法)
- reverse(List):反转List中元素的顺序
- shuffle(List):对List集合元素进行随机排序
- sort(List):根据元素的自然顺序对指定List集合元素按升序排序
- sort(List, Comparator):根据指定的Comparator产生的顺序对List集合元素进行排序
- swap(List, int, int):将指定List集合中的i处元素和j处元素进行交换
Collections常用方法
- 查找、替换
- Object max(Collection):根据元素的自然顺序,返回给定集合中的最大元素
- Object max(Collection,Comparator):根据 Comparator 指定的顺序,返回 给定集合中的最大元素
- Object min(Collection)
- Object min(Collection,Comparator)
- int frequency(Collection,Object):返回指定集合中指定元素的出现次数
- void copy(List dest,List src):将src中的内容复制到dest中
- boolean replaceAll(List list,Object oldVal,Object newVal):使用新值替换 List 对象的所有旧值
Collections常用方法:同步控制
- Collections 类中提供了多个 synchronizedXxx() 方法,该方法可使将指定集 合包装成线程同步的集合,从而可以解决多线程并发访问集合时的线程安全 问题
补充:Enumeration
- Enumeration 接口是 Iterator 迭代器的 “古老版本”
1 | Enumeration stringEnum = new StringTokenizer("a-b*c-d-e-g", "-"); |
面试题
Collection 和 Collections的区别?
Collection是创建集合的一个借口
Collections是一个静态工具类可以用来操作Collection
练习
见framework=>testing