网站排名不稳定,装潢设计与制作,青岛建设网站设计公司,东莞网站建设dgjcwl目录Java基础Java面向对象有哪些特征ArrayList和LinkedList有什么区别高并发的集合有哪些问题迭代器的fail-fast和fail-safeArrayList底层扩容机制HashMap面试合集解答设计模式单例设计模式哪些地方体现了单例模式Java基础
Java面向对象有哪些特征
Java面向对象有三大特征封装继承多态
其中封装是增加了代码的复用性封装好的代码可以重复使用体现高内聚低耦合
封装说明的是一个类的行为和属性与其他类的关系 封装隐藏了类的内部实现机制可以在不影响使用的情况下改变类的内部结构同时也保护了数据。对外界而已它的内部细节是隐藏的暴露给外界的只是它的访问方法。 继承也是增加了代码的复用性不用频繁的重新编写方法而是直接继承父类方法
继承是父类和子类的关系 继承是从已有的类中派生出新的类新的类能吸收已有类的数据属性和行为并能扩展新的能力。 多态是增加了代码的可移植性健壮性灵活性
多态说的是类与类之间的关系 封装和继承最后归结于多态多态指的是类和类的关系两个类由继承关系存在有方法的重写故而可以在调用时有父类引用指向子类对象。多态必备三个要素:继承重写父类引用指向子类对象。 ArrayList和LinkedList有什么区别
ArrayList底层是以数组实现的对于随机访问的时间复杂度是O(1) 但是对于头部插入删除操作效率要低于LinkedList而ArrayList尾部的插入删除操作还要比LinkedList快许多因为尾部操作直接在数组后面加或删根据索引定位比LinkedList更改指针指向还要更加快 LinkedList底层是以双向链表实现的它对于头部和尾部添加删除的操作时间复杂度为O(1)但是对于随机访问效率要低于ArrayList 重点来了 ①对于查询操作二者耗时是一样的根据值去查找都需要一个一个比较 ②对于中间元素的插入删除操作LinkedList要比ArrayList耗时更多因为LinkedList的双向链表虽然链表对于删除插入操作效率更高但是它需要先遍历到中间位置链表遍历耗时长时间浪费在遍历到对应索引位置上了 ③LinkedList占用内存多于ArrayList下图可以看的很清楚 总结 ArrayList
①基于数组需要连续内存②随机访问快指根据下标访问)③尾部插入、删除性能可以其它部分插入、删除都会移动数据因此性能会更低④可以利用cpu缓存局部性原理
LinkedList
①基于双向链表无需连续内存②随机访问慢要沿着链表遍历)③头尾插入删除性能高④占用内存多 高并发的集合有哪些问题
线程非安全集合类
ArrayList、HashMap 线程不安全但是性能好
需要线程安全怎么办呢? 使用Collections.synchronizedList(list); Collections.synchronizedMap(m); 底层使用synchronized代码块锁虽然也是锁住了所有的代码但是锁在方法里边比锁在方法外边性能可以理解为稍有提高吧。 线程安全集合类
ConcurrentHashMap CopyOnWriteArrayList CopyOnWriteArraySet
底层大都采用Lock锁(1.8的ConcurrentHashMap不使用Lock锁)保证安全的同时性能也很高。 迭代器的fail-fast和fail-safe
对于迭代器可以遍历listset这些单列集合其中有一个问题在遍历这些集合时是否允许其他线程对集合进行插入修改操作呢
下面是迭代器的两种处理策略
fail-fast一旦发现遍历的同时其它人来修改则立刻抛异常
fail-safe发现遍历的同时其它人来修改应当能有应对策略例如牺牲一致性来让整个遍历运行完成对于ArrayList的迭代器就是属于fail-fast这种策略它是不允许一边遍历一边修改的会直接报错尽快失败
迭代器的fail-fast源码分析其实就是我之前讲的并发修改异常地址http://t.csdn.cn/C43GG在遍历开始时记录modCount修改值然后在每次的next()中调用checkForComodification()方法检查modCount比较两个modCount是否一致来判断 而对于CopyOnWriteArrayList的迭代器迭代器其实是它里面的内部类每个集合的迭代器都有可能不同 具体流程见下图简而言之就是它的遍历和添加操作的不是同一个数组用读写分离的方式来处理遍历时的数组修改牺牲一致性来让整个遍历运行完成 总结 fail-fast 与fail-safe ArrayList是 fail-fast的典型代表遍历的同时不能修改尽快失败CopyOnWriteArrayList是 fail-safe 的典型代表遍历的同时可以修改原理是读写分离 ArrayList底层扩容机制
JDK7初始化一个ArrayList集合时初始容量为10 JDK8初始化一个ArrayList集合时长度为0只有在添加元素时才会给数组赋予大小
扩容机制分两种 一种是超过了数组容量大小底层数组扩容为原数组的1.5倍并把原数组中的元素拷贝到新数组中
另一种是新增加的元素数量超过了数组扩容后的容量简单说就是即使数组扩容1.5倍后仍然不能满足新增元素的个数addAll这种方法这时扩容长度就是需要容纳所有元素的长度 容易记的说法下次扩容的容量跟实际元素个数中取一个较大值来作为数组的最终大小 HashMap面试合集解答
底层数据结构1.7和1.8有何不同
在JDK7HashMap底层数据结构是 数组 链表的形式 而在JDK8 其底层结构式数组 链表 红黑树的结构 int index 数组长度-1哈希值;上面就是计算存储位置的公式
哈希表最大的优点就是实现集合中元素的快速查找 因为数组下标索引是根据元素的哈希值来计算得到的所以可以根据元素值快速定位索引找到元素位置判断位置是否有元素若没有即未找到位置若有元素比较二者hash值是否相同相同即找到了该元素。可以通过值来查询这是ArrayList无法比拟的ArrayList只能用索引来查找不能根据元素值来查找
HashMap底层的数组扩容阙值是元素个数达到了数组容量的3/4或数组长度*扩容因子就会扩容为原数组的两倍 树化条件 而它的链表树化时机是当链表长度大于8而且数组长度大于等于64时链表转化为红黑树 而当数组长度未达到64而链表长度大于等于8时虽然不会树化但是会进行数组扩容链表长度可能会大于8 树化为红黑树后它左侧都是比根节点小的元素右侧都是比根节点大的元素
为什么不一上来就树化 短链表时它的性能是比红黑树要好的最多比较几次而已长链表情况下红黑树的效率更高优化也是优化在这种情况而且红黑树底层的结构TreeNode成员变量比Node多比Node占用内存更多所以链表较短情况下 树化是没有性能提升的 为什么树化阙值是8 红黑树用来避免DoS攻击防止链表超长时性能下降树化应当是偶然情况
①hash表的查找更新的时间复杂度是O(1)而红黑树的查找更新的时间复杂度O(log2n),TreeNode占用空间也比普通Node的大如非必要尽量还是使用链表。 ②hash值如果足够随机则在 hash表内按泊松分布在负载因子0.75的情况下长度超过8的链表出现概率是0.00000006一亿分之六选择8就是为了让树化几率足够小 红黑树何时会退化为链表
退化情况1:在扩容时如果拆分树时树元素个数6则会退化链表
退化情况2: 在remove树节点时若root根节点、root.left左孩子节点、root.right右孩子节点、root.left.left左孙子节点有一个为null不存在也会退化为链表
注举例当删除左孩子节点时树不会退化但是再次执行remove操作时会判断若没有左孩子就会退化为链表 情况1和情况2不要混为一谈1是在数组扩容时的条件2是在删除树的结点时的条件 如何计算索引 计算对象的hashcode()再进行调用HashMap的 hash()方法进行二次哈希最后和数组长度减一按位与运算 哈希值 mod 数组长度 等价于 哈希值 数组长度 - 1 用位运算效率更高性能更高 前提是数组长度是2的n次方
二次hash()是为了综合高位数据让哈希分布更为均匀
计算索引时如果是2的n次幂可以使用位与运算代替取模效率更高;扩容时 hash 原数组长度0的元素留在原来位置否则新位置旧位置索引原数组长度
缺点数组容量是2的n次幂时分布性没有选质数的好 put方法流程1.7和1.8的区别
扩容过程先把元素添加到旧数组然后达到阙值数组扩容再把旧数组的所有元素迁移到新数组
1.7和1.8的不同之处 ①链表插入节点时1.7是头插法新元素存数组老元素挂新元素下面1.8是尾插法新元素直接挂老元素下面 ②1.7是大于阙值而且没有空位时数组才会扩容而1.8时大于阙值就进行扩容 ③1.8在扩容计算Node索引时会优化扩容时 hash 原数组长度0的元素留在原来位置否则新位置旧位置索引原数组长度 加载因子 / 扩容因子为何是0.75f
在空间占用与查询时间之间取得较好的权衡大于这个值空间节省了但链表就会比较长影响性能小于这个值冲突减少了但扩容就会更频繁空间占用也更多造成空间浪费 多线程下操作HashMap有啥问题
数据错乱1.71.8 都会存在 JDK7会发生死链问题原因就识JDK7的头插法
JDK7的头插法认识
别眨眼接下来是多线程情况下 Key能否为null作为key的对象有什么要求
HashMap 的 key 可以为 null但 Map 的其他实现则不然作为 key 的对象必须实现 hashCode更好的分布性 和 equals万一hash值相同比较equals并且 key 的内容不能修改不可变hashCode不一定equals但一旦equals了必然hashCode相同key 的 hashCode 应该有良好的散列性 设计模式
单例设计模式
实现方式之一
饿汉式一开始就先把INSTANCE对象创建出来提前创建
构造方法抛出异常是防止反射破坏单例readResolve() 是防止反序列化破坏单例
public class Singleton1 implements Serializable {private Singleton1() {if (INSTANCE ! null) {throw new RuntimeException(单例对象不能重复创建);}System.out.println(private Singleton1());}private static final Singleton1 INSTANCE new Singleton1();public static Singleton1 getInstance() {return INSTANCE;}public static void otherMethod() {System.out.println(otherMethod());}public Object readResolve() {return INSTANCE;}
}但是以下几种方式会破坏单例 ①反射 可以加个判断来防止暴力反射创建对象以免破坏单例 已经创建了单例对象再用反射调用创建对象时会报错 if (INSTANCE ! null) {throw new RuntimeException(单例对象不能重复创建);}②反序列化 拿到单例对象后通过ObjectOutStream来把对象变成一个字节流再通过ObjectInputStream还原成一个对象序列化反序列化过程又可以造出一个新的对象甚至不需要走构造方法
防止方法 重写readResolve()方法后反序列化时就会用readResolve()的方法返回值作为结果返回而不是通过字节数组反序列化生产的对象了
public Object readResolve() {return INSTANCE;
}③Unsafe unsafe是JDK内置的一个类它其中有一个allocateInstance(clazz)方法可以根据参数类型创建这个类型的实例也不会走构造方法目前没有防止的方法 实现方式之二
枚举饿汉式 枚举饿汉式能天然防止反射、反序列化破坏单例 public enum Singleton2 {INSTANCE;private Singleton2() {System.out.println(private Singleton2());}Overridepublic String toString() {return getClass().getName() Integer.toHexString(hashCode());}public static Singleton2 getInstance() {return INSTANCE;}public static void otherMethod() {System.out.println(otherMethod());}
}实现方式之三
懒汉式单例 用的时候再创建单例对象什么时候调什么时候创 但是饿汉式是线程不安全的在多线程情况下无法保证单例所以只能在创建单例对象方法上加synchronized来修饰加锁保证单例
public class Singleton4 implements Serializable {private Singleton4() {System.out.println(private Singleton4());}private static volatile Singleton4 INSTANCE null; // 可见性有序性public static Singleton4 getInstance() {if (INSTANCE null) {synchronized (Singleton4.class) {if (INSTANCE null) {INSTANCE new Singleton4();}}}return INSTANCE;}public static void otherMethod() {System.out.println(otherMethod());}
}为何必须加 volatile
INSTANCE new Singleton4() 不是原子的分成 3 步创建对象、调用构造、给静态变量赋值其中后两步可能被指令重排序优化变成先赋值、再调用构造如果线程1 先执行了赋值线程2 执行到第一个 INSTANCE null 时发现 INSTANCE 已经不为 null此时就会返回一个未完全构造的对象 这里注意一下使用的是双检锁的方式来创建单例对象在多个线程竞争锁时获取到锁的执行未获取到锁的挂起等到释放锁后挂起的线程被唤醒而此时单例对象已经存在了所以需要再次进行判断防止创建新的对象 if (INSTANCE null) {synchronized (Singleton4.class) {if (INSTANCE null) {INSTANCE new Singleton4();}}反问为什么饿汉式不用考虑线程安全问题 因为饿汉式创建单例对象时赋值给静态变量的单例对象会在类加载时就创建了由JVM保证其原子性且安全执行JVM保证了初始化阶段的线程安全 枚举饿汉式也是在静态代码块里创建枚举变量的它的线程安全也不需要考虑 实现方式之四
内部类懒汉式
这就运用了饿汉式的保证线程安全的方法 内部类在使用时初始化这样创建单例对象的操作就在静态代码块中执行避免了线程安全问题
public class Singleton5 implements Serializable {private Singleton5() {System.out.println(private Singleton5());}private static class Holder {static Singleton5 INSTANCE new Singleton5();}public static Singleton5 getInstance() {return Holder.INSTANCE;//这时会触发内部类的加载链接触发}public static void otherMethod() {System.out.println(otherMethod());}
}既兼备了懒汉式的特性又避免了双检锁的缺点 哪些地方体现了单例模式
Runtime 体现了饿汉式单例System.java的Console 体现了双检锁懒汉式单例Collections 中的 EmptyNavigableSet 内部类懒汉式单例ReverseComparator.REVERSE_ORDER 内部类懒汉式单例Comparators.NaturalOrderComparator.INSTANCE 枚举饿汉式单例
