集合

Collection包结构，与Collections的区别

Collection是集合类的上级接口，子接口有 Set、List、LinkedList、ArrayList、Vector、Stack、Set；Collections是集合类的一个帮助类， 它包含有各种有关集合操作的静态多态方法，用于实现对各种集合的搜索、排序、线程安全化等操作。此类不能实例化，就像一个工具类，服务于Java的Collection框架。

说说List,Set,Map三者的区别？

  • List(对付顺序的好帮手)： List接口存储一组不唯一（可以有多个元素引用相同的对象)，有序的对象
  • Set(注重独一无二的性质): 不允许重复的集合。不会有多个元素引用相同的对象。
  • Map使用键值对存储。Map会维护与Key有关联的值。两个Key可以引用相同的对象，但Key不能重复，典型的Key是String类型，但也可以是任何对象。

ArrayList和linkedList的区别

Array（数组）是基于索引(index)的数据结构，它使用索引在数组中搜索和读取数据是很快的。

Array获取数据的时间复杂度是O(1),但是要删除数据却是开销很大，因为这需要重排数组中的所有数据, (因为删除数据以后, 需要把后面所有的数据前移)

缺点: 数组初始化必须指定初始化的长度, 否则报错

例如:

int[] a = new int[4];//推介使用int[] 这种方式初始化
int c[] = {23,43,56,78};//长度：4，索引范围：[0,3]

List—是一个有序的集合，可以包含重复的元素，提供了按索引访问的方式，它继承Collection。

List有两个重要的实现类：ArrayList和LinkedList

ArrayList: 可以看作是能够自动增长容量的数组

ArrayList的toArray方法返回一个数组

ArrayList的asList方法返回一个列表

ArrayList底层的实现是Array, 数组扩容实现

LinkList是一个双链表,在添加和删除元素时具有比ArrayList更好的性能.但在get与set方面弱于

ArrayList.当然,这些对比都是指数据量很大或者操作很频繁。

1.是否保证线程安全： ArrayList和LinkList全都是不同步的，也就是不保证线程安 2.底层数据结构：ArrayList底层使⽤的是数组； LinkedList 底层使⽤的是双向链表 数据结构（JDK1.6之前为循环链表，JDK1.7取消了循环。注意双向链表和双向循环链表的区别，下⾯有介绍到！） 3.插⼊和删除是否受元素位置的影响： ① ArrayList 采⽤数组存储，所以插⼊和删除元素的时间复杂度受元素位置的影响。 ⽐如：执⾏ add(E e) ⽅法的时候，ArrayList会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是O(1)。但是如果要在指定位置 i插⼊和删除元素的话（ add(int index, E element) ）时间复杂度就为 O(n-i)。因为在进⾏上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执⾏向后位/向前移⼀位的操作。 ②LinkList采⽤链表存储，所以对于 add(E e) ⽅法的插⼊，删除元素时间复杂度不受元素位置的影响，近似 O（1），如果是要在指定位置i 插⼊和删除元素的话（ (add(int index, E element) ） 时间复杂度近似为 o(n)) 因为需要先移动到指定位置再插⼊。 4.是否⽀持快速随机访问：LinkList不⽀持⾼效的随机元素访问，⽽ ArrayList ⽀持。快速随机访问就是通过元素的序号快速获取元素对象(对应于 get(int index) ⽅法)。 5.内存空间占⽤： ArrayList的空 间浪费主要体现在在list列表的结尾会预留⼀定的容量空间，⽽LinkedList的空间花费则体现在它的每⼀个元素都需要消耗⽐ArrayList更多的空间（因为要存放直接后继和直接前驱以及数据）。

补充内容:RandomAccess接⼝

public interface RandomAccess {
}

ArrayList实现了 RandomAccess 接⼝,而LinkList没有实现 RandomAccess 接⼝

下⾯再总结⼀下 list 的遍历⽅式选择：

实现了 RandomAccess 接⼝的list，优先选择普通 for 循环 ，其次 foreach,

未实现 RandomAccess 接⼝的list，优先选择iterator遍历（foreach遍历底层也是通过iterator实现的,），⼤size的数据，千万不要使⽤普通for循环

补充内容:双向链表和双向循环链表

双向链表： 包含两个指针，⼀个prev指向前⼀个节点，⼀个next指向后⼀个节点。

image-20210504200811875

