文档章节

Java集合包

學習是一种信仰
 學習是一种信仰
发布于 2017/07/25 11:59
字数 3352
阅读 17
收藏 1
点赞 0
评论 0

集合包是java中最常用的包,最常用的有Collection和Map接口的实现类,前者用于存放多个单对象,后者用于存放key-value形式的键值对。

java集合包常用实现类结构图如下所示(I表示接口):

 

 

 

 

 

 

1、ArrayList

动态数组,底层即数组,可以用来容纳任何对象,要求连续存放。ArrayList的重要成员是Object[] elementDate int Size表示有效元素的个数,数组的初始大小是10,扩容操作示意图如下,之前(上面)这块内存变成垃圾。 因此在初始化时尽量指定初始容量,避免扩容产生的内存垃圾,影响性能。

public ArrayList(int initialCapacity) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    this.elementData = new Object[initialCapacity];
}// 指定初始化大小

特点及使用注意

(1)foreach中能否对其基本类型元素值(包括数字、字符串、布尔)进行赋值改变?

 不能,高级For在JDK 5.0开始引入,用其迭代代码简洁,在foreach中修改的只是元素的副本,并不会改变原值(反编译之后可发现这一点),所以高级For循环可以用来遍历查询,不可修改当前取回的元素本身。

参考链接:http://me2xp.blog.51cto.com/6716920/1630007/

但是对象类型的元素有所不同,如果对对象数组进行遍历,则可以修改元素的状态,在每一轮循环中都可以拿到对象引用对其状态(成员变量、类变量)进行修改。

(2)如何正确遍历并删除ArrayList元素值?

问题背景:给定字符串集合["a","b","b","c"],删除其中元素"b"。

常见错误写法1:

public static void remove(List<String> list) 
	{
		for (int i = 0; i < list.size(); i++) 
		{
			String s = list.get(i);
			if (s.equals("b")) 
			{
				list.remove(s);
			}
		}
	}
// 错误的原因:这种最普通的循环写法执行后会发现第二个“b”的字符串没有删掉。

常见错误写法2:

public static void remove(List<String> list) 
	{
		for (String s : list)
		{
			if (s.equals("b")) 
			{
				list.remove(s);
			}
		}
	}
// 使用增强的for循环 在循环过程中从List中删除元素以后,继续循环List时会报ConcurrentModificationException,但删除之后马上就跳出的也不会出现异常 

思考及对策

为何和出现错误1,怎么解决?

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;
	}

private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,numMoved);
        elementData[--size] = null; // Let gc do its work
    }

可以看到会执行System.arraycopy方法,导致删除元素时涉及到数组元素的移动。针对错误写法1,在遍历第一个字符串b时因为符合删除条件,所以将该元素从数组中删除,并且将后一个元素移动(也就是第二个字符串b)至当前位置,导致下一次循环遍历时后一个字符串b并没有遍历到,所以无法删除。针对这种情况可以倒序删除的方式来避免:

public static void remove(ArrayList<String> list) 
	{
		for (int i = list.size() - 1; i >= 0; i--) 
		{
			String s = list.get(i);
			if (s.equals("b")) 
			{
				list.remove(s);
			}
		}
	}

为何会出现错误2怎么解决?

final void checkForComodification() {
		if (modCount != expectedModCount)
			throw new ConcurrentModificationException();
	}

这里会做迭代器内部修改次数检查,因为上面的remove(Object)方法修改了modCount的值,所以才会报出并发修改异常。要避免这种情况的出现则在使用迭代器迭代时(显示或for-each的隐式)不要使用ArrayList的remove,改为用Iterator的remove即可:

public static void remove(List<String> list) 
		{
		Iterator<String> it = list.iterator();
		while (it.hasNext()) 
		{
			String s = it.next();
			if (s.equals("b")) 
			{
				it.remove();
			}
		}
}

部分参考:http://swiftlet.net/archives/743; http://elim.iteye.com/blog/1523785

(3)ArrayList非线程安全,如何解决?

