首页  流程图  详情

05_集合

2024-05-23 21:52:05   4  举报





为你推荐

查看更多



05-2

Java集合源码剖析,ArrayList，linkedlist，hashmap，stack，linkedhashmap等

ArrayList

linkedlist

hashmap

原理源码

作者其他创作

大纲/内容

LinkedHashMap

6 b

100

压入

fail-fast机制

109

110

扩容1倍

l 代表的是上一个node把上一个node的next指针指向新增的这个node

null

张三

在数组下标设置值elementData[size++] = e

3 e

4 现在指向

7 null

first不动

108

iteam

引用

Node

elementAt(len - 1);

红黑树插入node

add()

5 c

扩容原来的一半，总大小是原来的1.5倍

first

120

put的对象的hash和key都和原来index位置上的node一直，就进行覆盖，替换旧值

LinkedList

Set 底层完全基于HashMap，Set直接set一个只有key和空value的node。linkedHashSet 基于linkedHashMap实现，用链表记录顺序。TreeSet基于TreeMap实现，可以实现key自然排序和自定义排序

130

转为红黑树

0 a

当前值插入后的数组长度大于插入之前的长度

1 f

直接将node PUT到index位置

color = BLACK

last

l.next

初始化大小16和负载因子0.75f

2 g

hash降低冲突新算法(h = key.hashCode()) ^ (h >>> 16)通过高16位和低16位异或，更好的获取hash特征，让数据更加分散的分布在map数据结构中

删除弹出的数据，也就是最后加入的对象removeElementAt(len - 1)

put

在初始化Iterator里面的 expectedModCount 就会被初始化为当时的modCount，也就是当前的修改次数。如果迭代到某一个node发现modCount != expectedModCount 就会抛出ConcurrentModificationException，并发修改的异常，终止迭代，这个机制就叫做fail fast异常

压入栈顶，也就是最后一个，可能会扩容

4 d

peek()找出对象

hash寻址通过位运算&操作来代替取模length & hash每次扩容，数组的大小就是2的n次方，保证定位到某个index中去

第2次

split 数据重排

获取指定位置的数据：（它已经尽力了）get(5) 获取第5个元素，他会做一个“于” index > (size >> 1) size >> 1获取到当前链表的长度的一半如果index在上半段，就从头开始向后找；反之，就从链表的尾部开始向前查找。

2 f

ArrayList

resize()

基本原理：左小右大但是红黑树是有旋转，变色和动态调整整个tree的平衡机制，是一个平衡的二叉查找树

pop()弹出对象

之前指向

链表长度是否>8

111

left

数据结构：红黑树性能：O（logn）， hashMap在不考虑冲突的情况下是O（1）特点：根据key的自然顺序排序或自己实现comparator场景：大量统计或者增删改查的KV场景，希望有顺序的KV场景。（非插入顺序）

1 g

4 d

初次

是否treeNode

head

数据结构：链表 + Map（数组+链表+红黑树），是HashMap的高级封装。场景：需要记录顺序的KV集合亮点：继承HashMap，重写了newNode方法，在新增完node后，执行了linkNodeLast来记录顺序。链表的核心对象Entry继承了HashMap.Node。增加了before和tail两个指针默认按插入顺序，也可以设置true/false 改变顺序为访问书顺序

tail

push()压入对象

链表

新插入的node

指向

依然指向

right

结构：数组+链表+红黑树使用场景：高性能无序非多线程 KV存储需求扩容：达到（负载因子*长度）后，进行扩容，扩容后，大小和负载因子都翻一倍亮点：hash高低位异或，取特征进行hash寻址，减少冲突通过位操作&，代替取模%，提高性能控制链表长度，大于8直接转换为红黑树，get的时间复杂度从O(n)变为O(logn)

peek()elementAt(len - 1);

Stack

是否红黑树

index位置是否有Node对象

5 指向

扩容：int newCapacity = oldCapacity + (oldCapacity >> 1);亮点：位移扩容，增加到原来容量的1.5倍右位移1，相当于capacity/2

Map（数组+链表+红黑树）

栈，stack继承vector，实现栈数据结构：数组特点：先进后出扩容：和ArrayList扩容机制一样，但是默认扩大原来的2倍，而不是1.5

parent

HashSet LinkedHashSet TreeSet

当前node.next

李四