《Java核心技术卷I》笔记——（4）泛型和集合类

比眉伴天荒 2023-09-30 10:08 1阅读 0赞

**第 8 章节**  
这一章主要讲Java的泛型；泛型常用于集合类（可以放任意类型的参考类的容器），或是用于工厂（返回某个类的对象）；

**为什么用Java泛型？**

代码可以被多个类复用，泛型的使用避免了对Object类的“滥用”（强转类型）；用编译器检查来代替类型强转可能造成的异常；

**（1）泛型类？**

在定义一个类的时候使用泛型，即“将泛型类T看做成每一个具体参考类的工厂”；用法eg：

U类和T类对类MyClass的外部来说，是不确定的，在实例化类MyClass的对象时候才能确定；
    但对于类MyClass内部来说，U类和T类就是一个具体确定的类型，如：
    public class MyClass <U, T>
    {
      T first;
      U second; //作为成员变量的类型；
      private T getFirst(){...} //作为方法的返回类型； 或者作为方法传递的形参类型;
    }
    
    不能对确切的泛型类型使用instanceof操作，eg：ex_num instanceof Generic<Number> 这一句是非法的；
    
    需要注意的是，泛型类只有在实例化对象的时候才知道泛型的具体类型，所以对于静态方法（如单例模式）不能使用泛型类中的T类；

**（2）泛型方法？**

方法本身与泛型有关，与所在的类是不是泛型类没有关系，即泛型方法可以存在于泛型类和普通类里面；

eg：

public <T extends Comparable<T>> int compareObj(T x1, T x2) {    
       return x1.compareTo(x2);
    }

当然，泛型方法可以与泛型类一起配合使用； 静态方法有一种情况需要注意一下，那就是在类中的静态方法使用泛型：静态方法无法访问类上定义的泛型；如果静态方法操作的引用数据类型不确定的时候，必须要将泛型定义在方法上。

**泛型中的继承？**

<T extends Comparable>或<? extends Comparable>  
**注意**：这里虽然是继承接口，但不使用implements关键字，都用extends，并且后面可以接多个接口；

作为参数传递的时候，假如class B extends class A，而一个方法需要传递classF<B>对象，尽管A是B的父类，但是不能传入classF<A>对象；解决办法：将传递参数改成classF<? extends A>即可；

**泛型擦除？**

对已同一个类的两个对象，分别是MyCkass<A>与MyCkass<B>的实例，他们的getClass返回同一个值；

**泛型与数组？**

泛型可以写在数组的引用中，但不能写在new语句里面，eg：

List<String>[] ls = new ArrayList<String>[10]; //这是错的； 
    List<?>[] ls = new ArrayList[10]; //这是对的；

**第 9 章节**  
这一章属于Java知识的**重点**，主要包括常见的集合类（数组、队列、栈、映射Map），JDK中都有对应的实现类（从Iterable/Collection接口往下），封装到集合类的算法（快排、归并、二分、TimerSort...稳定的排序？），常用集合类JDK源码，线程安全的集合。

**迭代器？**

Iterator对象，用来遍历集合类的元素。Iterator的next()方法：迭代器相当于在两个元素之间，调用next()将把迭代器移动到当前元素与下各元素之间，并返回刚经过的当前元素；remove()方法则是删除上次调用next()方法时返回的那个元素；

**泛型与集合类？**

集合就是存放各种元素的容器，因此为达到收集异类，满足不同类都可以存入集合并执行一些常规操作，需要配合泛型。

**集合类的框架？（图） 具体/常见的集合？**

![581c55d43011f3874b3658c3fe76ee9c.png][]

image.png

数组/链表、散列hash、映射Map、树、队列（\*优先队列）；（图）

![540d35c6b17d1c4830f4c7aaf092dd38.png][]

image.png

**相似集合类的比较（JDK源码）**

**（1）List,Set,Map三者的区别？**

**List**： List接口存储（可以有多个元素引用相同的对象）的有序的对象。  
**Set**：不允许重复元素的集合。  
**Map**：使用键值对存储。Map会维护与Key有关联的值。两个Key可以引用相同的对象，但Key不能重复，典型的Key是String类型，但也可以是任何对象。

**（2）Arraylist 与 LinkedList 区别?**

