Java常用类库与技巧 - 集合

一 数据结构常见考点

• 数组和链表的区别;
• 链表的操作,如反转,链表环路检测,双向链表,循环链表相关操作;
• 队列,栈的应用;
• 二叉树的遍历方式及其递归和非递归的实现;
• 红黑树的旋转;

二 算法常见考点

• 内部排序 : 如递归排序 交换排序(冒泡 快排) 选择排序 插入排序;

• 外部排序 : 应掌握如何利用有限的内存配合海量的外部存储来处理超大的数据集;

  考点扩展

• 哪些排序是不稳定的,稳定意味着什么?

• 不同数据集,各种排序最好或最差的情况?

• 如何优化算法?

三 Java集合框架图

四 List和Set集合

1. ArrayList

• ArrayList是容量可以改变的非线程安全集合。
• ArrayList实现了List接口，其中元素必然是有序的（按照插入的顺序有序排列，而非按照元素大小排序）。
• 内部实现使用数组进行存储，集合扩容时会创建更大的数组空间，把原有数据复制到新数组中。
• ArrayList支持对元素的快速随机访问，但是插入与删除速度较慢，因为这个过程中很有可能需要移动其他元素

2. LinkedList

• LinkedList的本质是双向链表。
• 相比ArrayList，LinkedList的插入和删除速度更快，但是随机访问速度则很慢。（10万条数据相差数百倍）
• 除了继承AbstractList抽象类外，还实现了接口Deque，即double-ended-queue（双端队列）
• 可以将零散的内存单元通过附加引用的方式关联起来****，形成链路顺序查找的线性结构，内存利用率高。

3. ArrayList 和 LinkedList的异同😀

• 是否线程安全：两者都是不同步的，即 不保证线程安全。

• 底层数据结构：ArrayList的底层是Object数组，LinkList的底层是双向链表结构

• 插入和删除是否受元素位置的影响：

  • ArrayList 采用数组存储，插入、删除元素受元素位置影响。
  • LinkedList 采用链表存储，插入。删除不受位置影响。
  • 快速随机访问：ArrayList支持，快速随机访问就是通过元素序列号快速获取元素对象（对应于get（int index）方法）。LinkedList 不支持快速随机访问。

• 内存空间占用：ArrayList 的空间浪费主要体现在 list列表的结尾会预留一定的容量空间，而LinkedList的空间花费则体现在他的每一个元素都需要消耗比ArrayList更多的空间（因为要存放 直接前驱 和 直接后继 以及数据）

• 扩容机制：ArrayList的默认初始容量大小为10；每次扩容为当前容量的1.5倍。

五 Map集合

1. HashMap（😀必会）

• 底层数据结构：JDK1.8之前 底层是 数组和链表 结合在一起，也就是 链表散列。

  • HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash值，然后通过 (n - 1) & hash判断当前元素存放的位置（n：数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法去解决冲突。
  • 扰动函数：HashMap 的 hash方法，使用 hash 方法就是为了防止一些实现比较差的hashCode()方法。换句话说，使用扰动函数之后可以减少碰撞。
  • 拉链法：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可（链地址法）。

• JDK1.8之后，数据结构是由数组+链表+红黑树来实现的。在解决哈希冲突时有了较大的变化，当链表长度大于阈（yù）值（默认为8）时，将链表转化为红黑树，以减少搜索时间。[O(n)减小到O(logn)]

• 初始容量：初始容量：16，（长度始终保持为2的n次方），如果用户通过构造函数指定了一个数字作为容量，那么Hash会选择大于该数字的第一个2的幂作为容量。(3->4、7->8、9->16)。

• 加载因子：默认为0.75，当HashMap中的元素数目超过加载因子与当前容量的乘积，需要进行2倍扩容操作。

• 扩容机制：每次扩容为原来的2倍。

