集合详解

2020-08-17  本文已影响0人  浅乔未果

本文章根据多篇文章整理和自己修改而成，很多已经无法找到出处，如果出现相同的信息，请见谅！

一、概览

容器主要包括 Collection 和 Map 两种，Collection 存储着对象的集合，而 Map 存储着键值对（两个对象）的映射表。

Collection

Snipaste_2020-08-01_10-21-54.png Snipaste_2020-08-01_10-23-04.png

1. Set

1.哈希表的做法其实很简单，就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个int类型，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里，而当使用哈希表进行查询的时候，就是再次使用哈希函数将key转换为对应的数组下标，并定位到该空间获取value，如此一来，就可以充分利用到数组的定位性能进行数据定位。(但是hashCode值相同并不一定就是同一个值)
     2.在存储的适合发现hashCode值相同，再比较equals方法。
     3.equals相同，对象相同。（则无需储存）

适用场景分析:

HashSet是基于Hash算法实现的，其性能通常都优于TreeSet。为快速查找而设计的Set，我们通常都应该使用HashSet，在我们需要排序的功能时，我们才使用TreeSet。

2. List

3. Queue(JUC并发会有讲解)

Snipaste_2020-08-01_10-57-51.png

怎么选择：

Snipaste_2020-08-01_12-38-05.png

Map接口:

1. HashMap

Map 主要用于存储键(key)值(value)对，根据键得到值，因此键不允许重复,但允许值重复。 HashMap 是一个最常用的Map,它根据键的HashCode 值存储数据,根据键可以直接获取它的值，具有很快的访问速度。 HashMap最多只允许一条记录的键为Null;允许多条记录的值为 Null; HashMap不支持线程的同步，即任一时刻可以有多个线程同时写HashMap;可能会导致数据的不一致。如果需要同步，可以用 Collections的synchronizedMap方法使HashMap具有同步的能力，或者使用ConcurrentHashMap。 HashMap基于哈希表结构实现的 ，当一个对象被当作键时，必须重写hasCode和equals方法。

2. LinkedHashMap

LinkedHashMap继承自HashMap，它主要是用链表实现来扩展HashMap类，HashMap中条目是没有顺序的，但是在LinkedHashMap中元素既可以按照它们插入图的顺序排序，也可以按它们最后一次被访问的顺序排序。

3. TreeMap

TreeMap基于红黑树数据结构的实现，键值可以使用Comparable或Comparator接口来排序。TreeMap继承自AbstractMap，同时实现了接口NavigableMap，而接口NavigableMap则继承自SortedMap。SortedMap是Map的子接口，使用它可以确保图中的条目是排好序的。

在实际使用中，如果更新图时不需要保持图中元素的顺序，就使用HashMap，如果需要保持图中元素的插入顺序或者访问顺序，就使用LinkedHashMap，如果需要使图按照键值排序，就使用TreeMap。

4. Hashtable

Hashtable和前面介绍的HashMap很类似，它也是一个散列表，存储的内容是键值对映射，不同之处在于，Hashtable是继承自Dictionary的，Hashtable中的函数都是同步的，这意味着它也是线程安全的，另外，Hashtable中key和value都不可以为null。

遍历map实例

public class T {
  public static void main(String[] args) {
  Map<String, String> map = new HashMap<String, String>();
  map.put("first", "linlin");
  map.put("second", "好好学java");
  map.put("third", "sihai");
  map.put("first", "sihai2");
 ​
 ​
  // 第一种：通过Map.keySet遍历key和value
  for (String key : map.keySet()) {
  System.out.println(key + ":" + map.get(key));
  }
 ​
  System.out.println("==============================================");
 ​
  // 第二种：通过Map.entrySet使用iterator遍历key和value
  Iterator<Map.Entry<String, String>> iterator = map.entrySet().iterator();
  while (iterator.hasNext()){
  Map.Entry<String, String> entry = iterator.next();
  System.out.println(entry.getKey() + ":" + entry.getValue());
  }
 ​
  System.out.println("==============================================");
 ​
  // 第三种：通过Map.entrySet遍历key和value
  for ( Map.Entry<String, String> entry: map.entrySet()) {
  System.out.println(entry.getKey() + ":" + entry.getValue());
  }
 ​
  System.out.println("==============================================");
 ​
  // 第四种：通过Map.values()遍历所有的value，但是不能遍历键key
  for (String value: map.values()) {
  System.out.println(value);
  }
 ​
  System.out.println("==============================================");
 ​
  // 第五种，使用Lambda需要jdk1.8以后(推荐)
  map.forEach((m,k)-> System.out.println(m + ":" + k));
  }
 }

