java List Map 常见面试题总结

java集合框架为我们提供了一套性能优良、使用方便的接口和类,它们都位于java.util包中。集合框架是一种为表示和操作而规定的一种统一的彼岸准体系结构。

java集合框架

• Collection 类关系图
  • 容器，就是可以容纳其他Java对象的对象。*Java Collections Framework(JCF)*为Java开发者提供了通用的容器，其始于JDK 1.2，优点是: 降低编程难度 提高程序性能 提高API间的互操作性 降低学习难度 降低设计和实现相关API的难度 增加程序的重用性 Java容器里只能放对象，对于基本类型(int, long, float, double等)，需要将其包装成对象类型后(Integer, Long, Float, Double等)才能放到容器里。很多时候拆包装和解包装能够自动完成。这虽然会导致额外的性能和空间开销，但简化了设计和编程
  • Map
    • TreeMap
      • 基于红黑树实现。
    • HashMap
      • 基于哈希表实现
    • HashTable
      • 和 HashMap 类似，但它是线程安全的，这意味着同一时刻多个线程可以同时写入 HashTable 并且不会导致数据不一致。它是遗留类，不应该去使用它。现在可以使用 ConcurrentHashMap 来支持线程安全，并且 ConcurrentHashMap 的效率会更高，因为 ConcurrentHashMap 引入了分段锁。
    • LinkedHashMap
  • Collection
    • Set
      • TreeSet
        • 基于红黑树实现，支持有序性操作，例如根据一个范围查找元素的操作。但是查找效率不如 HashSet，HashSet 查找的时间复杂度为 O(1)，TreeSet 则为 O(logN)。
      • HashSet
        • 基于哈希表实现，支持快速查找，但不支持有序性操作。并且失去了元素的插入顺序信息，也就是说使用 Iterator 遍历 HashSet 得到的结果是不确定的
      • LinkedHashSet
        • 具有 HashSet 的查找效率，且内部使用双向链表维护元素的插入顺序。
    • List
      • ArrayList
        • 基于动态数组实现，支持随机访问。
      • Vector
        • 和 ArrayList 类似，但它是线程安全的。
      • LinkedList
        • 基于双向链表实现，只能顺序访问，但是可以快速地在链表中间插入和删除元素。不仅如此，LinkedList 还可以用作栈、队列和双向队列。
    • Queue
      • LinkedList
        • 可以用它来实现双向队列。
      • PriorityQueue
        • 基于堆结构实现，可以用它来实现优先队列。
• List
  • Collection- ArrayList源码解析
    • 概述
      • 与它类似的是LinkedList，和LinkedList相⽐，它的查找和访问元素的速度较快，但新增，删除的速度较慢 ①ArrayList 通过数组实现，一旦我们实例化 ArrayList 无参数构造函数默认为数组初始化长度为 10 ②,add 方法底层实现如果增加的元素个数超过了 10 个，那么 ArrayList 底层会新生成一个数组，长度为原数组的 1.5 倍+1，然后将原数组的内容复制到新数组当中，并且后续增加的内容都会放到新数组当中。 当新数组无法容纳增加的元素时，重复该过程。是一旦数组超出长度，就开始扩容数组。扩容数组调用的方法 Arrays.copyOf(objArr, objArr.length + 1);
    • ArrayList的实现
      • 底层数据结构
      • 构造函数
      • 自动扩容
        • ArrayList的扩容主要发生在向ArrayList集合中添加元素的时候，通过add()方法添加单个元素时，会先检查容量，看是否需要扩容。如果容量不足需要扩容则调用grow()扩容方法，扩容后的大小等于扩容前大小的1.5倍，也就是10+10/2。比如说超过10个元素时，会重新定义一个长度为15的数组。然后把原数组的数据，原封不动的复制到新数组中，这个时候再把指向原数的地址换到新数组。
      • add(),addAll()
      • set()
      • get()
      • remove()
      • trimToSize()
      • Fail-Fast机制
        • 在遍历集合的时候，如果集合结构发生变化的话，会抛出异常，防止继续遍历
    • indexOf(),lastIndexOf()
    • 参考
  • Collection- LinkedList源码解析
    • 概述
      • LinkedList本质是采用双向链表的方式实现List接口，因此在进行 插入 和 移除操作时效率较高，适合用来实现Stack（先进后出）和Queue（先进先出）.
    • LinkedLists实现
      • 底层数据结构
      • 构造函数
      • getFirst(),getLast（）
      • removeFirest（），removeLast(),remove（e）,remove（index）
      • add()
      • addAll()
      • clear()
      • Positional Access方法
      • 查找操作
      • Queue方法
      • Deque方法
    • 参考
  • Collection-Stack&Q ueue源码解析
    • Stack&Queue概述
    • Queue
      • Queue<String> queue = new LinkedList<String>();
      • 添加元素
        • queue.offer("a");
      • 返回第一个元素，并在队列中删除
        • queue.poll()
      • 返回第一个元素
        • queue.peek()
    • Deque
    • 方法剖析
      • addFirst（）
      • addLast()
      • pollFirst()
      • pollLast()
      • peekFirst()
      • peekLast
  • Collection-Priority Queue源码解析
    • 概述
    • 方法剖析
      • add()和offer（）
      • element()和peek()
      • remove()和poll()
      • remove（Object o）
    • 参考
