ArrayList HashMap

面试漫谈（四）- 集合篇（一）

Posted by YiBo on December 11, 2020

前记

下周二就要面个一个大厂了，需要恶补一下基础，这篇就以基础为主

说说ArrayList是什么，能用来干嘛

数组列表，用来装载数据，存储 int long boolean short 等的包装类，而不能存放基础数据类型。

底层是数组实现的存储

查找，访问元素速度快，新增，删除慢，线程不安全，但使用频率高

正常使用中，都是用来查询，不会涉及太多的增删，如果涉及频繁增删，可以使用LinkedList，如果要线程安全就是用Vector

说一下ArrayList底层

底层是数组，在构造方法的时候指定底层数组大小，如果使用无参构造，则会默认一个空数组，只有真正对数据添加时，才会分配默认 DEFAULT_CAPACITY = 10 的初始容量

Array长度是限制的，ArrayList可以存放任意对象，是怎么实现的

通过数组扩容

比如刚开始的长度是10，满了会重新定义一个10+10/2的数组，然后复制到新数组中，再把地址换到新地址

ArrayList的各种操作的逻辑说说

新增的逻辑

每次新增都会判断长度够不够，扩容JDK 8 之后的版本采用位运算，右移一位（10+10»1）,其实就是除2，之后就是copy数组，如果是在中间增加一个元素，增加位置后面的元素都要整体copy一遍，然后在空出来的位置添加，所以比较慢

但是也不一定都是慢的，取决于新增、删除的元素离数组末端有多远，push pop 操作完全不涉及数据移动操作，所以比较适合用来做栈。但是队列是先进先出的，所以不适合

ArrayList不适合做队列，那数组适合吗

​ 合适的 ArrayBlockingQueue内部就是环形队列，是定长的

删除的逻辑

其实就是copy了一个数组，效率也很低

ArrayList（100）这样构造会不会初始化数组大小

设置了初始大小后，打印list大小的时候还是0

ArrayList 线程为什么不是安全的

线程安全版本的数组是Vector，其实就是把所有方法统统加上synchronized

ArrayList的遍历和LinkedList遍历性能比较

ArrayList快，他的内存是连续的，而LinkedList是指针指向的，内存不连续

说说HashMap吧

底层是数组和列表组合构成的数据结构

数组是k-v模式，插入数据的时候，根据Key算出对应的hash值，然后插入指定index。如果算到重复的Hash值，则形成列表，java8之后用尾部插入

那为什么改为尾部插入呢

这个和HashMap的扩容有关

先说下扩容的机制，当多次插入时，就会进行 resize

  • 根据负载因子，默认是0.75f 比如容量100，插入第76个时候进行扩容

扩容的步骤分为俩步：

  1. 创建一个新的空数组，长度是原来的2倍
  2. ReHash： 遍历原来的数组，把所有entry重新Hash到新数组

回到本来的问题，为什么改为尾部插入

在多线程下，俩个现成的扩容会导致列表陷入无限循环。如果是尾部插入就不会，因为扩容前后的链表顺序不会变

HashMap的默认初始化长度是多少

16

这里要涉及到对key的Hash算法，尽可能拿到一个均有分布的Hash

​ 16是2的幕 index = (n-1)&hash，如果不是用2的幕的数字，length-1的值所有二进制位都为1，实现均匀分布

​ 为了保证 负载因子（0.75）*容量（2的幕） 的结果都是整数

为啥从写equals方法的时候需要重写hashCode方法

java中所有对象都是继承Object，Object中有俩个默认方法：

  1. HashCode

    根据内存地址换算一个值

  2. Equals

    根据内存地址判断是否相等

HashMap get的时候先用HashCode确定位置，再去比较Equals，如果只重写了equals，HashCode不一致还是拿不到

举个例子，u1= new User(“yibo”) , u2 = new User(“yibo”)

重写equals保证这俩个new对象相同

重写HashCode保证这俩个存放在HashMap中的地址也是相同的

HashMap 为什么是链表长度超过8个会转成树结构，小于6会变成链表

链表-》红黑树：不是超过8，先判断table的长度是否大于64，如果小于64通过扩容的方式来避免红黑树结构

红黑树-》链表：在remove后，通过红黑树根节点以及其子节点是否为空来判断

​ 在resize的时候，根据小于等于6，换回链表

因为树节点大小是链表节点大小的俩倍，所以只有在容器中包含足够的节点保证是用才用他。虽然查找速度更快，但是节点数比较小的时候，红黑树内存上会劣势

理想情况下，在随机哈希吗下，哈希表中节点的频率遵循泊松分布，8以上的概率很小

HashMap 多线程下会出现什么问题

