额,首先,因为基本都是左抄抄右抄抄,我都基本忘了从哪copy过来的了,只是为了方便自己复习,如果你看到有你的内容,请回复链接,我会注明转载。
Collection 接口
Map 接口
Map集合类 | key为null | Value为null |
---|---|---|
HashMap | √ | √ |
TreeMap | × | √ |
ConcurrentMap | × | × |
有序,可重复
位置访问方法
void add(int index, E e) // 将元素e插入到index处
boolean addAll(int index, Collection<? extends E> c)// 将集合c中所有元素插入到List集合的index处
E get(int index) // 返回index处的元素
E remove(int index) // 移除index处的元素
E set(int index, E e) // 将index处元素替换成e,并返回替换后的元素
查找
int indexOf(Object o) // 返回对象o再List中出现的位置
int lastIndexOf(Object o) // 返回对象o在List中最后一次出现的位置
范围查看
List subList(int fromIndex, int toIndex)//返回从fromIndex(包括)到toIndex(不包括)处所有元素集合组成的子集合
ListIterator<E> listIterator() // 返回List的ListIterator,初始位置索引为0
ListIterator<E> listIterator(int index) // 返回List的ListIterator,初始位置索引为index
ListIterator新增的方法
public interface ListIterator<E> extends Iterator<E> {
void add(E e); // 在游标 前面 插入一个元素(注意,是前面)
boolean hasPrevious(); // 判断游标前面是否有元素
int nextIndex(); // 返回游标后边元素的索引位置,初始为 0
E previous(); // 返回游标前面的元素,同时游标前移一位。游标前没有元素就报 java.util.NoSuchElementException 的错
int previousIndex(); // 返回游标前面元素的位置,初始时为 -1,同时报 java.util.NoSuchElementException 错;
void set(E e); // r更新迭代器最后一次操作的元素为 E,也就是更新最后一次调用 next() 或者 previous() 返回的元素。当没有迭代,也就是没有调用 next() 或者 previous() 直接调用 set 时会报 java.lang.IllegalStateException 错
}
迭代器
public class Demo {
public static void main(String[] args) {
ArrayList<String> arr = new ArrayList<>();
arr.add("a");
arr.add("b");
arr.add("c");
arr.add("d");
Iterator<String> iterator = arr.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
}
}
List实现
List接口的一个实现类,底层是数组
初始空间:默认10。复制其他数组时,开辟该数组空间的110%
空间扩展:原数组大小+原数组大小>>1
底层是双向循环链表
写时复制,适用于读多写少
读写分离
写操作在一个复制的数组上进行,读操作还是在原始数组中进行,读写分离,互不影响。
写操作需要加锁,防止并发写入时导致写入数据丢失。
写操作结束之后需要把原始数组指向新的复制数组。
get:index已知,获取index位置的元素
contains:index未知,查找某一元素
无序,不可重复
6个实现类,2个接口
map.keySet().iterator()
初始化
enumset为抽象类,不可直接new
底层使用RegularEnumSet(long-64),或者JumboEnumSet(long数组)如果枚举值个数小于等于64,则静态工厂方法中创建的就是RegularEnumSet,大于64的话就是JumboEnumSet。
静态构造函数
<E extends Enum<E>> EnumSet<E> of(E first, E... rest)
// 创建包含指定元素的集合
<E extends Enum<E>> EnumSet<E> range(E from, E to)
//初始集合包括枚举值中指定范围的元素
<E extends Enum<E>> EnumSet<E> allOf(Class<E> elementType)
// 创建一个初始包含elementType中的所有元素的集合
<E extends Enum<E>> EnumSet<E> noneOf(Class<E> elementType)
// 创建一组元素类型,初始值为空
适用于求 交集、并集、补集
并发:不同步、线程不安全、迭代器快速失效
只有两棵子树,度≤2
二叉树的性质
二叉树的类型
二叉树的类型
遍历
前序遍历:A B C D E F G H K
中序遍历:B D C A E H G K F
后序遍历:D C B H K G F E A
分析如下
插入图解:
查找图解
键值对,不继承Collection,键唯一
Map方法
Map实现
容量默认16
HashMap的bucket 数组大小一定是2的幂,若不是,寻找最近的的2的幂
为了减少hash值的碰撞,需要实现一个尽量均匀分布的hash函数,在HashMap中通过利用key的hashcode值,来进行位运算
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
// 序列号
private static final long serialVersionUID = 362498820763181265L;
// 默认的初始容量是16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认的填充因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 当桶(bucket)上的结点数大于这个值时会转成红黑树
static final int TREEIFY_THRESHOLD = 8;
// 当桶(bucket)上的结点数小于这个值时树转链表
static final int UNTREEIFY_THRESHOLD = 6;
// 桶中结构转化为红黑树对应的table的最小大小
static final int MIN_TREEIFY_CAPACITY = 64;
// 存储元素的数组,总是2的幂次倍
transient Node<k,v>[] table;
// 存放具体元素的集
transient Set<map.entry<k,v>> entrySet;
// 存放元素的个数,注意这个不等于数组的长度。
transient int size;
// 每次扩容和更改map结构的计数器
transient int modCount;
// 临界值 当实际大小(容量*填充因子)超过临界值时,会进行扩容
int threshold;
// 加载因子
final float loadFactor;
}
构造
public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder)
Hashmap实体中添加before,after(双向链表)实现有序访问
LinkedHashMap添加head、tail(头指针和尾指针)
accessOrder
accessOrder: 为 false按插入顺序访问;为true,按访问顺序访问(LRU算法)
LRU实现
protected boolean removeEldestEntry(Map.Entry<K,V> eldest)
可以重载该方法自己定义策略
是否线程安全
不安全,迭代器快速失效
实现原理
1.7
采用乐观读+分段锁实现 来 实现ConcurrentMap
ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成
Segment 实现了 ReentrantLock
1.8
采用CAS和synchronized来保证并发安全。数据结构跟HashMap1.8的结构类似,数组+链表/红黑二叉树。synchronized只锁定当前链表或红黑二叉树的首节点,这样只要hash不冲突,就不会产生并发,效率又提升N倍
其他
默认容量16
在获取size()会导致全锁,开销大
构造函数提供并发级别控制
额,再次强调一次,因为基本都是左抄抄右抄抄,我都基本忘了从哪copy过来的了,只是为了方便自己复习,如果你看到有你的内容,请回复链接,我会加上去。
原文:https://www.cnblogs.com/zzfan/p/11594986.html