总结图解：

Snipaste_2020-08-01_10-25-36.png

二、源码分析

ArrayList

1. 概览

因为 ArrayList 是基于数组实现的，所以支持快速随机访问。RandomAccess 接口标识着该类支持快速随机访问。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

数组的默认大小为 10。

 private static final int DEFAULT_CAPACITY = 10;
Snipaste_2020-08-01_15-55-21.png

2. 扩容

添加元素时使用 ensureCapacityInternal() 方法来保证容量足够，如果不够时，需要使用 grow() 方法进行扩容，新容量的大小为 oldCapacity + (oldCapacity >> 1)，也就是旧容量的 1.5 倍。

扩容操作需要调用 Arrays.copyOf() 把原数组整个复制到新数组中，这个操作代价很高，因此最好在创建 ArrayList 对象时就指定大概的容量大小，减少扩容操作的次数。

public boolean add(E e) {
  ensureCapacityInternal(size + 1);  // Increments modCount!!
  elementData[size++] = e;
  return true;
 }
 ​
 private void ensureCapacityInternal(int minCapacity) {
  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
  minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
  }
  ensureExplicitCapacity(minCapacity);
 }
 ​
 private void ensureExplicitCapacity(int minCapacity) {
  modCount++;
  // overflow-conscious code
  if (minCapacity - elementData.length > 0)
  grow(minCapacity);
 }
 ​
 private void grow(int minCapacity) {
  // overflow-conscious code
  int oldCapacity = elementData.length;
  int newCapacity = oldCapacity + (oldCapacity >> 1);
  if (newCapacity - minCapacity < 0)
  newCapacity = minCapacity;
  if (newCapacity - MAX_ARRAY_SIZE > 0)
  newCapacity = hugeCapacity(minCapacity);
  // minCapacity is usually close to size, so this is a win:
  elementData = Arrays.copyOf(elementData, newCapacity);
 }

3. 序列化

ArrayList 基于数组实现，并且具有动态扩容特性，因此保存元素的数组不一定都会被使用，那么就没必要全部进行序列化。

保存元素的数组 elementData 使用 transient 修饰，该关键字声明数组默认不会被序列化。

 transient Object[] elementData; // non-private to simplify nested class access

ArrayList 实现了 writeObject() 和 readObject() 来控制只序列化数组中有元素填充那部分内容。

 private void readObject(java.io.ObjectInputStream s)
  throws java.io.IOException, ClassNotFoundException {
  elementData = EMPTY_ELEMENTDATA;
 ​
  // Read in size, and any hidden stuff
  s.defaultReadObject();
 ​
  // Read in capacity
  s.readInt(); // ignored
 ​
  if (size > 0) {
  // be like clone(), allocate array based upon size not capacity
  ensureCapacityInternal(size);
 ​
  Object[] a = elementData;
  // Read in all elements in the proper order.
  for (int i=0; i<size; i++) {
  a[i] = s.readObject();
  }
  }
 }

private void writeObject(java.io.ObjectOutputStream s)
  throws java.io.IOException{
  // Write out element count, and any hidden stuff
  int expectedModCount = modCount;
  s.defaultWriteObject();
 ​
  // Write out size as capacity for behavioural compatibility with clone()
  s.writeInt(size);
 ​
  // Write out all elements in the proper order.
  for (int i=0; i<size; i++) {
  s.writeObject(elementData[i]);
  }
 ​
  if (modCount != expectedModCount) {
  throw new ConcurrentModificationException();
  }
 }

序列化时需要使用 ObjectOutputStream 的 writeObject() 将对象转换为字节流并输出。而 writeObject() 方法在传入的对象存在 writeObject() 的时候会去反射调用该对象的 writeObject() 来实现序列化。反序列化使用的是 ObjectInputStream 的 readObject() 方法，原理类似。

 ArrayList list = new ArrayList();
 ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream(file));
 oos.writeObject(list);

4. Fail-Fast

