当前位置：文档之家 › Java集合类知识点总结

Java集合类知识点总结

  • 格式：docx
  • 大小：24.08 KB
  • 文档页数：12

Java集合类知识点总结

Java集合类

Java集合类 (1)

1.Map (3)

1.1.HashMap (3)

1.1.1.底层实现 (3)

1.1.2.特点 (3)

1.1.3.源码分析 (4)

1.1.4.多线程可能出现的问题 (5)

1.2.ConcurrentHashMap (6)

1.2.1.底层实现 (6)

1.2.2.源码分析 (7)

1.3.HashTable (9)

1.3.1.HashTable是线程安全的，因为所有方法上都加了synchronized关键

字。9

1.3.2.HashTable的key和value都不可以为null。 (9)

1.3.3.扩容时，capacity=2*capacity+1 (9)

1.3.4.数组默认大小为11 (9)

1.3.5.查找下标时，没有使用hash&length-1，而是直接进行计算的 (9)

1.4.TreeMap (9)

1.4.1.底层实现为红黑树 (9)

1.4.

2.TreeMap是一个有序的key-value集合，基于红黑树实现。该映射根据

其键的自然顺序进行排序，或者根据创建时提供的Comparator进行排序 (10)

1.4.3.接口实现 (10) 1.4.4.Entry (11)

1.5.LinkedHashMap (11)

1.5.1.底层是数组+链表+红黑树+双向链表 (11)

1.5.2.维护链表顺序和访问顺序 (11)

1.5.3.LinkedHashMap 可以通过构造参数 accessOrder 来指定双向链表是否在

元素被访问后改变其在双向链表中的位置。 (11)

1.5.4.当accessOrder为true时，get方法和put方法都会调用recordAccess

方法使得最近使用的Entry移到双向链表的末尾；当accessOrder为默认值

false时，recordAccess方法什么也不会做。 (11)

1.5.5.LRU实现 (11)

2.Collection (11)

2.1.List (12)

2.1.1.ArrayList (12)

2.1.2.LinkedList (13)

2.1.3.CopyOnWriteArrayList (13)

2.2.Set (14)

2.2.1.HashSet (14)

2.2.2.TreeSet (14)

2.2.3.LinkedHashSet (15)

1.Map

1.1.HashMap

1.1.1.底层实现

1.7 数组+链表

数组的优点是访问速度快，但是插入删除操作慢

因为数组在内存中是连续存放的，因此存取很快

链表的优点是插入删除速度快，但是访问速度慢

由于链表不是连续存放的，因此插入删除时，只需要修改前后指针的指

向即可，不需要移动元素位置

1.8 数组+链表+红黑树

拉链法由头插法改为了尾插法

因为头插法在多线程的时候可能会导致死循环

链表长度大于8的时候转化为红黑树

红黑树的时间复杂度为logn,线性表查找的平均时间复杂度为n/2,因此在

链表长度为8时进行转化效率最高

红黑树的转化也是比较消耗性能的

链表个数超过8则链表转换成树结构，链表个数小于8则树结构转换成

链表

1.1.

2.特点

存取的时间复杂度为O(1)

1.1.3.源码分析

put()

1.判断key是否为null，如果为null，调用putlForNullKey，将key插入到

数组下标为0的位置

2.调用hash()方法计算key的hashcode，得到hash值

3.调用indexFor()方法进行取模运算，得到元素的下标位置

1.indexFor方法为：h&(length - 1)

2.使用与运算，计算速度更快，因为二进制运算比十进制运算效率更高

(十进制运算还需要将二进制转化为十进制)

3.length之所以要设定为2次幂，就是为了这个indexFor方法服务

4.可以让散列更加均匀，length-1的最后一位为1，因此进行与运算时，

可以散列到奇数和偶数的下标位置，如果对length直接取模，由于

length为2次幂，所以最后一位一定为0，所以与运算的结果一定是偶

数，这也就导致奇数下标的位置不能被散列到。

4.依次和该下标位置上的链表中的node节点比较key是否相等