双向循环链表： 最后⼀个节点的 next 指向head，⽽ head 的prev指向最后⼀个节点，构成⼀个环。

image-20210504200824995

ArrayList 与 Vector 区别呢?为什么要⽤Arraylist取代Vector呢？

Vector 类的所有⽅法都是同步的。可以由两个线程安全地访问⼀个Vector对象、但是⼀个线程访问Vector的话代码要在同步操作上耗费⼤量的时间。 Arraylist 不是同步的，所以在不需要保证线程安全时建议使⽤Arraylist。

说⼀说 ArrayList 的扩容机制吧

·

HashMap和HashTable的区别

1、两者父类不同

HashMap是继承自AbstractMap类，而Hashtable是继承自Dictionary类。不过它们都实现了同时实现了map、Cloneable（可复制）、Serializable（可序列化）这三个接口。

2、对外提供的接口不同

Hashtable比HashMap多提供了elments() 和contains() 两个方法。 elments() 方法继承自Hashtable的父类Dictionnary。elements() 方法用于返回此Hashtable中的value的枚举。

contains()方法判断该Hashtable是否包含传入的value。它的作用与containsValue()一致。事实上，contansValue() 就只是调用了一下contains() 方法。

3、对null的支持不同

Hashtable：key和value都不能为null。

int[] a = new int[4];//推介使用int[] 这种方式初始化

int c[] = {23,43,56,78};//长度：4，索引范围：[0,3]HashMap：key可以为null，但是这样的key只能有一个，因为必须保证key的唯一性；可以有多个key

值对应的value为null。

4、安全性不同

HashMap是线程不安全的，在多线程并发的环境下，可能会产生死锁等问题，因此需要开发人员自己处理多线程的安全问题。如果你要保证线程安全的话就使⽤ConcurrentHashMap 吧！

Hashtable是线程安全的，它的每个方法上都有synchronized 关键字，因此可直接用于多线程中。虽然HashMap是线程不安全的，但是它的效率远远高于Hashtable，这样设计是合理的，因为大部分的使用场景都是单线程。当需要多线程操作的时候可以使用线程安全的ConcurrentHashMap。ConcurrentHashMap虽然也是线程安全的，但是它的效率比Hashtable要高好多倍。因为ConcurrentHashMap使用了分段锁，并不对整个数据进行锁定。

5、初始容量大小和每次扩充容量大小不同

①创建时如果不指定容量初始值，Hashtable 默认的初始⼤⼩为11，之后每次扩充，容量变为原来的2n+1。HashMap 默认的初始化⼤⼩为16。之后每次扩充，容量变为原来的2倍。

②创建时如果给定了容量初始值，那么 Hashtable 会直接使⽤你给定的⼤⼩，⽽ HashMap 会将其扩充为2的幂次⽅⼤⼩（HashMap 中的 tableSizeFor() ⽅法保证，下⾯给出了源代码）。也就是说 HashMap 总是使⽤2的幂作为哈希表的⼤⼩,后⾯会介绍到为什么是2的幂次⽅。

6、计算hash值的方法不同

7、效率

因为线程安全的问题，HashMap 要⽐ HashTable 效率⾼⼀点。另外，HashTable 基本被淘汰，不要在代码中使⽤它；

8、底层数据结构

JDK1.8 以后的 HashMap 在解决哈希冲突时有了较⼤的变化，当链表⻓度⼤于阈值（默认为8）时，将链表转化为红⿊树，以减少搜索时间。Hashtable 没有这样的机制。

HashMap 和 HashSet区别

HashSet 底层就是基于 HashMap 实现的。（HashSet 的源码⾮常⾮常少，因为除了 clone() 、 writeObject() 、 readObject() 是 HashSet ⾃⼰不得不实现之外，其他⽅法都是直接调⽤ HashMap 中的⽅法。

HashMap HashSet
实现了Map接⼝ 实现Set接⼝
存储键值对 仅存储对象
调⽤ put（） 向map中添加元素 调⽤ add（） ⽅法向Set中添加元素
HashMap使⽤键（Key）计算Hashcode HashSet使⽤成员对象来计算hashcode值，对于两个对象来说hashcode可能相同，所以equals()⽅法⽤来判断对象的相等性，

HashSet如何检查重复