modCount 用来记录 ArrayList 结构发生变化的次数。结构发生变化是指添加或者删除至少一个元素的所有操作，或者是调整内部数组的大小，仅仅只是设置元素的值不算结构发生变化。

在进行序列化或者迭代等操作时，需要比较操作前后 modCount 是否改变，如果改变了需要抛出 ConcurrentModificationException。(在并发的情况下就可能会发生)

Snipaste_2020-06-28_14-36-48.png

Vector

1. 同步

它的实现与 ArrayList 类似，但是使用了 synchronized 进行同步。

public synchronized boolean add(E e) {
  modCount++;
  ensureCapacityHelper(elementCount + 1);
  elementData[elementCount++] = e;
  return true;
 }

2. 扩容

Vector 的构造函数可以传入 capacityIncrement 参数，它的作用是在扩容时使容量 capacity 增长 capacityIncrement。如果这个参数的值小于等于 0，扩容时每次都令 capacity 为原来的两倍。

public Vector(int initialCapacity, int capacityIncrement) {
  super();
  if (initialCapacity < 0)
  throw new IllegalArgumentException("Illegal Capacity: "+
  initialCapacity);
  this.elementData = new Object[initialCapacity];
  this.capacityIncrement = capacityIncrement;
 }

private void grow(int minCapacity) {
  // overflow-conscious code
  int oldCapacity = elementData.length;
  int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
  capacityIncrement : oldCapacity);
  if (newCapacity - minCapacity < 0)
  newCapacity = minCapacity;
  if (newCapacity - MAX_ARRAY_SIZE > 0)
  newCapacity = hugeCapacity(minCapacity);
  elementData = Arrays.copyOf(elementData, newCapacity);
 }

调用没有 capacityIncrement 的构造函数时，capacityIncrement 值被设置为 0，也就是说默认情况下 Vector 每次扩容时容量都会翻倍。

public Vector(int initialCapacity) {
  this(initialCapacity, 0);
 }
 ​
 public Vector() {
  this(10);
 }

3. 与 ArrayList 的比较

4. 替代方案

可以使用 Collections.synchronizedList(); 得到一个线程安全的 ArrayList。

 List<String> list = new ArrayList<>();
 List<String> synList = Collections.synchronizedList(list);

也可以使用 concurrent 并发包下的 CopyOnWriteArrayList 类。

 List<String> list = new CopyOnWriteArrayList<>();</pre>

三、重点问题重点分析:

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

二）Arraylist 与 LinkedList 区别?

三）ArrayList 与 Vector 区别呢?为什么要用Arraylist取代Vector呢？

Vector类的所有方法都是同步的。可以由两个线程安全地访问一个Vector对象、但是一个线程访问Vector的话代码要在同步操作上耗费大量的时间。

Arraylist不是同步的，所以在不需要保证线程安全时建议使用Arraylist。

四）HashSet与TreeSet与LinkedHashSet对比

五）LinkedHashMap和HashMap，TreeMap对比

六）HashMap 和 Hashtable 的区别

七）HashMap 和 HashSet区别

如果你看过 HashSet 源码的话就应该知道：HashSet 底层就是基于 HashMap 实现的。（HashSet 的源码非常非常少，因为除了 clone()、writeObject()、readObject()是 HashSet 自己不得不实现之外，其他方法都是直接调用 HashMap 中的方法。

八）HashSet如何检查重复

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

hashCode（）与equals（）的相关规定：

  1. 如果两个对象相等，则hashcode一定也是相同的

  2. 两个对象相等,对两个equals方法返回true

  3. 两个对象有相同的hashcode值，它们也不一定是相等的

  4. 综上，equals方法被覆盖过，则hashCode方法也必须被覆盖

  5. hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写hashCode()，则该class的两个对象无论如何都不会相等（即使这两个对象指向相同的数据）。

九）HashMap的底层实现

JDK1.8之前

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

所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法 换句话说使用扰动函数之后可以减少碰撞。

HashMap实现原理（比较好的描述）：HashMap以键值对（key-value）的形式来储存元素，但调用put方法时，HashMap会通过hash函数来计算key的hash值，然后通过hash值&(HashMap.length-1)判断当前元素的存储位置，如果当前位置存在元素的话，就要判断当前元素与要存入的key是否相同，如果相同则覆盖，如果不同则通过拉链表来解决。JDk1.8时，当链表长度大于8时，将链表转为红黑树。