**1. 线程安全**： ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；  
**2. 底层数据结构**： Arraylist 底层使用的是 Object 数组；LinkedList 底层使用的是双向链表；  
**3.插入和删除是否受元素位置的影响**：ArrayList采用数组存储，所以插入和删除指定位置元素的时间复杂度受元素位置的影响，使用Arrays.copyof()实现；LinkedList采用链表存储，所以插入，删除元素时间复杂度不受元素位置的影响，都是近似 O（1）而数组为近似 O（n）。  
**4. 是否支持快速随机访问**： LinkedList 不支持高效的随机元素访问，而 ArrayList 支持。  
**5.内存空间占用**：ArrayList的空间浪费主要体现在在list列表的结尾会预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间（因为要存放直接后继和直接前驱以及数据）。

**（3）RandomAccess接口？**

查看源码我们发现实际上RandomAccess接口中什么都没有定义。所以，在我看来RandomAccess接口不过是一个标识罢了。标识什么？标识实现这个接口的类具有随机访问功能。例如，Arraylist与LinkedList；实现了RandomAccess接口的list，优先选择普通for循环，其次foreach,未实现RandomAccess接口的list，优先选择iterator遍历（foreach遍历底层也是通过iterator实现的,），大size的数据，千万不要使用普通for循环；

**（4）ArrayList 与 Vector ？**

Vector被废弃，看做ArrayList的线程安全版本；其方法都使用synchronized修饰，线程安全但是单线程性能不高；

**（5）ArrayList扩容机制？**

1.5倍扩容；最好在 add 大量元素之前用 ensureCapacity 方法，以减少增量重新分配的次数；

**（6）HashMap 和 Hashtable 的区别？**

**1.线程是否安全**： HashMap 是非线程安全的，HashTable 是线程安全的；HashTable 内部的方法基本都经过synchronized 修饰。（如果要保证线程安全的话就使用 ConcurrentHashMap ）；  
**2.效率**：因为线程安全的问题，HashMap 要比 HashTable 效率高一点。另外，HashTable 基本被淘汰，不要在代码中使用它；  
**3.对Null key 和Null value的支持**： HashMap 中，null 可以作为键，这样的键只有一个，可以有一个或多个键所对应的值为 null。但是在 HashTable 中 put 进的键值只要有一个 null，直接抛出 NullPointerException。  
**4.初始容量大小和每次扩充容量大小的不同**：Hashtable默认的初始大小为11，之后每次扩充，容量变为原来的2n+1。HashMap默认的初始化大小为16。之后每次扩充，容量变为原来的2倍。创建时如果给定了容量初始值，那么Hashtable会直接使用你给定的大小，而 HashMap 会将其扩充为2的幂次方大小（HashMap 中的tableSizeFor()方法保证）。也就是说 HashMap 总是使用2的幂作为哈希表的大小。  
**5.底层数据结构**： JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。

**（7）HashMap——当HashMap()的key为自定义的类型时候，为何需要重写equal()与hashCode()方法？ 底层原理？**

![0c24ab8e47f9a3dc679307f0dc179f8d.png][]

image.png

![8f4c613a83a8beac09349a9718a90342.png][]

image.png

**Hashmap的底层实现是“拉链法”**——数组+链表；通过hashcode()得到key（一般为String类）的哈希值。对数组（桶位）取模后得到Entry数组的下标；遍历当前Entry数组所在的链表，通过判断equals(key)得到需要的那个链表节点，从未可以进行“读取/更改/删除”操作；

**使用自定义类型的key为什么要重写方法？**

eg：有个学生类Student，类里面有个字段ID，有两个对象：  
Student s1 = new Student("A");  
Student s2 = new Student("A");  
逻辑上我们认为他们作为key是相等的，但是实际上s1.equals(s2)为false，因此需要重写与equals()/hashCode()方法，让ID相等的两个Student对象“相等”，即用s2能在map里找到s1所在使的桶位-进而找到链表节点；

**hashCode()与equals()的相关规定**：

（1）如果两个对象相等，则hashcode一定也是相同的  
（2）两个对象相等,对两个equals方法返回true  
（3）两个对象有相同的hashcode值，它们也不一定是相等的