e.hash == hash && ((k = e.key) == key || key.equals(k))

首先判断e.hash==hash是因为不同的key值也可能被散列到同一个位

置，因此首先判断hash值，如果不相等则两个key肯定不等

如果相等，再通过==和equals比较是否相等，之所以要先判断hash值是否相等，是因为equal()很耗性能，因此先判断hash值能够提高效率

重写了hashcode()方法就必须重写equals方法

5.如果相等，更新value值，如果不相等，使用头插法(1.7)/尾插法(1.8)将

entry(1.7)/Node(1.8)插入到链表中

get()

和put()方法类似，获取到桶的下标，再在链表上查找key值，再获取key 对应的value值

resize()

当hashmap中的元素个数超过数组大小*loadFactor时，就会进行数组扩容

扩容时，令 capacity 为原来的两倍。

1.7时，需要new 一个新数组，并对旧数组上的所有元素进行indexFor()操

作确定下标地址,这一步很费时，1.8时只需判断hash值的左边新增的那一位是否为1，即可判断此节点是留在原地lo还是移动去高位hi,如果为1，则移动去高位，否则不变 1.7时，扩容的时候可能出现死循环，1.8没有这个问题

构造方法

在第一次put()的时候，数组才初始化

数组的长度为大于指定值的最小二次幂

数组默认大小为16

1.1.4.多线程可能出现的问题

1.扩容时可能出现死循环

2.put的时候可能被失效/覆盖

线程A,B同时调用addEntry方法，同时获取到了相同的头节点，然后A写入新的头结点之后，B也写入新的头结点，那B的写入操作就会覆盖A的写入操作造成A的写入操作丢失。

3.修改的时候可能被覆盖

线程A,B先后修改同一key值的value，会导致覆盖

4.put非null元素后get出来的却是null

扩容时调用的transfer方法，在获取数组的每个头节点的时候，在将e=头节点之后，都会将头节点置空，此时get可能导致获取到的值为0

1.2.ConcurrentHashMap

1.2.1.底层实现

1.7 segment数组+HashEntry数组(数组+链表)

chm由一个segment数组组成

segment

每个segment元素包含一个HashEntry数组，每个HashEntry包含一个链表

HashEntry大部分成员变量都为final

final k key

volatile V value

final int hash

final HashEntry next

1.8 数组+链表+红黑树 1.2.2.源码分析

put()

基本流程

1.7 通过两次hash确定

第一次Hash定位到Segment

通过segmentFor()函数进行,计算方式也和indexFor()相同

SegmentMask

ssize-1

SegmentShift

32-sshift

ssize

是大于ConcurrentLevel的最小二次幂

第二次Hash定位到元素所在的链表的头部

定位方法和HashMap中的indexFor()相同

通过segment.lock加锁

1.8通过两次hash确定

通过CAS+synchronized加锁

1.如果没有hash冲突就直接通过CAS插入

2.如果有hash冲突或者CAS操作失败，说明存在并发情况，使用

synchronized加锁

3.如果插入成功就调用addCount（）方法统计size，并且检查是否需要

扩容

源码分析

1.ensureSegment

1.判断是否被其他线程初始化，这里使用了getObjectVolatile()方法

2.使用segment[0]的属性来初始化其他槽

3.使用while()循环，内部使用CAS操作，尝试初始化槽

2.segment.put() get()

get不需要加锁，因为HashEntry的value值设定为了volatile

如果get()到的是null值，则可能这个key，value对正在put的过程中，如果出现这种情况，那么就通过lock加锁来保证取出的value是完整的

resize()

构造函数

先根据ConcurrentLevel构造出Segment数组

Segment数组大小是不大于concurrentLevel的最大的2的指数

每个Segment中的HashEntry数组的大小都是大于指定大小的最小二次幂

每个hashEntry的大小为大于initialCapacity/concurrentLevel的最小二次幂

初始参数

initialCapacity(每个HashEntry的长度)

loadFactor：扩容因子

concurrencyLevel：并发度，指Segment数组的长度