JDK 1.8 HashMap 的 hash 方法源码:

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

 static final int hash(Object key) {
  int h;
  // key.hashCode()：返回散列值也就是hashcode
  // ^ ：按位异或
  // >>>:无符号右移，忽略符号位，空位都以0补齐
  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 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 >>> 20) ^ (h >>> 12);
  return h ^ (h >>> 7) ^ (h >>> 4);
  }

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

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

Snipaste_2020-08-01_15-15-16.png

JDK1.8之后

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

Snipaste_2020-08-01_15-16-51.png

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

十）HashMap 的长度为什么是2的幂次方

HashMap为了存取高效，要尽量较少碰撞，就是要尽量把数据分配均匀，每个链表长度大致相同，这个实现就在把数据存到哪个链表中的算法；

这个算法实际就是取模，hash%length，计算机中直接求余效率不如位移运算，源码中做了优化hash&(length-1)， hash%length==hash&(length-1)的前提是length是2的n次方；

为什么这样能均匀分布减少碰撞呢？2的n次方实际就是1后面n个0，2的n次方-1 实际就是n个1； 例如长度为9时候，3&(9-1)=0 2&(9-1)=0 ，都在0上，碰撞了； 例如长度为8时候，3&(8-1)=3 2&(8-1)=2 ，不同位置上，不碰撞；

其实就是按位“与”的时候，每一位都能 &1 ，也就是和1111……1111111进行与运算

0000 0011 3

& 0000 1000 8

= 0000 0000 0

0000 0010 2

& 0000 1000 8

= 0000 0000 0

0000 0011 3

& 0000 0111 7

= 0000 0011 3

0000 0010 2

& 0000 0111 7

= 0000 0010 2

当然如果不考虑效率直接求余即可（就不需要要求长度必须是2的n次方了）；

有人怀疑两种运算效率差别到底有多少，我做个测试：

/**
  * 
  * 直接【求余】和【按位】运算的差别验证
  */
 public static void main(String[] args) {

  long currentTimeMillis = System.currentTimeMillis();
  int a=0;
  int times = 10000*10000;
  for (long i = 0; i < times; i++) {
  a=9999%1024;
  }
  long currentTimeMillis2 = System.currentTimeMillis();

  int b=0;
  for (long i = 0; i < times; i++) {
  b=9999&(1024-1);
  }

  long currentTimeMillis3 = System.currentTimeMillis();
  System.out.println(a+","+b);
  System.out.println("%: "+(currentTimeMillis2-currentTimeMillis));
  System.out.println("&: "+(currentTimeMillis3-currentTimeMillis2));
 }
 ​
 结果：
 783,783
 %: 359
 &: 93

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

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

Rehash：一般来说，Hash表这个容器当有数据要插入时，都会检查容量有没有超过设定的临界值，如果超过，需要增大Hash表的尺寸，但是这样一来，整个Hash表里的元素都需要被重算一遍。这叫rehash，这个成本相当的大。

十三）comparable 和 Comparator的区别

一般我们需要对一个集合使用自定义排序时，我们就要重写compareTo()方法或compare()方法，当我们需要对某一个集合实现两种排序方式，比如一个song对象中的歌名和歌手名分别采用一种排序方法的话，我们可以重写compareTo()方法和使用自制的Comparator方法或者以两个Comparator来实现歌名排序和歌星名排序，第二种代表我们只能使用两个参数版的 Collections.sort().

四、并发下的集合不安全

1 List集合下的并发安全

 public static void main(String[] args) {
  List<String> list = new ArrayList();
  for (int i = 0; i < 10; i++) {
  new Thread(()->{
  list.add(UUID.randomUUID().toString().substring(0,7));
  System.out.println(list);
  },String.valueOf(i)).start();
  }
  }

发现可能出现的异常情况

Snipaste_2020-06-28_14-36-48.png

解决方案：

1. new Vector<>();

 public static void main(String[] args) {
 ​
  List<String> list = new Vector<>();
 ​
  for (int i = 0; i < 10; i++) {
  new Thread(()->{
  list.add(UUID.randomUUID().toString().substring(0,7));
  System.out.println(list);
  },String.valueOf(i)).start();
  }
  }

