本文共 5267 字，大约阅读时间需要 17 分钟。

数据结构 | java中的集合

1. Set

Set属于Collection接口下的

1. 不包含重复元素的接口
2. 不包含索引
3. 不能使用普通的for循环遍历

1.0 Set的迭代：

Set hs = new HashSet();Iterator it = hs.iterator();        while (it.hasNext()) {
               System.out.println(it.next());        }

1.1 set去重原理

在如下代码中：

public static void main(String[] args) {
           HashSet
   
     set=new HashSet<>();        String s1=new String("abc");        String s2=new String("abc");                set.add(s1);        set.add(s2);        set.add("种地");        set.add("通话");        System.out.println(set);    }
   

调用add()方法时：会进行比较

1.2 HashSet

不能保证元素的排列顺序，顺序有可能发生变化， 而且线程不安全， 集合元素可以是null,但只能放入一个null

1. 实现了set接口
2. 是一个无序的集合
3. 底层是一个hash表结构：查询的速度非常快
4. 必须重写 hashCode() 和 equals()

HashSet数据结构： Hash表

哈希表 ：数组+链表 / 数组+红黑树

哈希表的特点：查询速度快

1.2.1 LinkedHashSet

继承自HashSet,实现了Set , 多了一个链表 （记录元素的存储顺序）保证元素有序

1. 方法和HashSet的方法一样
2. 具有可预知迭代顺序

LinkedHashSet<String> linked=new LinkedHashSet<>();

1.3 TreeSet

TreeSet类型是J2SE中唯一可实现自动排序的类型, TreeSet是SortedSet接口的唯一实现类，TreeSet可以确保集合元素处于排序状态。

当遍历该集合时候，LinkedHashSet将会以元素的添加顺序访问集合的元素。

TreeSet支持的排序方法：

1. 自然排序（默认） : 使用CompareTo(Object obj) 比较元素之间大小关系，然后将元素按照升序排列。
2. 定制排序

CompareTo() : Java提供了一个Comparable接口，该接口里定义了一个compareTo(Object obj)方法，该方法返回一个整数值，实现了该接口的对象就可以比较大小。

1. 返回0，被比较的两个对象相等，
2. 返回正数，则表明obj1大于obj2
3. 返回负数，则表明obj1小于obj2。

TreeSet判断两个对象不相等的方式

1. equals方法
2. CompareTo方法

2.List

List 属于Collection接口下的

2.1 ArrayList

ArrayList底层是由动态数组实现的。 默认长度为10

1. 扩容： 当添加元素超过当前数组时， 创建一个新数组，长度为之前的1.5倍， 然后旧数组数据移动到新数组

2. 数组是用来存储固定大小的同类型元素，数组存放位置是在jvm的堆中

3. 为什么增删的效率比较低？

   1. 当有新的元素需要存储时，添加在尾部， 如果超过最大值 ，则需要扩容。
   2. 如果删除一个元素，后面的元素都会向前移动一个位置
      因此，ArrayList在存储和删除的时候效率比较低。

4. 为什么查询效率高？

   由于每个元素占用的内存相同且是连续排列的，因此在查找的时候，根据元素的下标可以迅速访问数组中的任意元素，查询效率非常高。 时间复杂度为 O(1)

   公式：index * 偏移量

5. 使ArrayList线程安全的策略:

   1. 使用Vector，它是jdk1.1出现的，add方法有同步锁，能保证线程安全
   2. 使用Collections.synchronizedList(new ArrayList<>());
      List<String> k=Collections.synchronizedList(new ArrayList<>());
   3. 使用CopyOnWriteArrayList List<String> k=new CopyOnWriteArrayList<>();

2.2 LinkedList

LinkedList底层是由双向链表的数据结构实现的。

双向链表单个节点的构成：

1. prev ：由用来存储上一个节点的地址；
2. data ：是用来存储要存储的数据；
3. next : 由用来存储下一个节点的地址；

双向链表：

1. 为什么删除高效查询低效？

   比如要删除数据8的元素，只需要修改数据7的next值和数据9的prev值即可，然后数据8没有元素指向它，它就成了垃圾对象，最后被回收。因此在增加和删除的时候只需要更改前后元素的next和prev值，效率非常高。

   但是在查询的时候需要从第一个元素开始查找，直到找到我们需要的数据为止，因此查询的效率比较低。

2. 使LinkedList线程安全的策略:

3. List<String> list = Collections.synchronizedList(new LinkedList<String>());

4. LinkedList换成ConcurrentLinkedQueue

5. Vector

2.3 Vector

Vector 类实现了一个动态数组。和 ArrayList 很相似，但是两者是不同的：

1. Vector 是同步访问的。
2. Vector 包含了许多传统的方法，这些方法不属于集合框架。

2.3.1 Vector 为什么线程安全：

构造方法还有增删改查的操作，都有这么一个 synchronized关键字，就是这个关键字为Vector容器提供了一个安全机制，保证了线程安全

2.4 ArrayList 和LinkedList的区别

