ArrayList 使用一个内置的数组来存储元素,这个数组的起始容量为 10。当数组需要增长时,新的容量按以下公式获得:新容量=旧容量*3/2+1,也就是说每次容量大概增长 50%。这就意味着,如果你有一个包含大量元素的 ArrayList 对象,那么最终将会有很大的空间被浪费掉,这个浪费由 ArrayList 本身的工作方式导致。
HashMap 的初始容量为什么设置为16
首先,length 为 2 的整数次幂的话,h&(length-1) 就相当于对 length 取模,这样便保证了散列的均匀,同时也提升了效率;其次,length 为 2 的整数次幂的话,为偶数,这样 length-1 为奇数,奇数的最后一位为 1,这样便保证了 h&(length-1) 的最后一位可能为 0,也可能为1,即与后的结果可能为偶数也可能为奇数,这样便可以保证散列的均匀性,如果 length 为奇数,那么 length-1 则为偶数,偶数的最后一位为0,这样在进行与运算时,最后一位必然为 0。也就是说与运算后得到的全是偶数,这样 hash 后 entry 都会被分配到偶数位上,,这样便浪费了一半的空间。因此,length 取 2 的整数倍是为了使不同的 hash 值发生碰撞的概率减小,这样就能是元素在哈希表中均匀分布
java 中的异常结构
- Error 与 Exception
Error 是程序无法处理的错误,比如 OutOfMemoryError、ThreadDeath 等。这些异常发生时,JVM 一般会选择线程终止
Exception 是程序本身可以处理的异常,这种异常分两大类:运行时异常和非运行时异常。程序中应当尽可能去处理这些异常。
- 运行时异常和非运行时异常
运行时异常都是 RuntimeException 类及其子类异常,如 NullPointerException、IndexOutofBoundsException 等,这些异常是不检查异常,程序可以选择捕获处理,也可以不处理。这些异常一般是由于程序逻辑异常引起的,程序应该从逻辑角度尽可能避免这类异常的发生
非运行时异常是 RuntimeException 以外的异常,是受检查的异常,其必须被 try{}catch 语句块所捕获,或者在方法签名里通过 throw 语句声明。受检查的异常必须在编译时被捕捉处理。如果不处理,程序就不能编译通过。如 IOException、SQLException 等以及用户自定义的 Exception 异常,一般情况下不自定义受检查异常。
concurrentHashMap 的实现
concurrentHashMap的实现:https://www.cnblogs.com/liaoweipeng/p/6343674.html
concurrentHashMap 的存在意义
目前学习到的散列表中 HashMap 是线程不安全的,HashTable 是线程安全的,但是 HashTable 的效率太低下了,所有访问 HashTable 的线程都要竞争同一个锁,当一个线程访问 HashTable 的同步方法时,其他线程访问 HashTable 的同步方法时可能进入阻塞或轮询状态。如线程 A 利用 put 方法添加元素,线程 B 不但不能使用 put 方法添加元素,并且也不能使用 get 方法获取元素,所以竞争越激烈效率越低。为了弥补散列表在线程安全下的效率问题,故而有了 currentHashMap。
实现原理
concurrentHashMap 使用了被称为 segment(默认创建16个并发的segment) 的分段锁技术,它既类似于 HashMap 的结构,即内部有一个 Entry 数组,数组中每个元素又是一个链表;同时又是一个 ReentranLock(segment 继承了 ReentranLock)。ConcurrentHashMap 中的 HashEntry 相对于 HashMap 中的 Entry 有一定的差异:
- HashEntry 中的 value 以及 next 都被 volatile 修饰,这样可以在多线程读写中保持可见性。
使用分段锁后,所有的资源被分成了多个部分并分别锁定,这样多线程在进行不同 segment 的资源写时不用竞争同一把锁,提升了效率
一个 concurrentHashMap 主要包含三大结构:整个 Hash 表,segment(段),HashEntry(节点)。每个 segment 就相当于一个 hashTable 。每个 hashEntry 代表 hash 表中的一个节点,在其定义的结构中可以看到,除了 value 值和 next 值没有定义为 final,其余都定义为 final 型。concurrentHashMap 读不需要加锁
concurrentHashMap 的 get 方法
concurrentHashMap 在多线程上的高效不仅体现在他写的分段锁上,同时也体现在他的 get 操作上。
先来看一下他的 get 方法
1 | public V get(Object key) { |
它没有使用同步控制,先利用 segmentFor 方法找到 segment,然后直接交给 segment 去找,再看 segment 中的 get 方法
1 | V get(Object key, int hash) { |
它也没有使用锁来同步,只是判断获取的 entry 的 value 是否为 null,为 null 时才使用加锁的方式再次去获取
没有锁同步的话,靠什么保证同步呢?我们来一步步分析:
第一步,先判断 count 是否等于 0,count 变量表示 segment 中 Entry 的数量,如果为 0 就不用找了
假设这个时候恰好另一个线程 put 或者 remove 了这个 segment 中的一个 entry,会不会导致两个线程看到的 count 值不一样呢?
看一下 count 变量的定义:transient volatile int count
;
它使用了 volatile 来修改。Java5 之后,JMM 实现了对 volatile 的保证:对 volatile 域的写入操作 happen-before 于每一个后续对同一个域的读写操作
所以,每次判断 count 变量的时候,即使恰好其他线程改变了segment 也会体现出来
第二步,获取到该 key 所在 segment 中的索引地址,如果该地址有相同的 hash 对象,顺着链表一直比较下去找到该 entry,当找到该 entry 的时候,先做一次比较:if(v != null)
这个时候,另一个线程恰好新增/删除了 entry,或者改变了 entry 的 value,会如何?
先来看一下 HashEntry 的结构:
1 | static final class HashEntry<K,V> { |
除了 value,其他成员都是 final 修饰的,也就是说 value 可以被改变,其他都不可以改变,包括指向下一个 HashEntry 的 next 也不能被改变,也就是说新增的 entry 只会出现在链表头
- 在 get 代码的①和②之间,另一个线程新增了一个 entry,如果另一个线程新增的这个 entry 又恰好是我们要 get 的,那么事情就比较微妙了
如果另一个线程刚好 new 这个对象时,当前线程来 get 它,因为没有同步,那么当前线程 get 到的可能是一个尚未完全构造好的对象引用
这里和 DCL 问题相同,没有锁同步的话,new 一个对象对于多线程看到这个对象的状态是没有保障的,这里同样有可能一个线程 new 这个对象的时候还没有执行完构造函数就被另一个线程得到这个对象的引用
所以才需要判断一下:if (v != null)
如果是一个不完整的对象,则使用锁的方式再 get 一次。这里也是 concurrentHashMap 为什么不接受 null 值的原因。如果加入 null 值则无法有效区分未完全加载的对象和本身为 null 的对象。
- 在 get 代码的 ① 和 ② 之间,另一个线程修改了 entry 的 value
value 是 volatile 修饰的,可以保证读取时获取到的是修改后的值
- 在 get 代码的 ① 之后,另一个线程删除了一个 entry
假设我们的链表元素是:e1-> e2 -> e3 -> e4 我们要删除 e3这个entry,因为HashEntry中next的不可变,所以我们无法直接把e2的next指向e4,而是将要删除的节点之前的节点复制一份,形成新的链表。
根据 hash 值定位 segment 时会调用 segmentfor 方法,返回相应的 segment 在数组中的下标。segment 的 get 操作实现非常简单高效
Java 中的内部类
1.为什么使用内部类
使用内部类最吸引人的原因是:每个内部类都能独立地实现一个接口,所以无论外围类是否已经实现了某个接口,对于内部类都没有影响
1.1使用内部类最大的优点就在于它能够非常好的解决多重继承的问题,使用内部类还可以为我们带来如下特性:
内部类可以用多个实例,每个实例都有自己的状态信息,并且与其他外围对象的信息相互独立
在某个外围类中,可以让多个内部类 以不同的方式实现同一个接口,或者继承同一个类
创建内部类对象的时刻并不依赖于外部类对象的创建
内部类提供了更好的封装,除了外围类,其他类都不能访问
2.内部类分类
2.1成员内部类
Inner 类定义在 outer 类的内部,相当于 outer 类的一个成员变量的位置,Inner 类可以使用任意访问控制符
Inner 类中定义的 show() 方法可以直接访问 outer 类中的数据,而不受访问控制符的影响
定义成员内部类后,必须使用外部类 对象来构建内部类对象,而不能直接去 new 一个内部类对象
- 即:内部类 对象名 = 外部类实例.new 内部类()
编译包含内部类的程序后会包含两个 .class 文件:outer.class,outer$Inner.class
成员内部类中不能存在任何 static 的变量和方法,可以定义常量
因为非静态内部类是要依赖于外部类的实例,而静态对象和方法是不依赖于对象的,仅与类相关
简而言之:在加载静态域时,根本没有外部类,所以在非静态内部类中不能定义静态域或方法,否则编译不通过;非静态内部类的作用域是实例级别
常量是在编译器就确定的,放到所谓的常量池了
注意:
外部类是不能直接使用内部类的成员和方法的,可先创建内部类的对象,然后通过内部类的对象来访问其成员变量和方法
如果外部类和内部类具有相同的成员变量或方法,内部类默认访问自己的成员变量或方法,如果要访问外部类的成员变量,可以使用 this关键字,如: outer.this.name
2.2静态内部类:是 static 修饰的内部类
静态内部类不能直接访问外部类的非静态成员,但可以通过
new 外部类().成员
的方式访问如果外部类的静态成员和内部类的成员名称相同,可通过
类名.静态成员
访问外部类的静态成员如果外部类的静态成员和内部类的成员名称不同,则可通过成员名直接调用外部类的静态成员
创建静态内部类的对象时,不需要外部类的对象,可以直接创建
内部类 对象名 = new 内部类()
2.3方法内部类:访问仅限于方法内或者该作用域内
方法内部类就像是方法里面的一个局部变量一样,是不能有 public、protected、private 以及 static 修饰符的
只能访问方法中定义的 final 类型的局部变量,因为:当方法被调用完成后局部变量就已经消亡了。但内部类对象可能还存在,直到没有被引用时才会消亡。此时就会出现一种情况,就是内部类要访问一个不存在的局部变量。
使用 final 修饰符不仅会保持对象的引用不会改变,而且编译器还会持续维护这个对象在回调方法中的生命周期
方法内部类并不是直接调用方法传进来的参数,而是内部类将传进来的参数通过自己的构造器备份到了自己内部,方法内部类调用的实际上是自身的属性而不是外部类方法的参数
2.4匿名内部类
匿名内部类是直接使用 new 来生成一个对象的引用
对于匿名内部类的使用是存在缺陷的,就是它仅能被使用一次,创建匿名内部类时它会立即创建一个该类的实例,该类的定义会立即消失,所以匿名内部类是不能够被重复使用
使用匿名内部类时,我们必须是继承一个类或者实现一个接口,但是两者不可兼得,同时也只能继承一个类或实现一个接口
匿名内部类中是不能定义构造函数的,匿名内部类中不能存在任何的静态成员变量和静态方法
匿名内部类不能是抽象的,他必须要实现继承的类或者实现接口的所有抽象方法
Object 类中的方法
Object 类中方法及说明如下:
- getClass()
返回此 Object 的运行类
- hashCode()
用于获取对象的哈希值
- equals(Object obj)
用于确认两个对象是否相同
- clone()
创建并返回此对象的一个副本
- toString()
返回该对象的字符串表示
- notify()
唤醒在此对象监视器上等待的单个线程
- notifyAll()
唤醒在此对象监视器等待的所有线程
- wait(long timeout,int nanos)
在其他线程调用此对象 notify() 方法,或者超过指定的时间量前,该线程处于等待状态
- wait()
用于让当前线程失去操作权限,当前线程进入等待序列
- finalize()
当垃圾回收器确定该对象不可达时,在垃圾回收前调用此方法,若调用后可达则不回收,否则回收
产生死锁的四个必要条件
死锁概念及产生原理
概念:多个兵法进程因争夺系统资源而产生相互等待的现象
原理:当一组进程中的每个进程都在等待某个事件发生,而只有这组进程中的某个进程才能触发该事件,这就称这组进程发生了死锁
本质原因:
1.系统资源有限
2.进程推进顺序不合理
产生死锁的四个必要条件:
互斥:某种资源一次只允许一个进程访问,即该资源一旦分配给某个进程,其他进程就不能再访问,直到该进程访问结束
占有且等待:一个进程本身占有资源,同时还有资源未得到满足,正在等待其他进程释放该资源
不可抢占:别人已经占有了某项资源,你不能因为自己也需要该资源,就去把别人的资源抢过来
循环等待:存在一个进程l链,使得每个进程都占有下一个进程所需的至少一种资源。
避免死锁的方法:
1.死锁预防 —— 确保系统不会进入死锁状态
产生死锁需要四个条件,只要这四个条件中有一个条件得不到满足,就不可能发生死锁了。由于互斥条件是非共享资源所必需的,不仅不能改变,还应加以保证,所以,主要是破坏产生死锁的其他三个条件。
破坏 ”占有且等待“ 条件
允许进程只获得运行初期需要的资源,便开始运行,在运行过程中逐步释放掉分配到的已经使用完毕的资源,然后再去请求新的资源
破坏 ”不可抢占“ 条件
当一个已经持有了一些资源的进程在提出新的资源请求没有得到满足时,它必须释放掉已经保持的所有资源,带以后需要使用的时候再重新申请。这就意味着进程已占有的资源会短暂地释放或者说是被抢占了
该种方法实现起来比较复杂,且代价也比较大。释放已经保持的资源很有可能会导致进程之前夫人工作失效等,反复的申请和释放资源导致进程的执行被无限的推迟,这不仅会延长进程的周转周期,还会影响系统的吞吐量
破坏循环等待条件
可以通过定义资源类型的线性顺序来预防,可将每个资源编号,当一个进程占有编号为 i 的资源时,那么它下一次申请只能申请编号大于 i 的资源
这样虽然可以避免循环等待,但是这种方法是比较低效的,资源的执行速度会变慢,并且可能在没有必要的情况下拒绝资源的请求,比如说,进程 C 想要申请资源 1 ,如果资源 1 并没有被其他进程占用 ,此时将它分配给进程 C 是没有问题的,但是为了避免产生循环等待,该申请会被拒绝,这样就降低了资源的利用率
- 避免死锁 —— 在使用前进行判断,只允许不会产生死锁的进程申请资源
死锁的避免是利用额外的检验信息,在分配资源时判断是否会出现死锁,只在不会出现死锁的情况下才分配资源
两种避免方法:
如果一个进程的请求会导致死锁,则不启动该进程
如果一个进程的增加资源请求会导致死锁,则拒绝该请求
避免死锁的具体实现通常利用银行家算法