2. 使用Collections.snychronizedList

 public static void main(String[] args) {
  List<String> list = Collections.synchronizedList(new ArrayList<>());
  for (int i = 0; i < 10; i++) {
  new Thread(()->{
  list.add(UUID.randomUUID().toString().substring(0,7));
  System.out.println(list);
  },String.valueOf(i)).start();
  }
  }

3. 使用JUC编程下的CopyOnWriteArrayList<>();

读写分离
 public boolean add(E e) {
  final ReentrantLock lock = this.lock;
  lock.lock();
  try {
  Object[] elements = getArray();
  int len = elements.length;
  Object[] newElements = Arrays.copyOf(elements, len + 1);
  newElements[len] = e;
  setArray(newElements);
  return true;
  } finally {
  lock.unlock();
  }
 }
 ​
 final void setArray(Object[] a) {
  array = a;
 }

 @SuppressWarnings("unchecked")
 private E get(Object[] a, int index) {
  return (E) a[index];
 }
适用场景

CopyOnWriteArrayList 在写操作的同时允许读操作，大大提高了读操作的性能，因此很适合读多写少的应用场景。

但是 CopyOnWriteArrayList 有其缺陷：

所以 CopyOnWriteArrayList 不适合内存敏感以及对实时性要求很高的场景。

2. set集合

同上：

Set<String> list = Collections.synchronizedSet(new HashSet<>());

Set<String> list = new CopyOnWriteArraySet<>();

3. Map集合

解决方案：ConcurrentHashMap

 // ConcurrentModificationException
 public class MapTest {
 public static void main(String[] args) {
 // map 是这样用的吗？ 不是，工作中不用 HashMap
 // 默认等价于什么？ new HashMap<>(16,0.75);
 // Map<String, String> map = new HashMap<>();
 Map<String, String> map = new ConcurrentHashMap<>();
 for (int i = 1; i <=30; i++) {
 new Thread(()->{
 map.put(Thread.currentThread().getName(),UUID.randomUUID().toString().substring(
 0,5));
 System.out.println(map);
 },String.valueOf(i)).start();
 }
 }
 }

哈希表

1.介绍

哈希表就是一种以 键-值(key-indexed) 存储数据的结构，我们只要输入待查找的值即key，即可查找到其对应的值。

哈希的思路很简单，如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。这是对于简单的键的情况，我们将其扩展到可以处理更加复杂的类型的键。

2.链式哈希表

链式哈希表从根本上说是由一组链表构成。每个链表都可以看做是一个“桶”，我们将所有的元素通过散列的方式放到具体的不同的桶中。插入元素时，首先将其键传入一个哈希函数（该过程称为哈希键），函数通过散列的方式告知元素属于哪个“桶”，然后在相应的链表头插入元素。查找或删除元素时，用同们的方式先找到元素的“桶”，然后遍历相应的链表，直到发现我们想要的元素。因为每个“桶”都是一个链表，所以链式哈希表并不限制包含元素的个数。然而，如果表变得太大，它的性能将会降低。

Snipaste_2020-08-01_16-22-38.png

应用场景

我们熟知的缓存技术（比如redis、memcached）的核心其实就是在内存中维护一张巨大的哈希表，还有大家熟知的HashMap、ConcurrentHashMap等的应用。

ConcurrentHashMap与HashMap等的区别

1. HashMap

我们知道HashMap是线程不安全的，在多线程环境下，使用Hashmap进行put操作会引起死循环，导致CPU利用率接近100%，所以在并发情况下不能使用HashMap。

2. HashTable

HashTable和HashMap的实现原理几乎一样，差别无非是

但是HashTable线程安全的策略实现代价却太大了，简单粗暴，get/put所有相关操作都是synchronized的，这相当于给整个哈希表加了一把大锁，如下图所示：

Snipaste_2020-08-01_16-25-07.png

多线程访问时候，只要有一个线程访问或操作该对象，那其他线程只能阻塞，相当于将所有的操作串行化，在竞争激烈的并发场景中性能就会非常差。

3. ConcurrentHashMap

主要就是为了应对hashmap在并发环境下不安全而诞生的，ConcurrentHashMap的设计与实现非常精巧，大量的利用了volatile，final，CAS等lock-free技术来减少锁竞争对于性能的影响。

我们都知道Map一般都是数组+链表结构（JDK1.8该为数组+红黑树）。

Snipaste_2020-08-01_16-26-33.png