这个通过看源码就可以发现，有下面几种

  • 在put()的时候，如果俩个线程同时需要在列表后面添加元素，他们拿到到的前Node p都是一致的，在进行p->next=… 的时候，另一个线程的就会无效，换句话说丢失了

  • put 和 get 并发时，可能导致get为null。线程1执行put时，导致rehash，线程2此时get会导致这个问题

  • 一遍size()一遍put() 会抛出异常，因为他是 fail-fast，在遍历的时候如果有改变，就会检测到并且抛出异常

  • 还有JDK1.7中并发put会造成循环链表，俩个线程同时rehash 导致get的时候出现死循环：get的for循环一直停不下来，列表中又没有对应的key

HashMap怎么处理线程安全的场景

俩个选择

  1. Collections.SynchronizedMap(Map)

    内部维护了一个普通的Map 和 排斥锁 mutex

  2. HashTable

    源码简单粗暴，直接用 synchronized 套上，所以并发度不行

    且不允许键和值为null，直接抛空指针异常。而HashMap的键值都可以为null

    迭代器的机制是 fail-safe，与之相对的HashMap中迭代器的机制是fail-fast

    • Fail-fast （java.util包下的集合类）

      在迭代器遍历一个集合对象时，如果遍历过程中对集合对象进行了修改，则会抛出 Concurrent Modification Exception

      使用 modCount 遍历来判断

    • fail-safe （java.util.concurrent）

      可以多线程并发使用

  3. CurrentHashMap

    JDK1.7

    和HashMap差不多，不同点是，使用 volatile 修饰了HashEntry，

    volatile三个特性

    • 可见性（不同线程对这个变量操作的可见性）
    • 有序性（禁止进行指令重排序）
    • 只能保证对单次读、写的原子性

    并发度高的原因：

    • 采用了分段锁，Segment 继承与 ReentrantLock
    • 支持 Segment数组数量的线程并发

    put的逻辑

    1. 获取锁
    2. 获取失败，采用自旋获取锁，重试次数达到 MAX_SCAN_RETRIES 则改为阻塞锁获取，保证能够获取成功

    get的逻辑

    1. 由于value属性是用 volatile 关键字，保证了内存可见性，所以每次获取都是最新值，整个过程不需要加锁

    基本上还是数组加链表的方式，查询的时候，会遍历链表，导致效率很低，和JDK1.7的HashMap是一样的问题

    JDK1.8

    采用了 CAS+synchronized 来保证并发安全性

    volatile修饰，且引入红黑树

    put的逻辑

    1. 根据key算出HashCode

    2. 利用CAS尝试写入，失败则自旋保证成功

      CAS是乐观锁的实现方式，类比mysql中 update … where

      条件可以是原来的值，也可以是版本号

    3. 判断是否需要扩容

    4. 都不满足，利用synchronized锁写入数据

      重量级锁，采用锁升级的方式，先使用偏向锁优先同一线程后再次获取锁，如果失败，就升级为CAS轻量级锁，如果失败就会短暂自旋，防止线程被系统挂起。如果都失败就升级为重量级锁

    5. 大于 TREEIFY_THRESHOLD 则转换为红黑树

    get的逻辑 – 和HashMap一致

    1. 根据计算出来的HashCode寻址
    2. 红黑树、列表取值

​

常见问题

  • 谈谈你理解的 Hashtable，讲讲其中的 get put 过程。ConcurrentHashMap同问。

  • 1.8 做了什么优化？

  • 线程安全怎么做的？

  • 不安全会导致哪些问题？

  • 如何解决？有没有线程安全的并发容器？

  • ConcurrentHashMap 是如何实现的？

  • ConcurrentHashMap并发度为啥好这么多？

  • 1.7、1.8 实现有何不同？为什么这么做？

  • CAS是啥？

  • ABA是啥？场景有哪些，怎么解决？

  • synchronized底层原理是啥？

  • synchronized锁升级策略

  • 快速失败（fail—fast）是啥，应用场景有哪些？安全失败（fail—safe）同问。

  • 在回答Hashtable和ConcurrentHashMap相关的面试题的时候，一定要知道他们是怎么保证线程安全的，那线程不安全一般都是发生在存取的过程中的，那get、put你肯定要知道。

    HashMap是必问的那种，这两个经常会作为替补问题，不过也经常问，他们本身的机制其实都比较简单，特别是ConcurrentHashMap跟HashMap是很像的，只是是否线程安全这点不同。

    提到线程安全那你就要知道相关的知识点了，比如说到CAS你一定要知道ABA的问题，提到synchronized那你要知道他的原理，他锁对象，方法、代码块，在底层是怎么实现的。

    synchronized你还需要知道他的锁升级机制，以及他的兄弟ReentantLock，两者一个是jvm层面的一个是jdk层面的，还是有很大的区别的。

    那提到他们两个你是不是又需要知道juc这个包下面的所有的常用类，以及他们的底层原理了？

##

FEATURED TAGS
java Spring IOC tech AOP dubbo 到底是什么 多线程 JVM WeeklyPapper(周报) redis spring
FRIENDS