综上，equals方法被覆盖过，则hashCode方法也必须被覆盖 hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写hashCode()，则该class的两个对象无论如何都不会相等（即使这两个对象指向相同的数据）。

**（8）JDK源码-HashMap？ 遍历方法？**

1.遍历key，由key取出value：map.keySet()-map.get(key);  
2.使用迭代器遍历Entry：it = map.entrySet().iterator-while(it.hasNext())\{...entry.getKey();entry.getValue()\};  
3.（推荐）针对大容量map，forEach循环遍历Entry数组；  
4.Map.Values()得到value数组；

**hash()方法？**

hashcode与本身的高16位异或运算；
    static final int hash(Object key) {
           int h;
           return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
       }

**HashMap核心属性？**

1.Node<K,V>，链表节点，包含key/value/hash/next 4个属性；  
2.table，Node<K,V>的数组，数组元素为Node<K,V>，即链表节点，存放key/value的实体；  
3.size，存入map的元素个数；  
4.loadFactor，负载因子，用来扩容；  
5.threshold，阈值，决定了hashmap何时扩容以及扩容后的大小，一般等于table的大小乘以loadFactor；

**构造函数？**

设定initialCapacity初始容量，loadfactor负载因子；（默认16/0.75）；当指定设定initialCapacity初始容量后，不会直接使用这个值，而是转化成“大于等于”这个值的2的指数次；

**容量为何是2的指数次？**

**为了方便扩容！**hashmap使用“懒加载”，构造完成hashmap后只有在进行put()方法时，才会判断是否初始化table/扩容resize();当添加完成元素后，才会判断size与threshold的大小，满足条件则会调用resize()方法扩容；

**扩容原理？**

步骤：  
1. 当判断满足扩容条件时候，table数组长度变为以前的两倍：newThr = oldThr << 1;（N=N\*2，N为之前数组长度）;  
2. 判断当前元素的hash()值得下一位（从右到左）位的值是否为0，若为0则元素仍在之前的桶位，若为1则元素移动到下标为（原索引+旧容量N）的索引处；

再来解释一下以上原理以及**为何容量N要是2的指数次？**

放入新元素时执行putVal()方法，需要传递新元素的hash()值作为方法参数，而hash()方法返回一个int（32位）值，而新元素插入的索引（数组下标）为hash&(table.size-1)，即一个2进制的"与"操作,

eg： 当前数组size为16，即N=16；需要插入2个新元素，记为key1和key2；

N-1=15  =  0000 0000 0000 0000 | 0000 0000 0000 1111
     key1(hash):1111 1111 1111 1111 | 0000 1111 0000 0101
     key2(hash):1111 1111 1111 1111 | 0000 1111 0001 0101

“与”操作后，索引分别为：key1-0101，key2-0101;  
现在，进行扩容：N=N<<1=32,下一位由0变成1，进行“与”操作后，索引分别为：key1-0 0101，key2-1 0101;

**而新位置（索引）比原来的值多了0或N；**

**结论**：扩容后，之前为同一索引下的元素插入的新位置取决于当前index值得“2进制的下一位”是0还是1；若为1，则新位置为“原位置index+旧容量N”，而不需要重新计算这个元素的hash()值，这就是为什么容量为2的指数次的原因；

**JDK8做的优化？**

当一个桶位下的链表（Node<K,V>）长度大于8，遍历这个链表找元素则会很慢，JDK优化后，将长度大于8的链表转化为“红黑树”对节点排序，便于节点的查找；

**（9）ConcurrentHashMap 和 Hashtable 的区别？（图）ConcurrentHashMap线程安全的具体实现原理？**

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiD5rW35YGl5Lq6_size_20_color_FFFFFF_t_70_g_se_x_16][]image.png

![24c729e87f863cd9b2b08558c253ea5d.png][]

image.png

JDK7：ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成；一个 ConcurrentHashMap 里包含一个 Segment 数组。Segment 的结构和HashMap类似，是一种数组和链表结构，一个 Segment包含一个HashEntry 数组，每个HashEntry是一个链表结构的元素，每个Segment守护着一个HashEntry数组里的元素，当对HashEntry 数组的数据进行修改时，必须首先获得对应的 egment的锁，这样可以并行的对不同Segment下的节点进行操作，而不会引起线程的等待；