ConcurrentHashMap避免了对全局加锁改成了局部加锁操作，这样就极大地提高了并发环境下的操作速度，由于ConcurrentHashMap在JDK1.7和1.8中的实现非常不同，接下来我们谈谈JDK在1.7和1.8中的区别。

JDK1.7版本的ConcurrentHashMap的实现原理

在JDK1.7中ConcurrentHashMap采用了数组+Segment+分段锁的方式实现。

Segment(分段锁)

ConcurrentHashMap中的分段锁称为Segment，它即类似于HashMap的结构，即内部拥有一个Entry数组，数组中的每个元素又是一个链表,同时又是一个ReentrantLock（Segment继承了ReentrantLock）。

内部结构

ConcurrentHashMap使用分段锁技术，将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问，能够实现真正的并发访问。如下图是ConcurrentHashMap的内部结构图：


Snipaste_2020-08-01_16-28-07.png

ConcurrentHashMap定位一个元素的过程需要进行两次Hash操作。

第一次Hash定位到Segment，第二次Hash定位到元素所在的链表的头部。

该结构的优劣势：

坏处

这一种结构的带来的副作用是Hash的过程要比普通的HashMap要长

好处

写操作的时候可以只对元素所在的Segment进行加锁即可，不会影响到其他的Segment，这样，在最理想的情况下，ConcurrentHashMap可以最高同时支持Segment数量大小的写操作（刚好这些写操作都非常平均地分布在所有的Segment上）。

所以，通过这一种结构，ConcurrentHashMap的并发能力可以大大的提高。

JDK1.8版本的ConcurrentHashMap的实现原理

JDK8中ConcurrentHashMap参考了JDK8 HashMap的实现，采用了数组+链表+红黑树的实现方式来设计，如下图所示：

Snipaste_2020-08-01_16-31-34.png

内部大量采用CAS操作，这里我简要介绍下CAS。

CAS是compare and swap的缩写，即我们所说的比较交换。cas是一种基于锁的操作，而且是乐观锁。在java中锁分为乐观锁和悲观锁。悲观锁是将资源锁住，等一个之前获得锁的线程释放锁之后，下一个线程才可以访问。而乐观锁采取了一种宽泛的态度，通过某种方式不加锁来处理资源，比如通过给记录加version来获取数据，性能较悲观锁有很大的提高。

CAS 操作包含三个操作数 —— 内存位置（V）、预期原值（A）和新值(B)。如果内存地址里面的值和A的值是一样的，那么就将内存里面的值更新成B。CAS是通过无限循环来获取数据的，如果在第一轮循环中，a线程获取地址里面的值被b线程修改了，那么a线程需要自旋，到下次循环才有可能机会执行。

JDK8中彻底放弃了Segment转而采用的是Node，其设计思想也不再是JDK1.7中的分段锁思想。

Node：保存key，value及key的hash值的数据结构。其中value和next都用volatile修饰，保证并发的可见性。

 <strong>class Node<K,V> implements Map.Entry<K,V> {
  final int hash;
  final K key;
  volatile V val;
  volatile Node<K,V> next;
  //... 省略部分代码
 } </strong>

Java8 ConcurrentHashMap结构基本上和Java8的HashMap一样，不过保证线程安全性。

在JDK8中ConcurrentHashMap的结构，由于引入了红黑树，使得ConcurrentHashMap的实现非常复杂，我们都知道，红黑树是一种性能非常好的二叉查找树，其查找性能为O（logN），但是其实现过程也非常复杂，而且可读性也非常差，DougLea的思维能力确实不是一般人能比的，早期完全采用链表结构时Map的查找时间复杂度为O（N），JDK8中ConcurrentHashMap在链表的长度大于某个阈值的时候会将链表转换成红黑树进一步提高其查找性能。

Snipaste_2020-08-01_16-34-20.png

ConcurrentHashMap总结

其实可以看出JDK1.8版本的ConcurrentHashMap的数据结构已经接近HashMap，相对而言，ConcurrentHashMap只是增加了同步的操作来控制并发，从JDK1.7版本的ReentrantLock+Segment+HashEntry，到JDK1.8版本中synchronized+CAS+HashEntry+红黑树。

1. 数据结构：取消了Segment分段锁的数据结构，取而代之的是数组+链表+红黑树的结构。

