集合体系【List+Set+Map+HashMap+TreeSet】

目录

1HashMap原理

2List、Set、Map的区别？看这个就够了

细说ArrayList和LinkedList区别

3HashMap和HashTable的区别

4什么是ConcurrentHashMap?

5TreeSet

---

1HashMap原理

HashMap底层是基于数组+链表+红黑树。

默认初始容量为（数组长度为**16），默认负载系数为0.75（这个表示的意思是扩容机制当容量达到75%的时候自动进行扩容（扩大一倍，扩容也是采用位运算【因为用乘法会影响CPU的性能，计算机不支持乘法运算，最终都会转化为加法运算[01的方式]。】），当扩容的时候，会创建新的数组，以前存放的数组将会重新通过hashCode进行排序，类似于hashCode/16取模【其实使用的是位运算，位运算效率更高】得到下标存放在对应的数组中，扩容后hashCode/32.）。

底层原理：

1.先通过hash算法计算出当前键值的hashCode值，然后对数组长度进行取模【其实是位运算，

hash值取模和位运算执行效果是一样的，位运算执行效果比较高】，从而获得余数（即为下标）存储到对应的数组中【存储的是当前hash值（key计算的hash值），key，value和next】（所以HashMap存取数据元素是无序的）。[底层是位运算，性能更好，且可以更好的避免哈希碰撞]

2.通过下标存储键值时，如果当前下标没有存放其他键值时会直接存入，如果该下标处，已经存在其他键值时，则会发生哈希碰撞。

3.发生哈希碰撞后，会继续比较下标处所有key的equals（内容）是否为true（来判断是不是同一个元素。）

如果是true，表示是相同的key，执行覆盖操作。

如果是false，表示是不同的key，执行在最后一个键值对后面追加操作，从而形成单向链表（链表的产生）。

4.如果链表长度>=8个且当前Map集合中数组长度>=64个，则会形成红黑树；如果当前数组长度<64个，则会扩容键值对数组（16*2），而且会重新进行排序。（并且会重新将所有键值对对32进行取余重新排序进行存储从而导致效率低）

5.当调用remove方法的时候，会删除元素，当红黑树中剩余的键值对个数<=6个的时候，会重新还原成单向链表。（性能更好）

2List、Set、Map的区别？看这个就够了

Collection接口

List：采用一个一个的数据进行存储（单列集合），存储数据是有序可重复的，，可以插入多个null元素，元素都有索引**。常用的实现类有 ArrayList、LinkedList 和 Vector。

• ArrayList：底层数据结构是Object动态数组，查改性能高（通过下标），增删性能低，线程不安全

• LinkedList：底层数据结构是双向链表，查询性能低（从头开始查询），增删性能高，线程不安全

  

• Vector（线程安全的arraylist）：底层数据结构是数组，查询性能高，增删性能低，线程安全

=======================================

细说ArrayList和LinkedList区别

ArrayList:底层基于Object的动态数组（可以进行动态扩容、缩容 起始容量为10**--扩容是当前容量的1.5倍【oldCapacity，将当前容量的二进制数右移1位后再转为十进制再加上以前的旧容量(你可以用笔算一下，其实就是当前容量的1.5倍)】）。适用于经常查改【**为什么查改块？？？===通过索引进行直接查找和修改--不会改变数组的长度，从而不会进行动态缩容和扩容降低了执行效率，因为每次添加和删除都会造成数据的移动，非常消耗性能】的场景，线程不安全。存取元素（有序，可重复）【代码修改-** array.set(1,"nihao")； 查找-array.get(0)

LinkedList：底层基于双向链表（也是与ArrayList的本质区别）【为了能把相关联的数据连续起来，那么链表就必须在前一个数据节点的存储空间中记录下下一块的数据节点的前置节点的地址，下一块的数据节点就需要记录上一个数据节点Node的前置节点地址。这样才能达到所有的数据环环相扣，联系起来成为一个整体。】。适用于经常增删**【为什么增删快？？？===因为增加只需要插入元素，将上一块元素和下一块的元素的数据存储地址更换成插入元素的存储地址即可，删除同理。--如图】的场景，线程不安全**。存取元素（有序，可重复）

=======================================

Set：set的底层实现其实是Map，采用一个一个的数据进行存储（单列集合）存储数据时无序不可重复的【将存储的数据当作map的key，value为一个new Object】，只允许存入一个null元素，必须保证元素唯一性。Set 接口常用实现类是 HashSet、LinkedHashSet 以及 TreeSet。

• HashSet：无序不重复的，使用HashMap的key存储元素，判断key值的重复依据是hashCode()和equals()，线程不安全。

• TreeSet：有序不重复的，底层使用TreeMap的key存储元素,Value为new Object，排序方式分为自然排序【实现comparable接口，重写compareTo方法】，定制排序（比较器排序）【匿名内部类创建new Comparator，重写compare方法定制排序规则】线程不安全。

• LinkedHashSet;底层基于LinkedHashMap（哈希表和链表实现的接口）（从而存取元素是有序的-链表,就是为了让HashSet存储有序），线程不安全，集合中可以添加单个null。

Map接口：采用键值对的方式进行存储数据（双列集合），key值不能重复；value 允许重复**。从Map集合中检索元素时，只要给出键对象，就会返回对应的值对象。

• HashMap：底层是数组+链表+红黑树，key的值没有顺序，线程不安全

• LinkedHashMap：底层数据结构由链表和哈希表组成，保证了存储数据的有序性。

• TreeMap：key的值可以自然排序，线程不安全

• HashTable：它的key和value都不允许为null，线程安全

• Properties：它的key和value都是String类型的，线程安全

3HashMap和HashTable的区别

HashMap和HashTable都是实现了Map接口的集合框架，他们的区别

• HashTable是线程安全的，它的实现方法都加了synchronized关键字，因此它的性能较低

• HashMap是线程不安全的，它实现方法没有加synchronized，因此它的性能较高

• HashMap的key和value都允许为null，HashTable中的key和value都不能为null,如果不考虑线程安全，建议使用HashMap，通过查询网上资料，前两者线程并发度并不高，容易发生大面积阻塞。如果需要考虑线程安全的高并发实现，建议使用ConcurrentHashMap，因为ConcurrentHashMap使用了CAS+Synchronized保证线程安全，他的性能和效率高于hashtable。

4什么是ConcurrentHashMap?

// 具体细节看下面这篇文章【ConcurrentHashMap如何保证线程安全的。】

什么是ConcurrentHashMap？_GuGuBirdXXXX的博客-CSDN博客

• ConcurrentHashMap：ConcurrentHashMap:使用锁分段技术确保线性安全，是一种高效但是线程安全的集合。它是HashMap的线程安全，支持高并发的版本.

• 在jdk1.7中，它是通过分段锁的方式来实现线程安全的。意思是将哈希表分成许多片段Segment，而Segment本质是一个可重入的互斥锁，所以叫做分段锁。

• 在jdk1.8中，它是采用了CAS操作和synchronized来实现的，而且每个Node节点的value和next都用了volatile关键字修饰，保证了可见性

5TreeSet

        有序不重复的，底层使用TreeMap的key存储元素,Value为new Object，排序方式分为自然排序【实现comparable接口，重写compareTo方法】，定制排序（比较器排序）【匿名内部类创建new Comparator，重写compare方法定制排序规则】线程不安全。

集合对象如何实现自然排序和定制排序？_GuGuBirdXXXX的博客-CSDN博客+