Collections给出了解决方案,提供了synchronizedCollection方法,该方法返回一个线程安全容器。

*Java中常用的集合框架中的实现类HashSet、TreeSet、ArrayList、ArrayDeque、LinkedList、HashMap、TreeMap都是线程不安全的,如果有多个线程同时访问它们,且同时有多个线程修改他们的时候,将会出现如读脏数据等错误。Collections给出了解决方案,提供了synchronizedCollection方法来实现线程安全,该方法返回一个线程安全容器。

(4)contains方法

contains()方法是通过将传入的实际参数和集合中已有的元素进行equals()比较来实现的,Object类中的equals()方法比较的是两个对象的地址,因此需要根据实际需要重写equals()方法。
(5)ArrayList、LinkedList、Vector、Stack区别联系

ArrayList和LinkedList是List(线性表)的两种典型实现:基于数组和基于双向链表的线性表。一般而言,由于数组以一块连续内存区来保存所有的数组元素,所以数组在随机访问时性能最好,所有的内部以数组作为底层实现的集合在随机访问时性能都比较好;而内部以链表作为底层实现的集合在执行插入、删除操作时有较好的性能。但总体来说,ArrayList的性能要更好,因此大部分使用时都应该考虑使用ArrayList。

  • 如果需要遍历List集合元素,对于ArrayList和Vector(也是以数组形式存储集合元素的一种集合类型)集合,应该使用随机访问方法(get)来遍历集合元素;对于LinkedList集合,则应该采用迭代器(Iterator)来遍历集合元素。
  • 如果需要经常执行插入、删除操作来改变包含大量数据的List集合的大小,可以考虑使用LinkedList集合。使用ArrayList和Vector集合可能需要经常重新分配内部数组的大小,效果较差。
  • 如果有多个线程需要同时访问List集合的元素,开发者可以考虑使用Collections将集合包装成线程安全的集合。

Vector是基于synchronized机制实现的线程安全的ArrayList,但在插入元素容量扩充时机制略有不同,通过传入的capacityIncrement来控制容量的扩充。

Stack继承自Vector,在此基础上实现了栈的弹出以及压入和弹出操作,push、pop、peek(只返回,不出栈)

2、HashMap

底层实现

JDK7实现,数组+链表;JDK8实现,数组+红黑树。

可参考:https://my.oschina.net/hosee/blog/618953

存储过程

当程序试图将一个 key-value 对放入 HashMap 中时,程序首先根据该 key 的 hashCode() 返回值决定该 Entry 的存储位置:如果两个 Entry 的 key 的 hashCode() 返回值相同,那它们的存储位置相同。如果这两个 Entry 的 key 通过 equals 比较返回 true,新添加 Entry 的 value 将覆盖集合中原有 Entry 的 value,但 key 不会覆盖。如果这两个 Entry 的 key 通过 equals 比较返回 false,新添加的 Entry 将与集合中原有 Entry 形成 Entry 链,而且新添加的 Entry 位于 Entry 链的头部。流程图如下所示:

读取实现

如果 HashMap 的每个 bucket 里只有一个 Entry 时,HashMap 可以根据索引、快速地取出该 bucket 里的 Entry;在发生“Hash 冲突”的情况下,单个 bucket 里存储的不是一个 Entry,而是一个 Entry 链,系统只能必须按顺序遍历每个 Entry,直到找到想搜索的 Entry 为止——如果恰好要搜索的 Entry 位于该 Entry 链的最末端(该 Entry 是最早放入该 bucket 中),那系统必须循环到最后才能找到该元素。

HashMap 在底层将 key-value 当成一个整体进行处理,这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对,当需要存储一个 Entry 对象时,会根据 Hash 算法来决定其存储位置;当需要取出一个 Entry 时,也会根据 Hash 算法找到其存储位置,直接取出该 Entry。

可参考:http://www.liuzk.com/162.html

性能选项

实际容量(capacity):大于initial capacity最小的2的n次方,如10<16

初始容量(initial capacity):可以通过HashMap的构造函数指定