**JDK8：ConcurrentHashMap取消了Segment分段锁，采用CAS和synchronized来保证并发安全。Segment变成了首节点；synchronized只锁定当前链表或红黑二叉树的首节点，这样只要hash不冲突，就不会产生并发**。

**（10）遗留的（废弃的）集合类？**

Vector/Stack/HashTable/Enumeration

**（11）[红黑树][Link 1]？**

**一种平衡二叉树，即从上往下每一层，大小关系满足：左子节点 < 根节点 < 右子节点，方便查询，时间复杂度log(n)，n为树的深度**。那么当插入的一组值为递减序列，且都插在左子节点，那么这个树就不“**平衡**”了，即某一侧的深度远大于另一侧，导致整个树的深度增加，以至于查询的时间增加（n增加）；这时候需要引入一种数据结构，即红黑树（二叉平衡树），其满足5个限制条件，当插入新节点，会判断是否满足这5个条件，不满足则需要调整，**调整的动作有：[左/右旋转、变色][Link 2]**；

**（12）乐观锁CAS?**

从思想上来说，Synchronized属于悲观锁，悲观地认为程序中的并发情况严重，所以严防死守。CAS属于乐观锁，乐观地认为程序中的并发情况不那么严重，所以让线程不断去尝试更新。实现CAS要用到Automic原子类-compareAndSet()方法；

**CAS缺点**：

1. ABA问题，线程1和线程2都修改成功了，但是忽略了变量中间的变化过程，解决办法-所以JAVA中提供了AtomicStampedReference/AtomicMarkableReference来处理会发生ABA问题的场景，主要是在对象中额外再增加一个标记来标识对象是否有过变更，这个类的compareAndSet方法作用是首先检查当前引用是否等于预期引用，并且当前标志是否等于预期标志，如果全部相等，则以原子方式将该引用和该标志的值设置为给定的更新值；

2. 对于自旋（不断循环尝试获得CPU资源），自旋CAS如果长时间不成功，当在并发量比较高的情况下，如果许多线程反复尝试更新某一个变量，却又一直更新不成功，循环往复，会给CPU带来很大的压力；

3. 只能保证一个共享变量的原子操作。当对一个共享变量执行操作时，我们可以使用循环CAS的方式来保证原子操作，但是对多个共享变量操作时，循环CAS就无法保证操作的原子性，这个时候就可以用锁，或者有一个取巧的办法，就是把多个共享变量合并成一个共享变量来操作。比如有两个共享变量i＝2,j=a，合并一下ij=2a，然后用CAS来操作ij。从Java1.5开始JDK提供了AtomicReference类来保证引用对象之间的原子性，你可以把多个变量放在一个对象里来进行CAS操作；

**（11）其他思考？——ConcurrentHashMap完全取代了Hashtable？**  
[ConcurrentHashMap完全取代了Hashtable吗？][ConcurrentHashMap_Hashtable]

[581c55d43011f3874b3658c3fe76ee9c.png]: https://img-blog.csdnimg.cn/img_convert/581c55d43011f3874b3658c3fe76ee9c.png
[540d35c6b17d1c4830f4c7aaf092dd38.png]: https://img-blog.csdnimg.cn/img_convert/540d35c6b17d1c4830f4c7aaf092dd38.png
[0c24ab8e47f9a3dc679307f0dc179f8d.png]: https://img-blog.csdnimg.cn/img_convert/0c24ab8e47f9a3dc679307f0dc179f8d.png
[8f4c613a83a8beac09349a9718a90342.png]: https://img-blog.csdnimg.cn/img_convert/8f4c613a83a8beac09349a9718a90342.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiD5rW35YGl5Lq6_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/f14533583bdc48d2a4088ad51b6359e1.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LiD5rW35YGl5Lq6,size_20,color_FFFFFF,t_70,g_se,x_16
[24c729e87f863cd9b2b08558c253ea5d.png]: https://img-blog.csdnimg.cn/img_convert/24c729e87f863cd9b2b08558c253ea5d.png
[Link 1]: http://www.360doc.com/content/18/0904/19/25944647_783893127.shtml
[Link 2]: https://www.cnblogs.com/ysocean/p/8004211.html
[ConcurrentHashMap_Hashtable]: https://blog.csdn.net/moakun/article/details/80617983