remove

在定位到待删除元素的位置以后，程序就将待删除元素前面的那一些元素全部复制一遍，然后再一个一个重新接到链表上去。尾结点指向e的下一个结点。e后面的结点不需要复制，它们可以重用。

因为HashEntry中的next是final，所以只能先把待删除之前的元素复制了再删除

size

size操作就是遍历了两次Segment，每次记录Segment的modCount值，然后将两次的modCount进行比较，如果相同，则表示期间没有发生过写入操作，就将原先遍历的结果返回，如果不相同，就需要将所有的

Segment都锁住，然后一个一个遍历了，

1.3.HashTable

合集下载

集合知识点

集合知识点

本章内容很重要，以后的学习以及工作中都会经常应用到。重点是掌握用几个常用的集合接口和类来操纵集合里的数据。至少需要掌握ArrayList TreeSet HashMap(HashTable)以及它们的特性，和对Swing组件的学习一样，要注意总结规律，总结添加元素，删除元素，获得元素（遍历）的通用方法和一些特殊的方法

1． 什么是集合？

将多个对象合在一起变成一个统一的对象，然后通过这个统一的对象来实现对多个对象的管理（存储，检索，操作，传输数据）。在数组里要进行这样的操作，可以会写很多算法，但在集合里，只需要调用其中的方法就可以了。集合也可以对其中的元素进行操纵，增加、删除、更改。同时，我们可以把存储之后的数据用于传输。这体现了JAVA里的封装思想。我们利用集合的功能特点，把我们对底层数据的操作封装起来，这样可以让程序的主要精力放在业务处理上，而不是对底层数据的操作上。

为什么要用集合？数组不能动态改变长度，操作不方便

什么是集合框架？Java Collection Framework (JCF)

–提供用于管理对象集合的接口和类

– 包括接口、实现和算法

2． 了解集合框架的具体优点并通过以后的代码能够深刻认识

减少编程工作量 - 它可以提供有用的数据结构和算法，从而使程序员不必自己编写。

提高性能 - 它可以提供有用的数据结构和算法的高性能实现。因为每个接口的不同实现是可以互换的，所以可通过交换实现方便地调整程序。并且集合算法是经过验证的，所以效率也是很高的。

实现无关 API 间的互操作 - 它可以建立一种公用语言，用于来回传递。在前面我们知道通过一个方法可以实现一个对象传递，但如果是一组对象传递怎么办呢？就可以使用集合进行传递，先把对象放在集合中，再把对象作为传输。

减少学习 API 所需的劳动 - 用户没有必要学习多个不同的集合 API。 因为集合框架实现了继承关系，所有有很大一部分共性。

Java基础知识点归纳

Java基础知识点归纳

Word文档

1 / 5

Java基础知识点归纳

Java基础学问点归纳

对于刚刚接触Java的人，java基础学问技术点繁多，那么yjbys我为大家汇总最全java学问点如下，仅供大家参考学习!

1. JVM相关(包括了各个版本的特性)

对于刚刚接触Java的人来说，JVM相关的学问不愿定需要理解很深，对此里面的概念有一些简洁的了解即可。不过对于一个有着3年以上Java阅历的资深开发者来说，不会JVM几乎是不行接受的。

JVM作为java运行的基础，很难信任对于JVM一点都不了解的人可以把java语言吃得很透。我在面试有超过3年Java阅历的开发者的时候， JVM几乎就是一个必问的问题了。当然JVM不是唯一确定技术能力好坏的面试问题，但是可以佐证java开发能力的高低。

在JVM这个大类中，我认为需要把握的学问有：

JVM内存模型和结构

GC原理，性能调优

调优：Thread Dump， 分析内存结构

class 二进制字节码结构， class loader 体系 ， class加载过程 ， 实例创建过程

方法执行过程：Java各个大版本更新提供的新特性(需要简洁了解)

2. Java的运行(基础必备)

这条可能出看很简洁，java程序的运行谁不会呢?不过很多时候， 我们只是单纯通过IDE去执行java程序，底层IDE又是如何执行java程序呢?很多人并不了解。