size:变量保存了该 HashMap 中所包含的 key-value 对的数量

threshold:该变量包含了 HashMap 能容纳的 key-value 对的极限,它的值等于 HashMap 的容量乘以负载因子(load factor)

负载因子(load factor):决定了Hash表的最大填满程度

当创建 HashMap 时,有一个默认的负载因子(load factor),其默认值为 0.75,这是时间和空间成本上一种折衷:增大负载因子可以减少 Hash 表(就是那个 Entry 数组)所占用的内存空间,但会增加查询数据的时间开销,而查询是最频繁的的操作(HashMap 的 get() 与 put() 方法都要用到查询);减小负载因子会提高数据查询的性能,但会增加 Hash 表所占用的内存空间。

掌握了上面知识之后,我们可以在创建 HashMap 时根据实际需要适当地调整 load factor 的值;如果程序比较关心空间开销、内存比较紧张,可以适当地增加负载因子;如果程序比较关心时间开销,内存比较宽裕则可以适当的减少负载因子。通常情况下,程序员无需改变负载因子的值。

3、TreeMap

采用红黑树(https://my.oschina.net/hosee/blog/618828)的数据结构来管理key-value对(红黑树的每个节点就是一个key-value对)

存储key-value对需要根据key排序,排序方式与TreeSet相同(两种排序方式)。

判断两个key相等的标准是:通过compareTo()返回0即认为这两个key相等。

对于自定义类作为key的情况,最好做到:两个key通过equals()方法比较返回true时,compareTo()方法也返回0。

两种排序的比较器:

java.lang.Comparable,TreeMap使用无参构造函数,那么容纳的对象必须实现Comparable接口。

public int compareTo(T o);

java.util.Comparator,TreeSet在构造时使用Comparator作为构造函数的参数。(两种排序方式同时存在时,该方式优先权更高)

int compare(T o1, T o2);

4、HashSet

HashSet的底层实现用到HashMap,HashSet操作的就是HashMap。(Java源码就是先实现HashMap、TreeMap,然后包装一个value为null的Map集合来实现Set集合的)

存储过程

两个对象的equals()方法返回true,但是hashCode值不相等,这时HashSet会把这两个对象存储在Hash表的不同位置,两个对象均可以添加成功,但这会与Set集合的规则相冲突。(这就是不重写相应hashCode()方法的后果,也可阅读参考:http://blog.chinaunix.net/uid-26602509-id-3355659.html)

所以阿里Java规范这样写道:

HashSet如何判断对象是否是相同

——>两个对象通过equals()方法比较相等,并且两个对象的hashCode方法的返回值也相等。

因此需要注意:

当把一个对象放入HashSet中时,如果需要重写此对象对应类的equals()方法,则同时需要重写其hashCode()方法。具体规则是:如果两个对象通过equals()方法比较返回true时,则它们的hashCode值也应该相等(Object规范:相等的对象必须具有相等的hashcode)。

5、TreeSet

底层是TreeMap,集合中的元素处于排序状态。采用红黑树的数据结构来存储集合元素。TreeSet支持两种排序方式:自然排序(默认情况)和定制排序。

当把一个对象添加到TreeSet中时,TreeSet会调用该对象的compareTo(Object obj)方法与容器中的其它对象比较大小,然后根据红黑树结构找到它的存储位置。如果compareTo(Object obj)返回0,意味着两个对象相同将无法添加到TreeSet集合中。

附:阿里Java规范-集合

6、List/Set/Map判断对象相同方式的区别

import java.util.*;

class A {
    @Override
    public int hashCode() {
        return UUID.randomUUID().hashCode();
    }

    @Override
    public boolean equals(Object obj) {
        return true;
    }
}

public class Main {

    public static void main(String[] args) throws Exception {
        List<A> list = new ArrayList<>();
        A a1 = new A();
        A a2 = new A();
        list.add(a1);
        // list contains()方法是通过将传入的实际参数和集合中已有的元素进行equals()比较来实现的
        System.out.println(list.contains(a2));
        Map<A, Object> map = new HashMap<>();
        map.put(a1, null);
        System.out.println(map.containsKey(a2));
        Set<A> set = new HashSet<>();
        set.add(a1);
        System.out.println(set.contains(a2));
    }
}
// output:
true
false
false

那么HashSet是如何判断对象是否是相同的呢?

——>两个对象通过equals()方法比较相等,并且两个对象的hashCode方法的返回值也相等。

因此需要注意:

当把一个对象放入HashSet中时,如果需要重写此对象对应类的equals()方法,则同时需要重写其hashCode()方法。具体规则是:如果两个对象通过equals()方法比较返回true时,则它们的hashCode值也应该相等(Object规范:相等的对象必须具有相等的hashcode)。

Map与Set类似,List稍有不同,其contains()方法是通过将传入的实际参数和集合中已有的元素进行equals()比较来实现的,Object类中的equals()方法比较的是两个对象的地址,因此需要根据实际需要重写equals()方法。

 

 

© 著作权归作者所有

共有 人打赏支持
學習是一种信仰
粉丝 2
博文 45
码字总数 40347
作品 0
杭州
[Java 并发编程] 集合框架之 同步容器类 & 并发容器类

吾生也有涯,而知也无涯。———《庄子》 通过上一篇文章,我们已经知道设计一个线程安全类的原则和步骤,以及在设计过程中我们应当注意的细节。实际上,Java 的集合库包含了线程安全集合和非...

seaicelin ⋅ 05/25 ⋅ 0

百词斩Java程序员面试11个问题,你会几个?2018-04-10

近日,我们在w3cschool app开发者头条上,可以看到百词斩Java程序员面经。 在分享百词斩Java面经前,w3cschool特别给程序员小伙伴们带来一些Java学习干货: 0、学习Java必备的3大神器 如果你...

W3Cschool ⋅ 04/10 ⋅ 0

sharding-jdbc分库分表规则(1)-单表查询

前言 当数据量到达一定数量级的时候,一般都会考虑分库分表。sharding-jdbc是一个开源的客户端分库分表基础类库,以一个jar包的形式提供,基于原生的JDBC驱动进行增强,基本能够无缝整合旧代...

xiaomin0322 ⋅ 06/07 ⋅ 0

Java编程基础知识点和技术点归纳

Java是一种可以撰写跨平台应用软件的面向对象的程序设计语言。Java 技术具有卓越的通用性、高效性、平台移植性和安全性,广泛应用于PC、数据中心、游戏控制台、科学超级计算机、移动电话和互...

Java小辰 ⋅ 05/23 ⋅ 0

每个项目中,你必须知道的11个Java第三方类库。

Java第三方library ecosystem是一个很广阔的范畴。不久前有人撰文:每个项目中,你必须知道的11个Java第三方类库。 单元测试 1.DBUnit DBunit是一个基于junit扩展的数据库测试框架。它提供了...

thinkyoung ⋅ 2015/01/07 ⋅ 0

甲骨文开源Java 性能监控调试工具 JMC

JMC (Java Mission Control) 是Oracle开源的Java 性能监控调试工具, 源自 JRockit JVM , 主要由三个组件构成:Java 进程浏览器、JMX 控制台和 Java Flight 记录器。 主要特性: Java 进程浏览...

marsdream ⋅ 05/07 ⋅ 0

重磅!Java 性能监控调试工具 JMC 宣布开源

JRockit JVM 创始人之一、Oracle Java 产品组成员 Marcus Hirt 昨日在其博客上宣布,Java Mission Control(JMC)的源代码已正式开源。 JMC 是源自 JRockit JVM 的一套监控和管理工具,Oracl...

王练 ⋅ 05/07 ⋅ 6

Java面试2018常考题目汇总及答案带走不谢!

一、JAVA基础篇-概念 1.简述你所知道的Linux: Linux起源于1991年,1995年流行起来的免费操作系统,目前, Linux是主流的服务器操作系统, 广泛应用于互联网、云计算、智能手机(Android)等...

java高级架构牛人 ⋅ 06/14 ⋅ 0

Google的Guava类库简介(转)

说明:信息虽然有点旧,至少可以先了解个大概。 Guava是一个Google的基于Java的类库集合的扩展项目,包括collections, caching, primitives support, concurrency libraries, common annotat...

easonjim ⋅ 2017/11/01 ⋅ 0

【目录导航】JAVA零基础进阶之路

【JAVA零基础入门系列】(已完结)导航目录 Day1 开发环境搭建 Day2 Java集成开发环境IDEA Day3 Java基本数据类型 Day4 变量与常量 Day5 Java中的运算符 Day6 Java字符串 Day7 Java输入与输出...

MFrank ⋅ 前天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

vue-cli是什么?

vue-cli是什么? vue-cli 是vue.js的脚手架,用于自动生成vue.js+webpack的项目模板,分为vue init webpack-simple 项目名 和vue init webpack 项目名 两种。 当然首先你的安装vue,webpack...

韦姣敏 ⋅ 27分钟前 ⋅ 0

12c rman中输入sql命令

12c之前版本,要在rman中执行sql语句,必须使用sql "alter system switch logfile"; 而在12c版本中,可以支持大量的sql语句了: 比如: C:\Users\zhengquan>rman target / 恢复管理器: Release 1...

tututu_jiang ⋅ 33分钟前 ⋅ 0

java 线程池

概述 减少了创建和销毁线程的次数,每个工作线程都可以被重复利用,可执行多个任务 可以根据系统的承受能力,调整线程池中工作线线程的数目,防止因为因为消耗过多的内存,而把服务器累趴下(...

轨迹_ ⋅ 38分钟前 ⋅ 0

Nginx的https配置记录以及http强制跳转到https的方法梳理

Nginx的https配置记录以及http强制跳转到https的方法梳理 一、Nginx安装(略) 安装的时候需要注意加上 --with-httpsslmodule,因为httpsslmodule不属于Nginx的基本模块。 Nginx安装方法: ...

Yomut ⋅ 50分钟前 ⋅ 0

SpringCloud Feign 传递复杂参数对象需要注意的地方

1.传递复杂参数对象需要用Post,另外需要注意,Feign不支持使用GetMapping 和PostMapping @RequestMapping(value="user/save",method=RequestMethod.POST) 2.在传递的过程中,复杂对象使用...

@林文龙 ⋅ 51分钟前 ⋅ 0

如何显示 word 左侧目录大纲

打开word说明文档,如下图,我们发现左侧根本就没有目录,给我们带来很大的阅读障碍 2 在word文档的头部菜单栏中,切换到”视图“选项卡 3 然后勾选“导航窗格”选项 4 我们会惊奇的发现左侧...

二营长意大利炮 ⋅ 55分钟前 ⋅ 0

智能合约编程语言Solidity之线上开发工具

工具地址:https://ethereum.github.io/browser-solidity/ 实例实验: 1.创建hello.sol文件 2.调试输出结果

硅谷课堂 ⋅ 56分钟前 ⋅ 0

ffmpeg 视频格式转换

转 Mp4 格式 #> ffmpeg -i input.avi -c:v libx264 output.mp4#> ffmpeg -i input.avi -c:v libx264 -strict -2 output.mp4#> ffmpeg -i input.avi -c:v libx264 -strict -2 -s 1......

Contac ⋅ 今天 ⋅ 0

VCS仿真生成vpd文件(verilog)

VCS仿真生成vpd文件(verilog): https://www.cnblogs.com/OneFri/p/5987673.html SYNOPSYS VCS常用命令使用详解 https://blog.csdn.net/hemmingway/article/details/49382551 DVE是synopsys公......

whoisliang ⋅ 今天 ⋅ 0

Spring Boot启动配置原理

几个重要的事件回调机制 配置在META-INF/spring.factories ApplicationContextInitializer SpringApplicationRunListener 只需要放在ioc容器中 ApplicationRunner CommandLineRunner 启动流程......

小致dad ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部