当你把对象加⼊ HashSet 时，HashSet会先计算对象的 hashcode 值来判断对象加⼊的位置，同时也会与其他加⼊的对象的hashcode值作⽐较，如果没有相符的hashcode，HashSet会假设对象没有重复出 现。但是如果发现有相同hashcode值的对象，这时会调⽤ equals（） ⽅法来检查hashcode相等的对象是否真的相同。如果两者相同，HashSet就不会让加⼊操作成功。

HashMap的底层实现

JDK1.8之前

JDK1.8 之前HashMap 底层是 数组和链表 结合在⼀起使⽤也就是 链表散列。HashMap 通过 key 的hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这⾥的 n 指的是数组的⻓度），如果当前位置存在元素的话，就判断该元素与要存⼊的元素的 hash值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。

所谓扰动函数指的就是 HashMap 的 hash ⽅法。使⽤ hash ⽅法也就是扰动函数是为了防⽌⼀些实现⽐较差的 hashCode() ⽅法 换句话说使⽤扰动函数之后可以减少碰撞。

JDK 1.8 HashMap 的 hash ⽅法源码:

JDK 1.8 的 hash⽅法 相⽐于 JDK 1.7 hash ⽅法更加简化，但是原理不变。

static final int hash(Object key) { 
    int h;
// key.hashCode()：返回散列值也就是hashcode
// ^ ：按位异或
// j>ké⽆符号右移，忽略符号位，空位都以0补⻬
return (key WX null) ? 0 : (h = key.hashCode()) ^ (h j>k 16);
}

对⽐⼀下 JDK1.7的 HashMap 的 hash ⽅法源码.

static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions  (approximately  8  at  default  load  factor).

h ^= (h j>k 20) ^ (h  j>k  12); return h ^ (h j>k 7) ^ (h j>k 4);
}

相⽐于 JDK1.8 的 hash ⽅法 ，JDK 1.7 的 hash ⽅法的性能会稍差⼀点点，因为毕竟扰动了 4 次。

所谓 “拉链法” 就是：将链表和数组相结合。也就是说创建⼀个链表数组，数组中每⼀格就是⼀个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

image-20210504201844532

JDK1.8之后

相⽐于之前的版本， JDK1.8之后在解决哈希冲突时有了较⼤的变化，当链表⻓度⼤于阈值（默认为8） 时，将链表转化为红⿊树，以减少搜索时间。

TreeMap、TreeSet以及JDK1.8之后的HashMap底层都⽤到了红⿊树。红⿊树就是为了解决⼆叉查找树 的缺陷，因为⼆叉查找树在某些情况下会退化成⼀个线性结构。

image-20210504201920644

HashMap 的⻓度为什么是2的幂次⽅

为了能让 HashMap 存取⾼效，尽量较少碰撞，也就是要尽量把数据分配均匀。我们上⾯也讲到了过了，Hash 值的范围值-2147483648到2147483647，前后加起来⼤概40亿的映射空间，只要哈希函数映射得⽐较均匀松散，⼀般应⽤是很难出现碰撞的。但问题是⼀个40亿⻓度的数组，内存是放不下的。所以 这个散列值是不能直接拿来⽤的。⽤之前还要先做对数组的⻓度取模运算，得到的余数才能⽤来要存放 的位置也就是对应的数组下标。这个数组下标的计算⽅法是" (n - 1) & hash "。（n代表数组⻓度)。这也就解释了 HashMap 的⻓度为什么是2的幂次⽅。

这个算法应该如何设计呢？

我们⾸先可能会想到采⽤%取余的操作来实现。但是，重点来了：“取余(%)操作中如果除数是2的幂次则 等价于与其除数减⼀的与(&)操作（也就是说 hash%lengthdehash&(length-1)的前提是 length 是2的n 次⽅；）。” 并且 采⽤⼆进制位操作 &，相对于%能够提⾼运算效率，这就解释了 HashMap 的⻓度为什么是2的幂次⽅

HashMap 多线程操作导致死循环问题

主要原因在于 并发下的Rehash 会造成元素之间会形成⼀个循环链表。不过，jdk 1.8 后解决了这个问题，但是还是不建议在多线程下使⽤ HashMap,因为多线程下使⽤ HashMap 还是会存在其他问题⽐如数据丢失。并发环境下推荐使⽤ ConcurrentHashMap 。