1. 底层结构不一样， Arr是一块连续的空间；Linked不连续；
2. Arr适合查询，linked适合增删；
3. LinkedList需要更多的内存，因为ArrayList的每个索引的位置是实际的数据，而LinkedList中的每个节点中存储的是实际的数据和前后节点的位置。
4. 使用场景不同：
   1. 如果应用程序对数据有较多的随机访问，ArrayList对象要优于LinkedList对象；
   2. 如果应用程序有更多的插入或者删除操作，较少的随机访问，LinkedList对象要优于ArrayList对象；
   3. 不过ArrayList的插入，删除操作也不一定比LinkedList慢，如果在List靠近末尾的地方插入，那么ArrayList只需要移动较少的数据，而LinkedList则需要一直查找到列表尾部，反而耗费较多时间，这时ArrayList就比LinkedList要快。

2.5 Array和ArrayList区别

可以将ArrayList想象成一种“会自动扩增容量的Array

区别:

1. Array() ：最高效；但是其容量固定且无法动态改变；

2. ArrayList() ：容量可动态增长；但牺牲效率；

3. Arrays类没有提供删除方法，而ArrayList中有remove()方法

基于效率和类型检验，应尽可能使用Array，无法确定数组大小时才使用ArrayList！

3.Map

Map核心方法

put()  向Map中添加数据 get() 根据指定的key值取得相应的value值，若没有测value值，返回null。 entrySet()  将Map集合变为Set集合 KeySet()  返回所有key值集合，key不能重复 values()  返回所有value值，value可以重复。

3.1 Hashtable

Hashtable是最早实现二元偶对象数据结构，后期的设计也让其与Vector一样多实现了Map接口而已。

是早期 Java 类库提供的一个哈希表实现，本身是同步的，不支持 null 键和值，由于同步导致的性能开销，所以已经很少被推荐使用。Hashtable:单纯的哈希表实现

3.1.1 为什么Hashtable线程安全

• 在put、get、remove等方法上使用方法级的内建锁( Synchronized ),锁的是当前Hashtable对象，即整个哈希表
• 因为内建锁锁住了当前table对象，所以当访问一个桶时就会把整个哈希表锁住，效率比较低

3.1.2 如何优化性能?

1）JDK8之前ConcurrentHashMap思路:

通过锁细粒度化，将整表锁拆分为多个锁进行优化。

将原先的16个桶设计改为16个Segment,每个Segment都有独立的一把锁。拆分后的每个Segment都相当于原先的一个HashMap(double-hash设计).并且Segment在初始化后无法扩容，每个Segment对应的哈希表可以扩容,扩容只扩容相应Segment下面的哈希表。Segment之间相互不影响

先判断我在哪个segment下面，然后再hash一次判断我在哪个segment的哪个具体的桶里面，然后进行链表存储。JDK1.7concurrentHashMap底层是两个哈希表的嵌套

线程安全 : 使用 ReentrantLock保证相应Segment下的线程安全

3.2 HashMap

是应用更加广泛的哈希表实现，行为上大致上与 HashTable 一致，主要区别在于HashMap 不是同步的，支持 null 键和值等。通常情况下，HashMap 进行 put 或者 get 操作，可以达到常数时间的性能，所以它是绝大部分利用键值对存取场景的首选，比如，实现一个用户 ID和用户信息对应的运行时存储结构。

3.2.1 HashMap源码解析

HashMap重要参数如下：

1	DEFAULT_INITIAL_CAPACITY(初始化容量-桶数量) : 16         2	DEFAULT_LOAD_FACTOR(负载因子): 0.75         3	TREEIFY_THRESHOLD(树化阈值) : 8（默认是8，可以改）         4	MIN_TREEIFY_CAPACITY(树化最少元素个数) : 64         5	UNTREEIFY_THRESHOLD(解树化，返回链表的阈值) : 6         6	Node
   
    [] table : 真正存储元素的哈希表
   

3.2.1 LinkedHashMap

在HashMap下有一个子类:LinkedHashMap,有序Map，序指的是元素的添加顺序

3.4 TreeMap

TreeMap 则是基于红黑树的一种提供顺序访问的 Map，和 HashMap 不同，它的 get、put、remove 之类操作都是 O（log(n)）的时间复杂度，具体顺序可以由指定的 Comparator 来决定，或者根据键的自然顺序来。TreeMap有序Map,序指的是Comparator或Compareable

3.5 ConcurrentHashmap

1. JDK 1.8之前 : segment( ReentrantLock )做分段锁 ,锁住一片区域

2. JDK 1.8之后: segment( Sychornized + CAS ), 锁住桶的头结点 , 此时sychronized性能已经优化的很高了, 而且可以节省大量空间（原来ReentrantLock下的segment都得加入同步队列，都得继承AQS下的Node，而synchronized只是锁住头结点，头结点下边的节点都不会加入同步队列里，所以 节省了空间），这是非常大的优势所在。

3.6 AQS:

ReentrantLock 中的 AbstractQueuedSynchronizer（AQS）！

类如其名，抽象的队列式的同步器，AQS定义了一套多线程访问共享资源的同步器框架，许多同步类实现都依赖于它，如常用的 ReentrantLock / Semaphore / CountDownLatch …。

---

4. Set接口与Map接口的关系:

public Set<Map.Entry<K,V>> entrySet()：将Map集合变为Set集合

Set接口是穿了马甲的Map接口,本质上Set接口的子类都是使用Map来存储元素的，都是将元素存储到Map的key值而已，value都是用共同的一个空Object对象。

转载地址：https://blog.csdn.net/weixin_40597409/article/details/115381061 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！