集合

1. 集合概念

1. 集合是存储数据的容器
2. 集合与数组的区别
   1. 集合的长度是不固定的，数组是固定的
   2. 集合只能存储引用类型的变量，数组能存放基本数据类型和引用类型
   3. 一个集合里面可以存放不同类型的数据，数组只能存放同一种

2.常见集合类

1. controller类：包括set、list
2. map类

3.list类

1. list是一个有序可重复的容器，允许多个null值，元素都有索引
2. 常用实现类：
   1. arraylist：
      • 底层是数组，它实现了randomAccess接口，查找效率高，但是插入和删除元素的时候，需要做一次复制操作，效率就比较低
      • 线程不安全
      • 如果要实现线程安全，可以使用controllers 下的synchronizedList（）来实现，Collections.synchronizedList(list)
      • 扩容：50%
   2. vector：
      • 底层是数组
      • 比ArrayList多了一个线程安全
      • 扩容：100%
   3. linkedlist：
      • 双向链表
      • 线程不安全2
3. list类与数组的转换：
   • list – 数组：toArray()
   • 数组 – list：asList()

4.set类

1. set是一个无序不可重复的容器，只能有一个null值
2. 常用实现类
   1. hashset：
      • 无序唯一
      • 底层是HashMap
   2. linkedhashset：
      • 继承于hashset
      • 底层是HashMap
   3. treeset：
      • 有序唯一
      • 底层是红黑树

5.map类

1. map是一个键值对集合、存储值、值之间的映射，它的key是无序唯一的，只能有一个null值，value无序不要求唯一
2. 常用实现类
   1. HashMap：
      • JDK1.8之前是数组 + 链表； JDK1.8是数组 + 链表 + 红黑树
   2. treemap：
      • 底层是红黑树
   3. hashtable：
      • 数组 + 链表
      • 比HashMap多了一个线程安全（），（synchronized）
   4. linkedHashMap：
      • 在HashMap的基础上加一条双向链表，提高插入效率
   5. concurrentHashMap：
      • JDK1.8之前是segment + hashentry； JDK1.8是数组 + 链表 + 红黑树
      • 线程安全（JDK1.7之前分段锁，之后使用synchronized 和 CAS来控制并发）
      • 不允许null值

6.快速失败机制：fail-fast

多线程访问一个集合时，如果一个线程正在访问的集合，被另一个线程修改了集合的结构，就会产生fail-fast，这是一种错误检测机制

7.只读集合

controllers下有一个unmodifiablecontroller方法可以用来创建一个只读的集合

8.迭代器

1. lterator接口提供了遍历所有controller的接口（不包括map）
2. iterator只能单向遍历
3. 通过controller . iterator（）方法获取迭代器实例
4. iterator . remove () 方法可以边遍历，边移除元素
5. 如果需要双向遍历，则可以使用其子接口，listiterator

9.queue

1. blockingQueue是一个队列，在检索或者移除一个元素时，它会等待队列变为非空，当添加一个元素时，它会等待队列有可用空间，可用用来实现生产者-消费者模式

10.HashMap的实现原理

1. HashMap是基于hash算法实现的
   • 在put一个元素时，需要使用key的hashcode计算出它在数组中的下标
   • 如果出现hash值相同的情况，则通过equals比较key是否相同，如果相同则用新值替换旧值，如果不同，则新值放入链表中
   • 在get一个元素时，通过hash值，找到数组的下标，再判断key值是否相同就可以获得value
2. JDK1.8中，HashMap底层的实现
   • 在数组长度大于64且链表长度大于8时，链表才转换成红黑树（数组长度小于64时，优先扩容）
   • 扩容机制：
     • 在HashMap初始化或者键值对数量大于阈值是调用resize（）
     • 每次扩展都是扩展为原来长度的2倍
     • 扩容之后的长度都是2的次幂，如果指定扩容的长度不是2的次幂，那么其长度会自动扩容为比指定长度大的最小一个次幂数，比如，指定长度为7，实际扩容长度为8
     • 加载因子：0.75（时间与空间成本上的折中）
3. hash冲突
   • 碰撞，不同元素通过hashcode（）计算出来相同的hash值
   • 解决：hash（）中做扰动，JDK1.7进行了9次扰动，1.8中值进行了两次（1次位运算，1次异或运算）；引入红黑树，降低遍历的时间复杂度

11.comparable和comparator

• comparable是lang包下，使用compareTo(object obj）实现排序
• Comparator是util包下，使用compare（object obj1 ， object obj2）实现排序

最后

以上就是洁净蜡烛为你收集整理的面试笔记-集合集合的全部内容，希望文章能够帮你解决面试笔记-集合集合所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。