- 集合容器概述
- Collection接口
- Map接口
- Jdk1.7到Jdk1.8 HashMap 发⽣了什么变化(底层)?
- 谈谈ConcurrentHashMap的扩容机制
集合容器概述
什么是集合
- 集合就是一个放数据的容器，准确的说是放数据对象引用的容器
- 集合类存放的都是对象的引用，而不是对象的本身
集合类型主要有3种：set(集）、list(列表）和map(映射)。
集合的特点
集合用于存储对象的容器，对象是用来封装数据，对象多了也需要存储集中式管理。
和数组对比对象的大小不确定。因为集合是可变长度的。数组需要提前定义大小
集合和数组的区别
数组是固定长度的；集合可变长度的。
- 数组可以存储基本数据类型，也可以存储引用数据类型；集合只能存储引用数据类型。
数组存储的元素必须是同一个数据类型；集合存储的对象可以是不同数据类型。
List，Set，Map三者的区别？
Java 容器分为 Collection 和 Map 两大类，Collection集合的子接口有Set、List、Queue三种子接口。
- Collection集合主要有List和Set两大接口
- List：一个有序（元素存入集合的顺序和取出的顺序一致）容器，元素可以重复，可以插入多个null元素，元素都有索引。常用的实现类有 ArrayList、LinkedList 和 Vector。
- Set：一个无序（存入和取出顺序有可能不一致）容器，不可以存储重复元素，只允许存入一个null元素，必须保证元素唯一性。Set 接口常用实现类是 HashSet、LinkedHashSet 以及TreeSet。
Map是一个键值对集合，存储键、值和之间的映射。 Key无序，唯一；value 不要求有序，允许重复。Map没有继承于Collection接口，从Map集合中检索元素时，只要给出键对象，就会返回对应的值对象。
Collection
- List
- Arraylist ：Object数组
- Vector ：Object数组 ，线程安全
- LinkedList ： 双向循环链表
- Set
- HashSet（无序，唯一）：基于 HashMap 实现的，底层采用 HashMap 来保存元素
- LinkedHashSet： LinkedHashSet 继承与 HashSet，并且其内部是通过 LinkedHashMap 来实现的。有点类似于我们之前说的LinkedHashMap 其内部是基于 Hashmap 实现一样，不过还是有一点点区别的。
- TreeSet（有序，唯一）： 红黑树(自平衡的排序二叉树。)
- List
Map
- HashMap： JDK1.8之前HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）.JDK1.8以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间
- LinkedHashMap：LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。
- HashTable： 数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突、而存在的
- TreeMap： 红黑树（自平衡的排序二叉树）
Collection接口
如何边遍历边移除 Collection 中的元素
边遍历边修改 Collection 的唯一正确方式是使用 Iterator.remove() 方法，如下：List list = new ArrayList();list.add("1");list.add("2");Iterator i = list.iterator();while (i.hasNext()) {if (i.next() == "1") {i.remove();}}
ArrayList 和 LinkedList 的区别是什么？
数据结构实现：ArrayList 是动态数组的数据结构实现，而 LinkedList 是双向链表的数据结构实现。
- 随机访问效率：ArrayList 比 LinkedList 在随机访问的时候效率要高，因为 LinkedList 是线性的数据存储方式，所以需要移动指针从前往后依次查找
- 增加和删除效率：在非首尾的增加和删除操作，LinkedList 要比 ArrayList 效率要高，因为
ArrayList 增删操作要影响数组内的其他数据的下标 - 内存空间占用：LinkedList 比 ArrayList 更占内存，因为 LinkedList 的节点除了存储数据，还存储了两个引用，一个指向前一个元素，一个指向后一个元素
- 线程安全：ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；
- 综合来说，在需要频繁读取集合中的元素时，更推荐使用 ArrayList，而在插入和删除操作较多时，更推荐使用 LinkedList。
- LinkedList 的双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点
多线程场景下如何使用 ArrayList？
最常用的方法是通过 Collections 的 synchronizedList 方法将 ArrayList 转换成线程安全的容器后再使用。List<Object> list =Collections.synchronizedList(new ArrayList<Object>);
说一下 HashSet 的实现原理？
HashSet实际上是一个HashMap实例，都是一个存放链表的数组。它不保证存储元素的迭代顺序；此类允许使用null元素。HashSet中不允许有重复元素，这是因为HashSet是基于HashMap实现的，HashSet中的元素都存放在HashMap的key上面，而value中的值都是统一的一个固定对象PRESENT。HashSet如何检查重复？HashSet是如何保证数据不可重复的？
检查重复
当向Set中添加对象时，首先调用此对象所在类的hashCode()方法，计算次对象的哈希值，此哈希值决定了此对象在Set中存放的位置；若此位置没有被存储对象则直接存储，若已有对象则通过对象所在类的equals()比较两个对象是否相同，相同则不能被添加。保证不重复
HashSet的add 方法，使用了HashMap的put()方法，利用hashmap的key不能重复的特性实现。
这个方法中根据key的hashCode()返回值决定该Entry的存储位置，如果两个key的hash值相同，那么它们的存储位置相同，如果这个两个key的equals比较返回true。那么新添加的Entry的value会覆盖原来的Entry的value，key不会覆盖。且HashSet中add()中 map.put(e, PRESENT)==null 为false，HashSet添加元素失败。因此,如果向HashSet中添加一个已经存在的元素，新添加的集合元素不会覆盖原来已有的集合元素Map接口
什么是Hash算法
哈希算法是指把任意长度的二进制映射为固定长度的较小的二进制值，这个较小的二进制值叫做哈希值。Jdk1.7到Jdk1.8 HashMap 发⽣了什么变化(底层)?
- 1.7中底层是数组+链表，1.8中底层是数组+链表+红⿊树，加红⿊树的⽬的是提⾼HashMap插⼊和查询整体效率
- 1.7中链表插⼊使⽤的是头插法，1.8中链表插⼊使⽤的是尾插法，因为1.8中插⼊key和value时需要判断链表元素个数，所以需要遍历链表统计链表元素个数，所以正好就直接使⽤尾插法
- 1.7中哈希算法⽐较复杂，存在各种右移与异或运算，1.8中进⾏了简化，因为复杂的哈希算法的⽬的就是提⾼散列性，来提供HashMap的整体效率，⽽1.8中新增了红⿊树，所以可以适当的简化哈希算法，节省CPU资源
说一下HashMap的实现原理？
HashMap JDK1.8之前
JDK1.8之前采用的是拉链法。拉链法：将链表和数组相结合。也就是说创建一个链表数组，数组
中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。HashMap JDK1.8之后
jdk1.8在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转化为红黑树，以减少搜索时间。
HashMap 基于 Hash 算法实现的
- 当我们往HashMap中put元素时，利用key的hashCode重新hash计算出当前对象的元素在数
组中的下标 - 存储时，如果出现hash值相同的key，此时有两种情况。
- 如果key相同，则覆盖原始值；
- 如果key不同（出现冲突），则将当前的key-value放入链表中
- 获取时，直接找到hash值对应的下标，在进一步判断key是否相同，从而找到对应值。
HashMap的put方法的具体流程？
hashmap1.7 put
- 先判断key是否为null，如果是null则会插入头结点table[0]的位置，
- key不等于null，计算key的hashCode值，对数组的大小取模，hash & (length-1)，得到在数组中的位置，如果数组上已经有元素了，那么遍历该位置上的元素，如果存在hash、key都相等，那么说明是同一个key，则将原来的值覆盖，并且返回原来的值oldValue。如果这个元素上找不到要添加的key，说明是一个新值，则使用头插法，插入元素链表的头部。头插法，在多线程情况下，有可能造成循环链表，形成死循环。
- 如果数组上没有元素，当前位置没有数据插入，那么会新增一个entry写入当前位置。
hashmap1.8 put
1.对key求哈希值然后计算下标
2.如果没有哈希碰撞直接放入槽中（没有哈希碰撞说明当前位置没有内容）
3.如果发生碰撞了就以链表的形式放到后面
4.如果链表长度超过阈值，就把链表转为红黑树
5.如果节点已经存在就替换旧值
6.如果槽满了就需要扩容，根据新的容量（2倍）新建一个数组，保存旧的数组，遍历旧数组的每一个数据，重新计算每个数据在新数组中的存储位置
请详细描述 HashMap 的get方法获取结果的过程？
- 调用 hash 方法计算hash值
- 调用getNode()方法如果数组为null，则直接返回null
- 如果数组不为null，看索引位置上对应的第一个元素是否满足（比较hash值和调用equals方法比较key）
- 满足的话直接返回该节点，不满足的话先看是不是红黑树，是的话就调用红黑树的get方法，不是的话则进行do while循环比较，如果最后一个节点满足的话就返回，如果还不满足就返回null
加载因子为什么是0.75？
负载因子为1，空间利用率得到了很大的满足，很容易碰撞，但是查询效率低
负载因子为0.5，碰撞的概率低，容易扩容，产生链表的几率低，但是空间利用率低
HashMap的扩容操作是怎么实现的？
一般情况下，当元素数量超过阈值时便会触发扩容。每次扩容的容量都是之前容量的2倍。JDK1.7
整个扩容过程就是一个取出数组元素,然后遍历以该元素为头的单向链表元素，依据每个被遍历元素的 hash 值计算其在新数组中的下标然后进行交换。即 头插法。这样在多线程扩容的时候可能会导致循环指向，从而在获取数据get()的时候陷入死循环，到是线程执行无法结束JDK1.8
采用尾插法，先插入数据，插入之后在判断下一次++size的大小是否会超过当前的阈值，如果超过就扩容。HashMap 的主数组长度为什么是2的幂次方
为了让HashMap更高效的存取，尽量减少碰撞，就是尽量把数据分配均匀，每个链表红黑树长度大致相同。方式是采用%取余来实现。当除数为2的幂次等价于其除数减一的与操作。结合源码说说HashMap在高并发场景中为什么会出现死循环？
HashMap进行存储时，假设size超过当前最大容量负载因子时候会发生resize。而resize()方法中又调用了transfer()方法，而这种方法实现的机制就是将每一个链表转化到新链表，而且链表中的位置发生反转，而这在多线程情况下是非常easy*造成链表回路。从而发生get()死循环。
HashMap在JDK1.8都做了哪些优化？
ConcurrentHashMap线程安全的具体实现方式/底层具体实现？
JDK1.7
ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。就是首先将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问
JDK1.8
ConcurrentHashMap取消了Segment分段锁，直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 CAS和synchronized来保证并发安全。
synchronized只锁定当前链表或红黑二叉树的首节点，这样只要hash不冲突，就不会产生并发，效率又提升N倍。
ConcurrentHashMap 和 Hashtable 的区别？
ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。
Hashtable 使用同一把锁，使用 synchronized 来保证线程安全，效率非常低下。
谈谈ConcurrentHashMap的扩容机制
1.7版本
若有收获，就点个赞吧
0 人点赞
