-- List
-- Set
-- Queue
-- Map
-- 需要根据键值对获取元素则采用Map接口下的集合
-- 只需存放元素则采用Collection接口下的集合
当将一个新对象加入HashSet时,HashSet首先会计算它的hashcode
值来确定该元素应当存入的位置,同时还会与其余要加入的对象的hashcode
值进行对比,如果没有重复,则加入元素;否则HashSet会调用equals()
方法来判断二者是否完全相同,若相同则添加失败。
add()
、remove()
、contains()
。add()
、remove()
、contains()
。HashMap | HashSet |
---|---|
实现了Map接口 | 实现了Set接口 |
调用put()方法添加元素 | 调用add()方法添加元素 |
通过键值计算hashcode | 通过成员对象计算hashcode实现了Set接口 |
null
的key与value,但为null
的key只允许有一个,而value可以有多个;HashTable不允许有null
的key与value,否则会抛出NullPointerexception
2n + 1
。二者都继承自AbstractMap
,但TreeMap还实现了NavigableMap
与SortedMap
接口,使得TreeMap还拥有对集合内元素进行搜索以及根据键值进行排序的能力。
二者之间的区别主要体现在了实现线程安全的方式上。
Segment
分段分割,每一段上都会有一个同步锁。当多线程访问同一桶中不同段上的数据时就不会存在锁竞争的问题。在JDK 1.8时则摒弃了Segment分段分割的概念,ConcurrentHashMap实现线程安全的方式改变为synchronized + volatile/CAS
。当存入新的元素时,首先会判断当前数组是否为空,如果为空则通过volatile + CAS
进行初始化,随后将元素存入;否则会根据元素的hashcode获取元素应当存入的位置,在判断该处是否为空。如果为空则通过CAS
进行添加,否则通过synchronized
对整个数组加锁,然后在进行元素的添加或者替换操作。最后再判断是否触发数组结构转红黑树结构。HashTable实现线程安全则是通过synchronized
关键字来实现,但他采用的是同一把锁,也就是说,当一个线程在访问同步方法时,其余线程会被阻塞,导致效率低下。Object数组
,而LinkedList底层则是一个双向链表
O(1)
,其余情况下为O(n)
,因为要移动到指定位置再进行操作HashMap的底层数据结构是数组 + 链表。当存入新元素时,会通过该元素的hashcode值计算应当存入的位置。若为空,则直接存入;否则会对二者的key值进行比较,若想等则替换;不等则通过拉链法将元素存入
HashMap的底层数据结构转变为了数组 + 链表/红黑树的形式。与上面的区别在于,再添加元素时,会判断链表的长度是否超过了8
,如果超过了8,则会将数组结构转变为红黑树结构,便于查找;在此之前若数组长度不超过64
,会进行resize
扩容,扩容后的数组长度为原数组长度的2
倍。
HashMap是否触发resize扩容与两个因素有关:load factor负载因子(默认为0.75,从源码注释中可知这是时间上的最优解)、capacity初始容量。
当存入元素后使得HashMap中数组的长度大于负载银子与初始容量的乘积时便会触发resize扩容。主要包括两个阶段:
rehash
到新的数组中注:在创建数组时若要指定数组长度,最好使要指定的数组长度小于2^n与负载因子的乘积。则n即为需要指定的数组长度。例:需要创建的数组长度为1000,则应当new HashMap(1000);,但理论上采用new HashMap(1024);更为合适。然而,1024 * 0.75 < 1000,为了避免resize问题,需要指定为new HashMap(2048);
因为在计算存入元素位置时,采用的公式是hashcode(key) % n
,其中n
为数组的长度。而%
运算的效率低,为了提高计算效率,减少hash碰撞的概率,可以利用&
运算来代替,而如此做的条件便是n是2的整数幂,且二者之间的关系为hashcode(key) % n = hashcode(key) & (n - 1)
set
与list
连接事件、读写事件
;NIO主要有三大核心部分:Channel通道、Buffer缓冲区、Selector监视器
。传统IO基于字节流与字符流进行操作;NIO则是基于Channel与Buffer进行操作。数据总是从Channel通道中读取到Buffer缓冲区中,或者从Buffer缓冲区中写入到Channel通道中。Selector监视器则用于监听多个通道的事件,如:连接打开、数据到达等。字符流是由Java虚拟机将字节转换得到的,而这个过程非常耗时,同时如果编码类型未知就会出现乱码问题,因此IO流就提供了一个直接操作字符的接口
是一种用来处理对象流的机制,而所谓的对象流就是将对象的内容进行流化,可以对流化后的对象进行对写操作,也可将流化后的对象传输于网路之间。序列化是为了解决在对象流进行读写操作时所引发的问题
将需要被序列化的类实现Serializable
接口,该接口没有需要实现的方法,只是用来标注该对象可被序列化,然后使用一个输出流(如:FileOutputStream
)来构造一个ObjectOutputStream
(对象流)对象,接着使用ObjectOutputStream
对象的writeObject(Object obj)
方法就可以将参数为obj
的对象保存,若要恢复则可以使用输入流
```mermaid graph LR 红黑树的特征--> 每个节点都是红色或者黑色的 红黑树的特征--> 根节点是黑色的 红黑树的特征--> 每个叶子节点都是黑色的/指向空的叶子节点 红黑树的特征--> 如果一个叶子节点是红色,那么其子节点必须都是黑色的 红黑树的特征--> 从一个节点到该节点的子孙节点的所有路径上包括相同数目的黑节点