ConcurrentHashMap 和 Hashtable 的区别

ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的⽅式上不同。

  • 底层数据结构： JDK1.7的 ConcurrentHashMap 底层采⽤ 分段的数组+链表 实现，JDK1.8 采⽤的数据结构跟HashMap1.8的结构⼀样，数组+链表/红⿊⼆叉树。Hashtable 和 JDK1.8 之前的HashMap 的底层数据结构类似都是采⽤ 数组+链表 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突⽽存在的；
  • 使⽤ synchronized 来保证线程安全，效率⾮常低下。当⼀个线程访问同步⽅法时，其他线程也访问同步⽅法，可能会进⼊阻塞或轮询状态，如 使⽤ put 添加元素，另⼀个线程不能使⽤ put 添加元素，也不能使⽤ get，竞争会越来越激烈效率越低。
两者的对⽐图：

image-20210504202112905

JDK1.7的ConcurrentHashMap：

image-20210504202124863

JDK1.8的ConcurrentHashMap（TreeBin: 红⿊⼆叉树节点 Node: 链表节点）：

image-20210504202150994

ConcurrentHashMap线程安全的具体实现⽅式/底层具体实现

JDK1.7

image-20210504202124863

⾸先将数据分为⼀段⼀段的存储，然后给每⼀段数据配⼀把锁，当⼀个线程占⽤锁访问其中⼀个段数据 时，其他段的数据也能被其他线程访问。

ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成。

Segment 实现了 ReentrantLock,所以 Segment 是⼀种可重⼊锁，扮演锁的⻆⾊。HashEntry ⽤于存储键值对数据。

static  class  Segment<K,V>  extends  ReentrantLock  implements  Serializable
{
}

⼀个 ConcurrentHashMap ⾥包含⼀个 Segment 数组。Segment 的结构和HashMap类似，是⼀种数组和链表结构，⼀个 Segment 包含⼀个 HashEntry 数组，每个 HashEntry 是⼀个链表结构的元素，每个Segment 守护着⼀个HashEntry数组⾥的元素，当对 HashEntry 数组的数据进⾏修改时，必须⾸先获得对应的 Segment的锁。

JDK1.8

image-20210504202150994

ConcurrentHashMap取消了Segment分段锁，采⽤CAS和synchronized来保证并发安全。数据结构跟HashMap1.8的结构类似，数组+链表/红⿊⼆叉树。Java 8在链表⻓度超过⼀定阈值（8）时将链表（寻址时间复杂度为O(N)）转换为红⿊树（寻址时间复杂度为O(log(N))）

synchronized只锁定当前链表或红⿊⼆叉树的⾸节点，这样只要hash不冲突，就不会产⽣并发，效率⼜提升N倍。

comparable 和 Comparator的区别

comparable接⼝实际上是出⾃java.lang包 它有⼀个 compareTo(Object obj) ⽅法⽤来排

序 comparator接⼝实际上是出⾃ java.util 包它有⼀个 compare(Object obj1, Object obj2) ⽅法⽤来排序⼀般我们需要对⼀个集合使⽤⾃定义排序时，我们就要重写 compareTo() ⽅法或 compare() ⽅法， 当我们需要对某⼀个集合实现两种排序⽅式，⽐如⼀个song对象中的歌名和歌⼿名分别采⽤⼀种排序⽅ 法的话，我们可以重写 compareTo() ⽅法和使⽤⾃制的Comparator⽅法或者以两个Comparator来实现歌名排序和歌星名排序，第⼆种代表我们只能使⽤两个参数版的 Collections.sort() .

Comparator定制排序

ArrayList<Integer> arrayList = new ArrayList<Integer>(); 
arrayList.add(-1);
arrayList.add(3); 
arrayList.add(3); 
arrayList.add(-5); 
arrayList.add(7); 
arrayList.add(4); 
arrayList.add(-9); 
arrayList.add(-7);
System.out.println("原始数组:");
System.out.println(arrayList);
// void reverse(List list)：反转
Collections.reverse(arrayList); System.out.println("Collections.reverse(arrayList):"); System.out.println(arrayList);
// void sort(List list),按⾃然排序的升序排序Collections.sort(arrayList); System.out.println("Collections.sort(arrayList):");
System.out.println(arrayList);
// 定制排序的⽤法
Collections.sort(arrayList, new Comparator<Integer>() {

@Override
public  int  compare(Integer  o1,  Integer  o2)  { 
    return  o2.compareTo(o1);
}
});
System.out.println("定制排序后：");
System.out.println(arrayList);