这 个学问点是最最基本的java开发者需要把握的，初学java，第一个确定是教你如何在指令行中执行java程序，但是很多人一旦把java学完 了，IDE用上了，就把这个都忘了。为什么强调要知道这个呢，知道了java最纯粹的启动方式之后，你才能在启动出问题的时候，去分析当时启动的名目多 少，执行命名如何，参数如何，是否有缺失等。 这样有利于你真正开发中去解决那些奇诧异怪的可能和环境相关的问题。

java数据结构知识点集合

java数据结构知识点集合

Java工具包提供了强大的数据结构。在Java中的数据结构主要包括以下几种接口和类：

•枚举（Enumeration）

•位集合（BitSet）

•向量（Vector）

•栈（Stack）

•字典（Dictionary）

•哈希表（Hashtable）

•属性（Properties）

以上这些类是传统遗留的，在Java2中引入了一种新的框架-集合框架(Collection)，我们后面再讨论。

枚举（Enumeration）

枚举（Enumeration）接口虽然它本身不属于数据结构,但它在其他数据结构的范畴里应用很广。 枚举（The Enumeration）接口定义了一种从数据结构中取回连续元素的方式。

例如，枚举定义了一个叫nextElement 的方法，该方法用来得到一个包含多元素的数据结构的下一个元素。

关于枚举接口的更多信息，请参见枚举（Enumeration）。

位集合（BitSet）

位集合类实现了一组可以单独设置和清除的位或标志。1

该类在处理一组布尔值的时候非常有用，你只需要给每个值赋值一"位"，然后对位进行适当的设置或清除，就可以对布尔值进行操作了。

关于该类的更多信息，请参见位集合（BitSet）。

向量（Vector）

向量（Vector）类和传统数组非常相似，但是Vector的大小能根据需要动态的变化。

和数组一样，Vector对象的元素也能通过索引访问。

使用Vector类最主要的好处就是在创建对象的时候不必给对象指定大小，它的大小会根据需要动态的变化。

关于该类的更多信息，请参见向量(Vector)

（Stack）

栈（Stack）实现了一个后进先出（LIFO）的数据结构。

你可以把栈理解为对象的垂直分布的栈，当你添加一个新元素时，就将新元素放在其他元素的顶部。

当你从栈中取元素的时候，就从栈顶取一个元素。换句话说，最后进栈的元素最先被取出。

关于该类的更多信息，请参见栈（Stack）。

java面试核心知识点整理 pdf

java面试核心知识点整理 pdf

在Java面试中，以下是一些核心知识点：

Java基础：包括Java的基本语法、面向对象的概念（如类、对象、继承、

多态、封装等）、异常处理、集合框架（如List、Set、Map等）、泛型、流和Lambda

表达式等。

Java语言特性：包括自动拆装箱、枚举、注解、泛型擦除、Lambda表达式

和Stream API等。

Java标准库：包括Java标准库中常用的类和接口，如String、StringBuffer、

StringBuilder、Math、Random等。

数据结构和算法：包括数组、链表、栈、队列、二叉树等数据结构，以及排

序算法（如冒泡排序、选择排序、插入排序等）、查找算法（如二分查找）等。

Java虚拟机（JVM）：包括JVM的工作原理、内存模型、垃圾回收机制以及

性能调优等。

Java多线程：包括线程的概念、线程的创建和启动方式、线程同步和锁机制

（如synchronized关键字和ReentrantLock）等。

Java网络编程：包括TCP/IP协议和UDP/IP协议的基础知识，以及Socket

编程等。

Java Web开发：包括Web应用程序的基本概念，Servlet和JSP的原理和应

用，MVC模式等。

Java框架：如Spring的核心概念，AOP的实现方式，以及MyBatis的使用

等。

设计模式：如工厂模式、单例模式、观察者模式等常见的设计模式的实现和

应用场景。

以上是Java面试中常见的核心知识点，掌握这些知识点有助于提高面试通

过率。