• Map
  • Map - TreeSet & TreeMap 源码解析
    • 总体介绍
      • 与HashMap相比，TreeMap是一个能比较元素大小的Map集合，会对传入的key进行了大小排序。其中，可以使用元素的自然顺序，也可以使用集合中自定义的比较器来进行排序； 出于性能原因，TreeMap是非同步的(not synchronized)，如果需要在多线程环境使用，需要程序员手动同步；或者通过如下方式将TreeMap包装成(wrapped)同步的: SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...)); 红黑树是一种近似平衡的二叉查找树，它能够确保任何一个节点的左右子树的高度差不会超过二者中较低那个的一倍。具体来说，红黑树是满足如下条件的二叉查找树(binary search tree): 每个节点要么是红色，要么是黑色。 根节点必须是黑色 红色节点不能连续(也即是，红色节点的孩子和父亲都不能是红色)。 对于每个节点，从该点至null(树尾端)的任何路径，都含有相同个数的黑色节点。
    • 预备知识
      • 左旋
      • 右旋
      • 寻找节点后继
    • 方法剖析
      • get()
      • put（）
      • remoce()
    • TreeSet
  • Map-HashSet& HashMap源码解析
    • Java7 HashMap
      • 概述
      • get()
      • put()
      • remove（）
    • java8 HashMap
      • put过程分析
        • 谈一下hashMap中put是如何实现的？ 1.计算关于key的hashcode值（与Key.hashCode的高16位做异或运算） 2.如果散列表为空时，调用resize()初始化散列表 3.如果没有发生碰撞，直接添加元素到散列表中去 4.如果发生了碰撞(hashCode值相同)，进行三种判断 4.1:若key地址相同或者equals后内容相同，则替换旧值 4.2:如果是红黑树结构，就调用树的插入方法 4.3：链表结构，循环遍历直到链表中某个节点为空，尾插法进行插入，插入之后判断链表个数是否到达变成红黑树的阙值8；也可以遍历到有节点与插入元素的哈希值和内容相同，进行覆盖。 5.如果桶满了大于阀值，则resize进行扩容
      • get过程分析
        • 对key的hashCode进行hashing，与运算计算下标获取bucket位置，如果在桶的首位上就可以找到就直接返回，否则在树中找或者链表中遍历找，如果有hash冲突，则利用equals方法去遍历链表查找节点。
      • 数组扩容resize()
        • 谈一下hashMap中什么时候需要进行扩容，扩容resize()又是如何实现的？ 当链表长度大于8，且数组的长度大于64时候会转化为红黑树 当使用的数组达到3/4的时候会发生扩容（如果是很小会导致很多很多bucket没有满就扩容，浪费空间，如果太大会导致hash碰撞，所以折中取0.75） 1.通过判断旧数组的容量是否大于0来判断数组是否初始化过 否：进行初始化 判断是否调用无参构造器， 是:使用默认的大小和阙值 否:使用构造函数中初始化的容量，当然这个容量是经过tableSizefor计算后的2的次幂数 是，进行扩容，扩容成两倍(小于最大值的情况下)，之后在进行将元素重新进行与运算复制到新的散列表中 概括的讲：扩容需要重新分配一个新数组，新数组是老数组的2倍长，然后遍历整个老结构，把所有的元素挨个重新hash分配到新结构中去。因为扩容的大小是二倍所以过程就不需要计算hash值了，但是会进行链表拆分 例如：一个链表开始是容量为16的，hash值为31，他会放到位置15的桶里面，当扩容之后容量就变成32了，他就该放到位置为31的桶里面 PS：可见底层数据结构用到了数组，到最后会因为容量问题都需要进行扩容操作
      • 面试问题
        • 6.谈一下HashMap中hash函数是怎么实现的？还有哪些hash函数的实现方式？ 对key的hashCode做hash操作，与高16位做异或运算 还有平方取中法，除留余数法，伪随机数法 7.为什么不直接将key作为哈希值而是与高16位做异或运算？ 因为数组位置的确定用的是与运算，仅仅最后四位有效，设计者将key的哈希值与高16为做异或运算使得在做&运算确定数组的插入位置时，此时的低位实际是高位与低位的结合，增加了随机性，减少了哈希碰撞的次数。 HashMap默认初始化长度为16，并且每次自动扩展或者是手动初始化容量时，必须是2的幂。 8.为什么是16？为什么必须是2的幂？如果输入值不是2的幂比如10会怎么样？ 1.为了数据的均匀分布，减少哈希碰撞。因为确定数组位置是用的位运算，若数据不是2的次幂则会增加哈希碰撞的次数和浪费数组空间。(PS:其实若不考虑效率，求余也可以就不用位运算了也不用长度必需为2的幂次) 2.输入数据若不是2的幂，HashMap通过一通位移运算和或运算得到的肯定是2的幂次数，并且是离那个数最近的数字 10.如果两个键的hashcode相同，你如何获取值对象？ HashCode相同，通过equals比较内容获取值对象 11."如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？ 超过阙值会进行扩容操作，概括的讲就是扩容后的数组大小是原数组的2倍，将原来的元素重新hashing放入到新的散列表中去。 12.HashMap和HashTable的区别 相同点：都是存储key-value键值对的 不同点： HashMap允许Key-value为null，hashTable不允许； hashMap没有考虑同步，是线程不安全的。hashTable是线程安全的，给api套上了一层synchronized修饰; HashMap继承于AbstractMap类，hashTable继承与Dictionary类。 迭代器(Iterator)。HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的。所以当有其它线程改变了HashMap的结构（增加或者移除元素），将会抛出ConcurrentModificationException。 容量的初始值和增加方式都不一样：HashMap默认的容量大小是16；增加容量时，每次将容量变为"原始容量x2"。Hashtable默认的容量大小是11；增加容量时，每次将容量变为"原始容量x2 + 1"； 添加key-value时的hash值算法不同：HashMap添加元素时，是使用自定义的哈希算法。Hashtable没有自定义哈希算法，而直接采用的key的hashCode()。 13.请解释一下HashMap的参数loadFactor，它的作用是什么？ loadFactor表示HashMap的拥挤程度，影响hash操作到同一个数组位置的概率。默认loadFactor等于0.75，当HashMap里面容纳的元素已经达到HashMap数组长度的75%时，表示HashMap太挤了，需要扩容，在HashMap的构造器中可以定制loadFactor。 14.传统hashMap的缺点(为什么引入红黑树？)： JDK 1.8 以前 HashMap 的实现是 数组+链表，即使哈希函数取得再好，也很难达到元素百分百均匀分布。当 HashMap 中有大量的元素都存放到同一个桶中时，这个桶下有一条长长的链表，这个时候 HashMap 就相当于一个单链表，假如单链表有 n 个元素，遍历的时间复杂度就是 O(n)，完全失去了它的优势。针对这种情况，JDK 1.8 中引入了 红黑树（查找时间复杂度为 O(logn)）来优化这个问题。 15. 平时在使用HashMap时一般使用什么类型的元素作为Key？ 选择Integer，String这种不可变的类型，像对String的一切操作都是新建一个String对象，对新的对象进行拼接分割等，这些类已经很规范的覆写了hashCode()以及equals()方法。作为不可变类天生是线程安全的，
    • hashSet
    • hashtable
      • 面试问题
        • hashtable 线程安全吗？ 线程安全，因为他的方法是同步的
    • ConcurrentHashMap
      • 面试问题
        • 底层采用分段的数组 + 链表实现 ，线程安全 通过把整个Map分为N个Segment,可以提供相同的线程安全，但是效率提升n倍，默认提成16倍（读操作不加锁，由于HashEntry的value是volatile，也能保证读取到最新值） HashTable是针对整个Hash表的，每次锁住整个表让线程独占，ConcurrentHashMap允许多个修改操作并发进行，其关键在于使用了锁分离技术 有些方法需要跨段，比如size() 和containsValue()，他们可能需要锁定整个表而不仅仅是某个段 这需要按需锁定所有段，操作完毕后又按需释放所有段 扩容：段内扩容（段内元素超过改对应Entry数组长度的75%触发扩容，不会对整个Map进行扩容），插入 前检测需不需要扩容，有效避免无效扩容
  • Map - LinkedHash Set&Map源码解析
    • 总体介绍
      • 2.谈一下HashMap的底层原理是什么？ 基于hashing的原理，jdk8后采用数组+链表+红黑树的数据结构。我们通过put和get存储和获取对象。当我们给put()方法传递键和值时，先对键做一个hashCode()的计算来得到它在bucket数组中的位置来存储Entry对象。当获取对象时，通过get获取到bucket的位置，再通过键对象的equals()方法找到正确的键值对，然后在返回值对象。
    • 方法剖析
      • get()
      • put()
      • remove
    • LinkedhashSet
    • LinkedhashMap经典用法
  • Map - WeakHash Map源码解析