Output:

原始数组:
[-1, 3, 3, -5, 7, 4, -9, -7]
Collections.reverse(arrayList): [-7, -9, 4, 7, -5, 3, 3, -1]
Collections.sort(arrayList): [-9, -7, -5, -1, 3, 3, 4, 7]
定制排序后：
[7, 4, 3, 3, -1, -5, -7, -9]

重写compareTo⽅法实现按年龄来排序

// person对象没有实现Comparable接⼝，所以必须实现，这样才不会出错，才可以使treemap中的数据按顺序排列
// 前⾯⼀个例⼦的String类已经默认实现了Comparable接⼝，详细可以查看
String类的API⽂档，另外其他
// 像Integer类等都已经实现了Comparable接⼝，所以不需要另外实现了

public    class Person implements Comparable<Person> { private  String  name;
private int age;

public  Person(String  name,  int  age)  { super();
this.name  =  name; this.age = age;
}

public String getName() { return  name;
}

public void setName(String name) { this.name  =  name;
}

public int getAge() { return age;
}

public void setAge(int age) { this.age = age;
}

    /
     TODO重写compareTo⽅法实现按年龄来排序
    / @Override
    public int compareTo(Person o) {
    // TODO Auto-generated method stub if  (this.age  >  o.getAge())  {
    return 1;
    }  else  if  (this.age  <  o.getAge())  { return -1;
    }
    return age;
    }
    }

    public static void main(String[] args) {
    TreeMap<Person,  String>  pdata  =  new  TreeMap<Person,  String>(); 
    pdata.put(new  Person("张三",  30),  "zhangsan");
    pdata.put(new  Person("李四",  20),  "lisi");
    pdata.put(new  Person("王五",  10),  "wangwu"); 
    pdata.put(new  Person("⼩红",  5),  "xiaohong");
    // 得到key的值的同时得到key所对应的值
    Set<Person> keys = pdata.keySet(); for (Person key : keys) {
    System.out.println(key.getAge()  +  "-"  +  key.getName());

    }
}

Output：

5-⼩红
10-王五
20-李四
30-张三

集合框架底层数据结构总结

Collection

  1. List
  • Arraylist： Object数组
  • Vector： Object数组
  • LinkedList： 双向链表(JDK1.6之前为循环链表，JDK1.7取消了循环)
  1. Set

  2. HashSet（⽆序，唯⼀）: 基于 HashMap 实现的，底层采⽤ HashMap 来保存元素LinkedHashSet：

  3. LinkedHashSet 继承于 HashSet，并且其内部是通过 LinkedHashMap 来实现的。有点类似于我们之前说的LinkedHashMap 其内部是基于 HashMap 实现⼀样，不过还是有⼀点点区别的

  4. TreeSet（有序，唯⼀）： 红⿊树(⾃平衡的排序⼆叉树)

  1. Map

  2. HashMap： JDK1.8之前HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突⽽存在的（"拉链法"解决冲突）。JDK1.8以后在解决哈希冲突时有了较⼤的变化， 当链表⻓度⼤于阈值（默认为8)时，将链表转化为红⿊树，以减少搜索时间

  • LinkedHashMap： LinkedHashMap 继承⾃ HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红⿊树组成。另外，LinkedHashMap 在上⾯结构的基础上，增加了⼀条双向链表，使得上⾯的结构可以保持键值对的插⼊顺序。同时通过对链表进⾏相应的操作，实现了访问 顺序相关逻辑。详细可以查看：《LinkedHashMap 源码详细分析（JDK1.8）》
  • Hashtable： 数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突⽽存在的
  • TreeMap： 红⿊树（⾃平衡的排序⼆叉树)

如何选⽤集合?

主要根据集合的特点来选⽤，⽐如我们需要根据键值获取到元素值时就选⽤Map接⼝下的集合，需要排 序时选择TreeMap,不需要排序时就选择HashMap,需要保证线程安全就选⽤ConcurrentHashMap.当我们只 需要存放元素值时，就选择实现Collection接⼝的集合，需要保证元素唯⼀时选择实现Set接⼝的集合

⽐如TreeSet或HashSet，不需要就选择实现List接⼝的⽐如ArrayList或LinkedList，然后再根据实现这些接⼝的集合的特点来选⽤。

results matching ""

    No results matching ""