首页  思维导图  详情

java集合源码分析

2021-07-11 09:08:44   0  举报





AI智能生成

java集合源码分析

Java集合

作者其他创作

大纲/内容

arrayList

介绍

ArrayList 继承了AbstractList，实现了List。它是一个数组队列，提供了相关的添加、删除、修改、遍历等功能

ArrayList 实现了RandmoAccess接口，即提供了随机访问功能。RandmoAccess是java中用来被List实现，为List提供快速访问功能的

ArrayList 实现了Cloneable接口，即覆盖了函数clone()，能被克隆。

ArrayList 实现java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输。

类成员变量介绍

DEFAULT_CAPACITY=10

当用户指定ArrayList的容量为0时，默认容量为10

elementData

Object[]类型数组

size

动态数组的实际大小

ArrayList方法

查找

indexOf（正序查找，for循环从前往后遍历）

lastIndexOf（正序查找，for循环从后往前遍历）

删除

E remove(int index)

boolean remove(Object o)

void fastRemove(int index)

增加

关于ArrayList的一些问题

简单介绍下ArrayList

ArrayList是以数组实现，可以自动扩容的动态数组，当超出限制的时候会增加50%的容量，用ystem.arraycopy()复制到新的数组，因此最好能给出数组大小的预估值。默认第一次插入元素时创建大小为10的数组。arrayList的性能很高效，不论是查询和取值很迅速，但是插入和删除性能较差，该集合线程不安全。

ArrayList的自动扩容怎么样实现的

每次在add()一个元素时，arraylist都需要对这个list的容量进行一个判断。如果容量够，直接添加，否则需要进行扩容。在1.8 arraylist这个类中，扩容调用的是grow()方法

在核心grow方法里面，首先获取数组原来的长度，然后新增加容量为之前的1.5倍。随后，如果新容量还是不满足需求量，直接把新容量改为需求量，然后再进行最大化判断

通过grow()方法中调用的Arrays.copyof()方法进行对原数组的复制，在通过调用System.arraycopy()方法进行复制，达到扩容的目的

ArrayList的构造方法过程

无参的构造方法先将数组为空，第一次加入的时候然后扩充默认为10

有参的构造方法，直接创建这个数组

传入集合元素，先将集合元素转换为数组，把不是object的数组转化为object数组

ArrayList可以无限扩大吗

不能，大约8G,因为在ArrayList扩容的时候，有个界限判断。 private static final int MAX_ARRAY_SIZE = 2147483639，2的31次方减一然后减8,-8 是为了减少出错的几率，虚拟机在数组中保留了一些头信息。避免内存溢出

程序

数据结构

数组

底层结构：采用一段连续的存储单元来存储数据

特点：查询快O(1)，插入慢O(N)

链表

底层结构：是一种物理存储单元上非连续、非顺序的存储结构

特点：插入、删除时间复杂度O(1),查找遍历时间复杂度O（N），插入块，查询慢

算法

哈希算法（散列）

简介

将任意长度（key）通过散列算法变换成固定长度的key（地址），通过这个地址进行访问的数据结构

原理

对字符串算出ascii码，先进行相加，再进行mod（取模），算出哈希表的下标

取模的原因：节省数组的空间

问题

哈希冲突（哈希碰撞）

两个字符串的ascii码相同

解决方案

开放地址法

发生冲突，继续寻找下一块未被占用的存储地址

再散列函数法

链地址法

数组+链表

hashMap

jdk1.7

底层结构

数组+链表

问题

1、链表存储的结构，查询效率慢

jdk1.8

参数

链表转红黑树的要求

1、数组长度>=64

2、链表长度>=8

若链表长度>=8,但数组长度<64时，进行数组扩容操作

问题：为什么不直接设置为红黑树？

红黑树插入时有可能会发生左旋或者右旋，数据会交换位置,所以不推荐直接上红黑树

默认大小

阈值

0.75

当前数组长度>数组.size*0.75,会触发扩容机制

扩容

长度左移动1位，使用位运算

hashCode()

对字符串进行ascii码取值

通话和重地的hashCode()一样

hash

h=key.hashCode())^(h>>>16)

让h的高16位与低16位进行异或运算，减少hash冲突的概率

位运算

在Java中，整数的二进制是以补码的形式存在的

整数32位,正数符号为0，负数符号为1

十进制转为二进制

正数

原码=反码=补码

负数

原码

十进制转二进制不足32位的，最高位补符号位，其余补零

反码

补码

get

为什么要保证capacity是2的次幂呢？

1、需要在node数组中查询下标

2、因为n永远是2的次幂，所以n-1通过二进制表示，永远都是尾端以连续1的形式表示（00001111，00000011）
当(n-1)和hash做与运算时，会保留hash中后x位的1

好处

&运算速度快，至少比%取模运算块

能保证索引值肯定在capacity中，不会超出数组长度

(n-1)&hash，当n为2次幂时，会满足一个公式：(n-1)&hash=hash%n

put

大体流程

1、根据key通过哈希算法和数组长度-1进行与运算得到数组下标

2、如果数组下标位置元素为空，则将key和value封装为Entry对象（jdk7是Entry对象，jdk8是Node对象）并放入该位置

3、如果数组下标不为空

jdk7

1、先判断是否需要扩容

2、如果不用扩容就生成Entry对象，并使用头插法添加到当前位置的链表中

jdk8

当前位置上的Node类型为红黑树

1、将key和value封装为一个红黑树节点并添加进红黑树

2、在过程中会判断红黑树中是否存在此key，存在的话更新value

当前位置上的Node类型为链表

1、将key和value封装为一个链表Node并通过尾插法插入到链表的最后位置去

2、尾插法要遍历链表，在遍历过程中会判断是否存在当前key，存在则更新value

3、遍历完成后，将链表新Node插入到链表中去，判断是否链表节点超过8

4、若超过8调用treeifyBin()方法，会判断数组长度是否大于64，若小于则执行resize操作，若大与则转换为红黑树

64的容量之前，因为容量比较小，在数据量比较多的时候，很容易出现hash冲突，直接扩容的效率比树化并不差，并且还可以减少后续元素落在同一个index的概率

插入链表或红黑树后，才会判断是否需要扩容

tableSizeFor

1、cap-1：是为了传进来的本身就是2的幂次方整数这种情况不减一会返回本身的两倍，减一返回本身

2、对n右移1,2,4,8,16进行或操作，将所有二进制位都变为1，最后再加上1，就得出了2的幂次方大小

concurrentHashMap

jdk1.7

无参构造方法

//空参构造
publicConcurrentHashMap(){
//调用本类的带参构造
//DEFAULT_INITIAL_CAPACITY=16
//DEFAULT_LOAD_FACTOR=0.75f
//intDEFAULT_CONCURRENCY_LEVEL=16
this(DEFAULT_INITIAL_CAPACITY,DEFAULT_LOAD_FACTOR,DEFAULT_CONCURRENCY_LEVEL);
}

数据结构

Segment[]，默认长度为16

每个Segement保存HashEntry[]，默认长度为2

Segment

继承了ReentrantLock，是一个锁对象，实现了分段锁机制

HashEntry

初始容量为32

我们添加的元素，是存入对应的Segment中的HashEntry[]中。所以ConcurrentHashMap中默认元素的长度是32个，而不是16个

method

hash(Object k)

h ^=k.hashCode()，在经历一系列比较复杂的位运算，获取hash值

注意：键值对都不允许为null，否则报空指针异常