2. 保证线程安全机制：JDK1.7采用segment的分段锁机制实现线程安全，其中segment继承自ReentrantLock。JDK1.8采用CAS+Synchronized保证线程安全。

3. 锁的粒度：原来是对需要进行数据操作的Segment加锁，现调整为对每个数组元素加锁（Node）。

4. 链表转化为红黑树:定位结点的hash算法简化会带来弊端,Hash冲突加剧,因此在链表节点数量大于8时，会将链表转化为红黑树进行存储。

5. 查询时间复杂度：从原来的遍历链表O(n)，变成遍历红黑树O(logN)。

五、其他相关

二叉查找树

要想了解二叉查找树，我们首先看下二叉查找树有哪些特性呢？

1， 左子树上所有的节点的值均小于或等于他的根节点的值

2， 右子数上所有的节点的值均大于或等于他的根节点的值

3， 左右子树也一定分别为二叉排序树

我们来看下图的这棵树，他就是典型的二叉查找树

Snipaste_2020-08-01_11-14-48.png

这不是二分查找的思想吗？确实，查找所需的最大次数等同于二叉查找树的高度。当然在插入节点的时候，也是这种思想，一层一层的找到合适的位置插入。但是二叉查找树有个比较大的缺陷，而且这个缺陷会影响到他的性能。我们先来看下有一种情况的插入操作：

如果初始的二叉查找树只有三个节点，如下图：

Snipaste_2020-08-01_11-20-23.png

我们依次插入5个节点：7，6,5,4,3,。看下图插入之后的图：

Snipaste_2020-08-01_11-20-58.png

看出来了吗？有没有觉得很别扭，如果根节点足够大，那是不是“左腿”会变的特别长，也就是说查找的性能大打折扣，几乎就是线性查找了。

那有没有好的办法解决这个问题呢？解决这种多次插入新节点而导致的不平衡？这个时候红黑树就登场了。

红黑树

红黑树就是一种平衡的二叉查找树，说他平衡的意思是他不会变成“瘸子”，左腿特别长或者右腿特别长。除了符合二叉查找树的特性之外，还具体下列的特性：

1. 节点是红色或者黑色

2. 根节点是黑色

3. 每个叶子的节点都是黑色的空节点（NULL）

4. 每个红色节点的两个子节点都是黑色的。

5. 从任意节点到其每个叶子的所有路径都包含相同的黑色节点。

看下图就是一个典型的红黑树：

Snipaste_2020-08-01_11-16-36.png

很多童鞋又会惊讶了，天啊这个条条框框也太多了吧。没错，正式因为这些规则，才能保证红黑树的自平衡。最长路径不超过最短路径的2倍。

1、当插入和删除节点，就会对平衡造成破坏，这时候需要对树进行调整，从而重新达到平衡。那什么情况下会破坏红黑树的规则呢？

Snipaste_2020-08-01_11-29-29.png

向原来的红黑树插入值为14的新节点，由于父节点15是黑色节点，所以这种情况没有破坏结构，不需要做任何的改变。

2、向原树插入21呢？，看下图：

Snipaste_2020-08-01_11-34-51.png

由于父节点22是红色节点，因此这种情况打破了红黑树的规则4，必须作出调整。那么究竟该怎么调整呢？有两种方式【变色】和【旋转】分为【左旋转】和【右旋转】。

【变色】：

为了符合红黑树的规则，会把节点红变黑或者黑变红。下图展示的是红黑树的部分，需要注意节点25并非根节点。因为21和22链接出现红色，不符合规则4，所以把22红变黑：

Snipaste_2020-08-01_11-46-53.png

但这样还是不符合规则5，所以需要把25黑变红，看下图：

Snipaste_2020-08-01_11-47-29.png

你以为现在结束了？天真，因为25和27又是两个连续的红色节点(规则4)，所以需要将27红变黑。

Snipaste_2020-08-01_11-47-35.png

终于结束了，都满足规则了，舒服多了。

【左旋转】

也就是逆时针旋转两个节点，使父节点被自己的右孩子取代，而自己成为自己的左孩子，听起来吓死人，直接看图吧：

Snipaste_2020-08-01_11-49-11.png

【右旋转】

顺时针旋转两个节点，使得自己的父节点被左孩子取代，而自己成为自己的右孩子，看不懂直接看图吧：

Snipaste_2020-08-01_11-49-48.png