• HashMap：put方法的逻辑

  1. 如果HashMap未被初始化过,则初始化;

  2. 对key求Hash值,然后在计算下标;

  3. 如果没有碰撞,直接放入桶中;

  4. 如果碰撞了,以链表的方式链接到后边;

  5. 如果链表长度超过阈值,就把链表转成红黑树;

  6. 如果链表长度低于6, 就把红黑树转回链表;

  7. 如果节点已经存在就替换旧值;

  8. 如果桶满了(容量16*加载因子0.75),就需要resize(扩容2倍后重排);

• HashMap：如何有效减少碰撞

  1. 扰动函数：促使元素位置分布均匀，减少碰撞几率
  2. 使用final对象，并采用合适的equals()和hashCode方法

• HashMap的hash方法原理

  static final int hash(Object key) {
       
      int h;
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }
  

• HashMap 扩容问题

  1. 扩容会重新调整容量大小;
  2. 多线程环境下 : 调整大小会存在条件竞争,容易造成死锁;
  3. rehashing是一个比较耗时的过程;

• HashMap多线程操作导致死循环问题

  • 在多线程下，进行 put 操作会导致 HashMap 死循环。原因在于 HashMap 的扩容 resize()方法。由于扩容是新建一个数组，复制原数据到数组。由于数组下标挂有链表，所以需要复制链表，但是多线程操作有可能导致环形链表。

• HashMap的长度为什么是2的幂次方

  • 为了能让 HashMap 存取高效，尽量减少碰撞，也就是要尽量吧数据分配均匀。Hash值的范围是 -2^{31(-2147483648)到2}31-1(2147483647),前后加起来是一个大约40亿的映射空间。只要哈希函数映射的比较均匀松散。但问题是一个40亿长度的数组,内存是放不下去的。 所以这个散列值是不能直接拿来使用的。用之前还有先对数组的长度取模运算，得到的余数就是存放的位置（对应数组的下标），数组下标计算方法是(n - 1) & hash(n代表数组长度)。

  • 这个算法应该如何设计呢？

    取余啊 % 。但是重点来了 取余（%）操作中，如果除数是2的幂次 则等价于 与其除数减一的与（&）操作，也就是说 hash % n == hash & (n - 1)，前提是n 必须是2的n次方。并且采用二进制位操作 与& ，相对的能够提高运算效率，这就是为什么 HashMap的长度是2的幂次方。

2. HashTable

• 早期Java类库提供的哈希表的实现
• 线程安全：涉及到修改Hhashtable的方法，使用synchronized修饰
• 串行化的方式运行，性能较差

3. ConccurentHashMap

1. 如何优化Hashtable

通过锁细粒度化，将整锁拆解成多个锁进行优化

2. ConcurrentHashMap

3. ConcurrentHashMap:put方法的逻辑

1.判断Node[]数组是否初始化，没有则进行初始化操作

2.通过hash定位数组的索引坐标，是否有Node节点，如果没有则使用CAS进行添加(链表的头节点)，添加失败则进入下次循环。

3.检查到内部正在扩容，就帮助它一块扩容。

4.如果 f != null,则使用synchronize锁住f元素(链表/红黑树二叉树的头元素)

4.1 如果是Node(链表结构)则执行链表的添加操作

4.2 如果是TreeNode(树形结构)则执行树添加操作

5. 判断链表长度已经达到临界值8,当然这个8是默认值，大家也可以去做调整，当节点数超过这个值就需要把链表转换为数结构

4. CoucurrentHashMap总结：

• 比起Segment,锁拆得更细
• 首先使用无锁操作CAS插入头节点，失败则循环重试
• 若头节点已存在，则尝试获取头结点的同步锁，在进行操作

4. 三者的区别

HashMap线程不安全，数组+链表+红黑树

Hashtable线程安全，锁住整个对象，数组+链表

ConcurrentHashMap线程安全，CAS+同步锁，数组+链表+红黑树

六 Java常用类库与技巧 - 异常知识点总结