看起来这么复杂，到底怎么用呢？确实很复杂，我们讲下典型的例子，大家参考下：

以刚才插入21节点的例子：

Snipaste_2020-08-01_11-50-31.png

首先我们需要做的是变色，把节点25以及下方的节点变色：

Snipaste_2020-08-01_11-51-37.png

由于17和25是连续的两个红色节点，那么吧节点17变黑吗？这样是不行的，你想这样一来不就打破了规则4了吗，而且根据规则2，也不可能吧13变成红色。变色已经无法解决问题了，所以只能进行旋转了。13当成X，17当成Y，左旋转试试看：

Snipaste_2020-08-01_12-15-03.png

由于根节点必须是黑色，所以需要变色，结果如下图：

Snipaste_2020-08-01_12-15-59.png

继续，其中有两条路径（17-）8->6->NULL）的黑色节点个数不是3，是4不符合规则。

这个时候需要把13当做X，8当做Y，进行右旋转：

Snipaste_2020-08-01_12-20-39.png

最后根据规则变色：

Snipaste_2020-08-01_12-21-14.png

这样一来，我们终于结束了，经过调整之后符合规则。

那我们费这么大力气，这么复杂，这东西用在哪里，有哪些应用呢？

其实STL中的map就是用的红黑树。

TreeSet的两种排序方式比较

1.基本数据类型默认按升序排序

2.自定义排序

（1）自然排序：重写Comparable接口中的Compareto方法

（2）比较器排序：重写Comparator接口中的Compare方法

compare(T o1,T o2)      比较用来排序的两个参数。
 o1：代表当前添加的数据
 o2：代表集合中已经存在的数据
 0： 表示 o1 == o2
 -1(逆序输出)： o1 < o2 
 1(正序输出): o1 > o2 </pre>

1：o1 - o2（升序排列） -1：o2 - o1 (降序排列)

例子1

 public class Test {
  public static void main(String[] args) {

  /**
  * 自定义规则的TreeSet
  * 客户端排序：自己写一个比较器，转给TreeSet
  *
  * 比较规则
  * 当TreeSet集合添加数据的时候就会触发比较器的compare()方法
  */
  Comparator<Integer> comp = new Comparator<Integer>() {
  /**
  * o1 当前添加的数据
  * o2 集合中已经存在的数据
  * 0： 表示 o1 == o2
  * -1 ： o1 < o2
  * 1 : o1 > o2
  */
  @Override
  public int compare(Integer o1, Integer o2) {
  System.out.println(o1+"--"+o2);
  return o2 -o1; //输出53 33 10，降序排序
  //  return  0;  //只输出一个元素：33
  //   return -1; //输出53 10 33，倒序输出
  //  return 1;  //输出33 10 55
  }
  };

  Set<Integer> s2 = new TreeSet<>(comp);
  s2.add(33);
  s2.add(10);
  s2.add(55);

  System.out.println(s2); //输入53 33 10，降序排序

  }
  }

例子2：

 /**
  * 使用TreeSet和Comparator（使用匿名类），写Test.java
  * 要求：对TreeSet中的元素
  *     1，2，3，4，5，6，7，8，9，10进行排列，
  * 排序逻辑为奇数在前偶数在后，
  * 奇数按照升序排列，偶数按照降序排列
  * 输出结果：1 3 5 7 9 10 8 6 4 2
  */
  public class Test {
  public static void main(String[] args) {
  Set<Integer> s = new TreeSet<>(new Comparator<Integer>() {
  //重写compare方法
  @Override
  public int compare(Integer o1, Integer o2) {
  System.out.println("o1="+o1+" o2="+o2);
  if(o2%2==0){
  if (o1%2==0){
  return o2 -o1;
  }else{
  return -1;
  }
  }else {
  if (o1%2==0){
  return 1;
  }else{
  return o1 -o2;
  }
  }
  }
  });
  s.add(2);
  s.add(6);
  s.add(4);
  s.add(1);
  s.add(3);
  s.add(5);
  s.add(8);
  s.add(10);
  s.add(9);
  s.add(7);
  Iterator iterator = s.iterator();

  while(iterator.hasNext()){
  System.out.print(iterator.next()+" ");
  }
 ​
  }
  }

输出结果：

Snipaste_2020-08-01_12-26-19.png
上一篇 下一篇

猜你喜欢

热点阅读