Java集合专题

1. Java集合概述

Java集合也叫做容器,是由Collection接口和Map接口继承而来的

其中,Collection主要用来存放单一元素,Map用来存放键值对

2.List, Set, Queue, Map 四者的区别？

List:存储的数据是有序的,可以重复的

Set:存储的数据是无序的,不可重复

Queue:按照特定的排队规则来确定先后顺序如优先级队列等,存储的顺序是有序的,可以重复的

Map:使用键值对key-value存储,其中,它的key是不可重复的,而value是无序的,可重复的

3. 说一下常用集合的实现方式

首先常用的集合有List、Set、Queue、Map,那么其主要的实现有:

首先List它有三个比较常用的实现类,分别是:

• Vector：它的底层实现是Object[]数组,并且它是线程安全的,这是因为它在add()等方法上加上了synchronized同步锁,实现了线程安全,但是这也意味着它的性能是比较差的,因为使用了悲观锁
• ArrayList:它的底层实现是Object[]数组,相比来说,它适用于单机单线程环境下,可以当成一个可自动扩容的数组来使用
• LinkedList:它的底层实现原理是双向链表,具有头结点和尾结点。

Set它有三个比较常用的实现类

HashSet(无序的、唯一的):它是基于HashMap实现的,底层使用的是HashMap进行元素的保存,判断是否唯一的方法是使用contains()

LinkedHashSet:它是HashSet的子类,并且其内部是通过LinkedHashMap来实现的,它内部是基于HashMap进行实现的

TreeSet:红黑树,自平衡的排序二叉树

Queue有两个比较常用的实现类

• PriorityQueue:Object[]数组实现二叉堆
• ArrayQueue:Object[]+双指针

Map的实现有4个比较常用的实现类

• HashMap:其底层是用数组+链表实现的,其中数组是快速索引的基础,而链表是为了解决哈希冲突而引入的一种机制,在数据结构中我们称之为拉链法,相对的还有另外一种方法叫做再哈希法,它是直接再次进行哈希运算,在JDK1.8之后引入了红黑树

HashMap的扩容机制

• 如果当前的数组长度>64,那么将会先进行数组的扩容
• 如果当前的数组长度>=64,而且存在有一条链表的长度>8,那么这时候就会将链表转化为红黑树

这样做的目的是避免在链表上遍历的复杂度太高,提升查询效率

4. 集合应该要如何选择?

当需要存储键值对这样的结构的时候,我们选用Map底下的这几种数据结构,根据特性,可以这样归纳

• 单机单线程:HashMap或者LinkedHashMap
• 保证线程安全:ConcurrentHashMap
• 需要排序TreeMap

当需要存储的是单值这样的结果的时候,我们选用Collection下的容器

• 需要保证元素唯一:Set
• 不需要保证元素唯一:ArrayList或者LinkedList

而ArrayList和LinkedList的选择看插入的位置不同,如果都是在尾部插入,而且数组的长度能够提前预知,那么ArrayList最好,如果存在大量的中间插入,选择LinkedList最好

同时,如果作为查询用途,那么如果是大量的随机查询,那么采用ArrayList是最好的

5. ArrayList和LinkedList有什么区别?

这个问题可以从特性层面上进行回答,也就是线程安全性和底层的实现来看

首先ArrayList和LinkedList其内部的方法都没有使用同步关键字修饰,也没有CAS乐观锁机制,因此都不是线程安全的

第二个方面是他们的底层数据结构不同,ArrayList的底层数据结构是用Object[]实现的,而LinkedList的底层数据结构是链表实现的,在jdk1.7之前使用的是循环链表,而在jdk1.8之后使用的是双向链表

第三个方面是插入和删除这些常见操作的时间复杂度

首先ArrayList在尾部进行数据的插入的时候,此时的时间复杂度为O(1),但是如果在数组的中间进行插入/删除,将会导致大量的元素搬动,将导致O(n-i)的时间复杂度

而LinkedList是采用链表进行存储的,所以如果是在头尾插入元素,只需要修改被插入元素的指针指向和头尾节点的指向即可,时间复杂度为O(1),对应的api有addLast()、addFirst()、removeLast()、removeFirst(),但是如果是要在中间进行元素的插入的话,同样是需要O(n)的时间复杂度的,因为要先进行查找后进行操作

第四个方面是查询效率问题,LinkedList由于遍历的特性,因此在此情况下不支持随机访问,而ArrayList是支持随机访问的

第五个方面是内存空间占用的问题,ArrayList和LinkedList均存在一定的额外空间开销,其中ArrayList的额外内存开销是其底层数组通常需要预留一定量的空间,从而导致空间的浪费

而LinkedList需要维护头尾节点和中间的指针指向,这也导致了空间开销

6. 你刚才提到双向链表和循环链表,说一下都是什么?

双向链表,一个节点包括两个指针,一个指针pre指向前驱节点,一个指针next指向后续节点

循环链表,区别点在于头尾节点,尾节点的next指针指向头节点,形成环,常见的检测环的算法有快慢指针算法,当快慢指针相遇的时代表有环,当遇到null的时候代表无环

7. ArrayList是如何实现随机访问的?

实际上ArrayList实现随机访问是依据于底层的数据结构的特性来实现的。但是在

首先要了解接口

public interface RandomAccess {}

这个接口和可序列化接口一致,是一种标记性接口,用来标记这个类支持随机访问,这个标记有什么用?

它可以用来区分某些方法的底层实现

比如说常见的二分搜索,当底层数据结构支持随机访问的时候,那么在二分的时候就可以使用下标进行二分

否则的话只能通过迭代器进行二分

8. ArrayList是如何扩容的?

回答这个问题,首先要知道ArrayList是如何构建其底层数据结构的,因此先要从构造方法开始谈起

private static final int DEFAULT_CAPACITY = 10;//默认数组的大小为10,当超过后会触发扩容

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

  /**
   *默认构造函数，使用初始容量10构造一个空列表(无参数构造)
   */
  public ArrayList() {
      this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  }

  /**
   * 带初始容量参数的构造函数。（用户自己指定容量）
   */
  public ArrayList(int initialCapacity) {
      if (initialCapacity > 0) {//初始容量大于0
          //创建initialCapacity大小的数组
          this.elementData = new Object[initialCapacity];
      } else if (initialCapacity == 0) {//初始容量等于0
          //创建空数组
          this.elementData = EMPTY_ELEMENTDATA;
      } else {//初始容量小于0，抛出异常
          throw new IllegalArgumentException("Illegal Capacity: "+
                                             initialCapacity);
      }
  }


 /**
  *构造包含指定collection元素的列表，这些元素利用该集合的迭代器按顺序返回
  *如果指定的集合为null，throws NullPointerException。
  */
   public ArrayList(Collection<? extends E> c) {
      elementData = c.toArray();
      if ((size = elementData.length) != 0) {
          // c.toArray might (incorrectly) not return Object[] (see 6260652)
          if (elementData.getClass() != Object[].class)
              elementData = Arrays.copyOf(elementData, size, Object[].class);
      } else {
          // replace with empty array.
          this.elementData = EMPTY_ELEMENTDATA;
      }
  }

其中,无参构造函数中使用默认初始化的构造方法的时候,分配给底层的数据结构实际上是一个空数组,而其容量的初始化是在给数组添加第一个元素的时候,才会真正地分配容量

public boolean add(E e) {
 //添加元素之前，先调用ensureCapacityInternal方法
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //这里看到ArrayList添加元素的实质就相当于为数组赋值
    elementData[size++] = e;
    return true;
}

其中ensure这个函数是为了扩容的,关键所在

 //得到最小扩容量
  private void ensureCapacityInternal(int minCapacity) {
      if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            //当底层数组是空的时候,执行初始化
            // 获取默认的容量和传入参数的较大值
            // 初始时,size为0,size+1 = 1,然后它发现比初始容量要小,因此取10
            //这才是真正的初始化
          minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
      }
      ensureExplicitCapacity(minCapacity);
  }

//判断是否需要扩容
  private void ensureExplicitCapacity(int minCapacity) {
      modCount++;
      // overflow-conscious code
      if (minCapacity - elementData.length > 0)//最少所需的容量-目前容量>0,此时需要扩容
          //调用grow方法进行扩容，调用此方法代表已经开始扩容了
          grow(minCapacity);
  }

private void grow(int minCapacity) {
    // oldCapacity为旧容量，newCapacity为新容量
    int oldCapacity = elementData.length;
    
    //将oldCapacity 右移一位，其效果相当于oldCapacity /2，
    //我们知道位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的1.5倍，
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    
    //然后检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量，
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
   // 如果新容量大于 MAX_ARRAY_SIZE,进入(执行) `hugeCapacity()` 方法来比较 minCapacity 和 MAX_ARRAY_SIZE，
   //如果minCapacity大于最大容量，则新容量则为`Integer.MAX_VALUE`，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 `Integer.MAX_VALUE - 8`。
    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);
}

这一段的话就是当目前容量达到了Integer.MAX_VALUE-8的时候,就将容量直接扩大到MAX_VALUE

至此,扩容结束

关于System.arraycopy()和Arrays.copyOf()

实际上,System.arraycopy()是一个native方法,在操作系统层面上进行操作的,而Arrays.copyOf()是属于一种装饰者模式,它包装了功能

具体区别是,使用System.arraycopy()的时候需要手动创建数组,而Arrays.copyOf()则是根据用户复制信息,自动创建数组并且返回,本质上都是一样的.

ensureCapacity():此方法是重新分配数组空间,当初始化的数组长度不够用的时候,那么就可以使用该方法来重新分配内存空间,避免频繁的自动扩容

回答问题:ArrayList的扩容实际上非常符合开发者的直觉,它在每次添加元素的时候,会先检查当前数组的容量是否能够装下新的元素,如果无法装下新的元素,就会触发扩容,在扩容的时候有两个关键参数:

• 扩容因子:在ArrayList中,如果当容量不够的时候,会先尝试将当前的size*1.5,会得到一个newSize,当这个newSize依然比当前数组需要扩容产生的长度要小,那么就会直接将需要扩容的长度赋值给它
• 数组的最大容量:这个最大容量标志着数组中能够存放的数组的最大数量,当第一次超过这个数量的时候,会将其设置为Integet.MAX_VALUE,如果后续继续增加,则整数会溢出,导致OOM异常

它的扩容实际上是在底层重新生成数组并且复制,因此扩容的所带来的性能问题是非常严重的

为什么不直接分配空间呢?

这是一种懒加载的思想,有的类中如果声明了List,并且初始化,但是需要在一定条件下才会添加条件,假设一直没有触发条件,就会导致10个空间被白白浪费掉,因此这是一种性能优化的手段

9. comparable 和 Comparator 的区别

首先他们两者都是接口:

• comparable接口实际上出自于java.lang包,它有一个compareTo(Object obj)方法用来排序
• comparator接口实际上出自于java.util包,它有一个compare(Object obj1,Object obj2)

一般来说,当我们需要对一个集合进行排序的时候,我们就要重写compareTo方法或者compare方法

如果使用Comparator<>(),那就是自定义排序器,并且传入对应的执行方法,比如Collection.sort()

如果使用comparable则可以直接传入有序性的数据结构

关于返回值

@Override
public int compare(Integer o1, Integer o2) {
    return o2.compareTo(o1);
}

当compare的结果依赖于compareTo的结果

• 当compareTo的结果>0的时候,是说明当前元素较大,需要发生元素的交换
• 当compareTo的结果<0的时候,是说明当前元素较小,不需要交换元素
• 当compareTo的结果=0的时候,是说明当前元素不需要交换位置

只有当返回值为负数的时候,才会发生元素的交换

如果返回负数,第一个参数放前面;

10. 无序性和不可重复性怎么理解

• 无序性并不代表随机存放,而是说元素在内存中的存储位置不能够根据顺序进行判定
• 不可重复性指的是添加的元素按照equals()判断时,返回false,这时候认为他们俩是不一样的,因此在集合中我们需要重写equals()和hashCode()

11. 比较一下HashSet、LinkedHashSet和TreeSet有什么异同

• HashSet、LinkedHashSet和TreeSet都是Set的实现类,都能保证元素的唯一性,但是不保证线程安全
• HashSet、LinkedHashSet、TreeSet的主要区别在于底层实现的数据结构不同
  • HashSet可以看成是HashMap的装饰器,其底层是基于HashMap实现的,保证唯一性是通过HashMap的key唯一性的这个特性实现的
  • LinkedHashSet可以看成是HashSet的升级版,它的底层数据结构是链表+HashMap,它能够保证元素的插入和取出顺序是满足FIFO的
  • TreeSet的底层数据结构是红黑树,元素是有序的,排序的方式为自然排序和定制排序

12. Queue和Deque有什么区别?

Queue 是单端队列，只能从一端插入元素，另一端删除元素，实现上一般遵循 先进先出（FIFO） 规则。

Queue 扩展了 Collection 的接口，根据 因为容量问题而导致操作失败后处理方式的不同 可以分为两类方法: 一种在操作失败后会抛出异常，另一种则会返回特殊值。

Queue 接口	抛出异常	返回特殊值
插入队尾	add(E e)	offer(E e)
删除队首	remove()	poll()
查询队首元素	element()	peek()

Deque 是双端队列，在队列的两端均可以插入或删除元素。

Deque 扩展了 Queue 的接口, 增加了在队首和队尾进行插入和删除的方法

13. ArrayDeque 与 LinkedList 的区别

ArrayDeque 和 LinkedList 都实现了 Deque 接口，两者都具有队列的功能，但两者有什么区别呢？

首先ArrayDeque是双端队列的线性实现方式,它的关键参数是头尾指针和数组,大致工作原理如:

这是初始化后的ArrayDeque,在进行了一次头部插入和尾部插入后:

首先,插入头部的运算式子是

elements[head = (head - 1) & (elements.length - 1)] = e;

可以看到,它每次都是head-1,当为0的时候就插入到尾部了

elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
	doubleCapacity();

那么相对的,tail是+1,然后两个指针不断靠近,当head == tail的时候,这时候宣告队列已满,然后扩容

System.arraycopy(elements, p, a, 0, r); //作者注：将原数组head到末尾的数据拷贝到新数组从0下标下标位置
System.arraycopy(elements, 0, a, r, p); //作者注：将原数组0到tail的数据拷贝到新数组

其中关键的是保证头尾指针的位置没有变化,实现比较复杂

ArrayDeque 是基于可变长的数组和双指针来实现，而 LinkedList 则通过链表来实现。

ArrayDeque 不支持存储 NULL 数据，但 LinkedList 支持。

ArrayDeque 是在 JDK1.6 才被引入的，而LinkedList 早在 JDK1.2 时就已经存在。

ArrayDeque 插入时可能存在扩容过程, 不过均摊后的插入操作依然为 O(1)。虽然 LinkedList 不需要扩容，但是每次插入数据时均需要申请新的堆空间，均摊性能相比更慢

ArrayDeque在实现栈的时候性能更佳,因为只需要执行简单的算术运算,而LinkedList还要执行节点指向的更新

14. 说一说 PriorityQueue

PriorityQueue被称为优先级队列,其底层实现的数据结构是二叉堆,因此每次都要执行相关的堆排序,它通过堆元素的上浮和下沉,实现了在O(logN)的时间复杂度内插入元素和删除堆顶元素

它是非线程安全的,不支持存储null和non-comparable的对象,这些对象不能在堆上确定位置

它默认是小顶堆,可以传入一个Comparator作为自定义排序器

private void sink(int x) {
    // 如果沉到堆底，就沉不下去了
    while (left(x) <= size) {
        // 先假设左边节点较大
        int max = left(x);
        // 如果右边节点存在，比一下大小
        if (right(x) <= size && less(max, right(x)))
            max = right(x);
        // 结点 x 比俩孩子都大，就不必下沉了
        if (less(max, x)) break;
        // 否则，不符合最大堆的结构，下沉 x 结点
        swap(x, max);
        x = max;
    }
}

private void swim(int x) {
    // 如果浮到堆顶，就不能再上浮了
    while (x > 1 && less(parent(x), x)) {
        // 如果第 x 个元素比上层大
        // 将 x 换上去
        swap(parent(x), x);
        x = parent(x);
    }
}

// 父节点的索引
int parent(int root) {
    return root / 2;
}
// 左孩子的索引
int left(int root) {
    return root * 2;
}
// 右孩子的索引
int right(int root) {
    return root * 2 + 1;
}

15. HashMap和HashTable的区别

问题可以按照线程安全性、查询效率、对空键空值的支持、扩容容量、底层数据结构这几个方面机芯回答

• 线程安全方面,由于HashTable内部的实现的方法有同步关键字synchorinzed修饰,因此它是线程安全的,而HashMap则没有,然而目前来说,实现HashMap的线程安全有两种方式,一种是在业务代码中加锁,或者是直接替代使用ConcurrentHashMap,基本上不会因为并发问题而使用HashTable
• 效率:因为线程安全问题,在单机单线程的环境下,HashMap的效率要高于HashTable
• 对空键空值的支持,这个问题需要从它的底层源代码来分析,关键在于它的哈希值是如何产生的

对于HashTable:其底层源码是这样描述的,当key == null的时候直接抛出异常,那么为什么要抛出异常呢?

这是因为这个集合设计者考虑到了并发时的情况,如果在多线程的环境下,有如下代码

private HashTable<String,String> table = new HashTable<>();
public void threadOneOps(String key){//线程1的操作代码
    if(table.contains(key)){
        table.get(key);
    }
}
public void threadTwoOps(String key){//线程2的操作代码
    table.remove(key);
}
//开始线程并发....

假设线程1和线程2的key都是相同的,初始时,存到table中一个键值对(key,value)

然后线程1执行,查询key,发现存在,然后此时线程2上CPU,然后将key删除掉了

然后线程1恢复执行,它去get(key),得到的肯定是null,这时候就存在问题了

问题主要在于你得到的这个null是有歧义的

到底是之前有个线程put进去了一个null,还是说是压根就没有put这个key-value进去?

程序执行的结果将会依赖于线程并发的顺序。

在这里的话就产生了一个并发安全问题,而本身HashTable是作为一个线程安全容器进行设计的,因此为了避免这样的歧义问题,就禁止使用空key或者空value了

禁用null能够解决这个问题吗?

可以。主要是对于这个问题

到底是之前有个线程put进去了一个null,还是说是压根就没有put这个key-value进去?

如果禁用null的话,那么key为null或者value为null的原因一定是根本就没有存在过这个值

我们有时候希望判断一个key有没有被放进过集合中,如果允许key-value为null的话,在并发的情况下就无法判断了。那么为什么HashMap又允许呢?这是因为HashMap仅支持线程下执行,多线程下执行将会因为modCount的异常修改而无法使用

那么单线程下就没有这个问题了吗?因为各个指令都是串行执行的,假设你put进去了一个(null,null),那么这时候通过hash()方法,它会将key为null的这个entry映射到数组下标为0的位置,然后存储起来,这时候你通过containsKey()就可以准确地知道这个key是否存在过

• 初始容量大小和每次扩充容量的大小不同:

① 创建时如果不指定容量初始值，Hashtable 默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1。HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。② 创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为 2 的幂次方大小（HashMap 中的tableSizeFor()方法保证）。也就是说 HashMap 总是使用 2 的幂作为哈希表的大小。

• 底层数据结构

JDK1.8以后的HashMap采取了数组+链表(红黑树)的结构,其执行机制是:当数组的长度不超过64的时候而链表的长度大于8的时候,再出现哈希冲突的时候,会直接扩容,而只有当数组长度超过64的时候,链表的长度超过8的时候,会将这条链路转化为红黑树,而HashTable则没有这样的机制,这也是为什么被淘汰的原因

16. HashMap和HashSet的区别

HashSet是基于HashMap实现的,它保证数据的唯一性是基于key的唯一性进行实现的。

其中比较key是否相等的原理是:

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

首先通过hash值计算得出对应的索引,然后通过equals()方法比较是否相等

从这里可以看出,当在同一个哈希桶中,其hashCode()一定相同,那么我们为了区分这个对象,一定要在equals()方法加入这个对象相关的特征信息,否则的话在集合内部工作就可能出现问题

因此当使用到集合存储对象的时候,如果你重写了equals()方法,那么你一定就要重写hashcode()方法

这是因为当两个对象生成的hashCode有可能一样,但是对象内部的数据可能是不一样的,因此你必须加上对应的特征值。

同时这样做也可以提高效率,这是因为在类似于set这样的数据结构上,通过hashcode可以快速定位到表上的位置,然后查看这个位置上是否有对应的值,这样一来就减少了遍历的次数。

17.HashMap和TreeMap的区别

TreeMap 和HashMap 都继承自AbstractMap ，但是需要注意的是TreeMap它还实现了NavigableMap接口和SortedMap 接口。

实现 NavigableMap 接口让 TreeMap 有了对集合内元素的搜索的能力。

实现SortedMap接口让 TreeMap 有了对集合中的元素根据键排序的能力。默认是按 key 的升序排序，不过我们也可以指定排序的比较器。

综上，相比于HashMap来说 TreeMap 主要多了对集合中的元素根据键排序的能力以及对集合内元素的搜索的能力。

18. HashSet是如何检查重复的?

当你将对象加入到HashSet的时候,HashSet会先计算对象的hashCode的值来判断对象在数组中的位置,同时也会与其他加入的对象的hashCode()的值进行比较,如果没有相同的hashcode,那么证明没有重复出现,否则的话,如果发现有相同的hashcode对象,再通过equals()方法进行比较

在 JDK1.8 中，实际上无论HashSet中是否已经存在了某元素，HashSet都会直接插入，只是会在add()方法的返回值处告诉我们插入前是否存在相同元素。

19. HashMap底层实现原理

HashMap的底层实现可以简单描述为数组+链表,结合在一起使用也就是链表的散列,大致工作原理如下:

• 先执行hash(key.hashCode()) = hash,key经过扰动函数后得到hash值

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

扰动函数可以降低哈希碰撞的概率,指的是不同的输入造成相同的输出

• 然后通过(n-1) & hash值来决定这个对象存放的索引
• 如果当前位置存在元素的话,就判断该元素和要存入的元素的hash值和key是否相同,如果相同的话就直接覆盖该元素,不相同的话就通过拉链法解决

比较hash是快速的,而比较key是通过equals()的,因此先通过hash过滤掉一部分数据,之后实在无法确定才通过key的equals()方法进行判断

HashMap的问题在于当冲突太多时,会导致拉链太长,导致在搜索的时候时间复杂度太高,因此引入了红黑树

将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树。

20. HashMap的长度为什么是2的幂次方

这个问题要从存放元素的操作说起

if ((p = tab[i = (n - 1) & hash]) == null)
           tab[i] = newNode(hash, key, value, null);

可以看到,每个元素落在数组中的位置与数组长度n有关,计算的式子为(n - 1) & hash,这样设计的原因是hash是一个int类型,其范围是在-2147483648 到 2147483647大约40亿空间,因此还需要将哈希值和(n-1)取余得到一个合法的下标,按照正常的设计来说是这样的:

i = hash%length;

注意这里用到了取余运算,那么每一次都要这样计算下标,非常消耗性能

有公式:当length是2的n次方的时候,此时:

hash%length==hash&(length-1)

这时候我们就可以用位运算代替取余运算了,提高性能

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

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

数据插入的原理

在扩容的时候,会将原本的数组扩大为两份,而在处理拉链法产生的数组的时候,它采用的是头插法

也就是原本的结构是A->B->C,经过扩容后就变成了C->B->A,在单线程下是没有任何问题的,但是在多线程下,由于存在线程栈隔离的问题,就产生了问题了

在多线程并发环境下,假设两个线程同时扩容

如图所示,在扩容开始的时候,T1、T2指向头结点A,T1.next和T2.next指向节点B

这两个指针变量都存在于各自的线程栈中,因此是相互隔离的,只有线程内部可以看到它

如上图所示,在扩容后,线程T1结束了,然而T2依然指向A,而T2.next指向B

然而这时候它依然会执行扩容操作,会导致这样的情况发生

这个环是怎么产生的呢?来看源代码

void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        //遍历旧表
        for (Entry<K,V> e : table) {
            while(null != e) {
                Entry<K,V> next = e.next;
                //如果hashSeed变了，需要重新计算hash值
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                //得到新表中的索引
                int i = indexFor(e.hash, newCapacity);
                //将新节点作为头节点添加到桶中
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
}

• 第一次循环,这时候e = T2 = A,e.next = T2.next = B,这时候唤醒的时候是从indexFor后开始执行的

//头插法,A.next = newTable[i],初始为null,也就是A.next = null
e.next = newTable[i];
//让A上来当头节点
newTable[i] = e;
//然后e = B
e = next;
//下一次循环

//头插法,B.next = newTable[i]
e.next = newTable[i];
//让B上来当头节点
newTable[i] = e;
//然后e = B.next
e = next;

这时候B.next是什么东西?是A,也就是说下一次会执行的是

//头插法,A.next = newTable[i],初始为null,也就是A.next = null
e.next = newTable[i];
//让A上来当头节点
newTable[i] = e;
//然后e = B
e = next;
//下一次循环

这样的话就导致死循环了

总结: 本身来说HashMap不适合在并发的情况下使用,因此应该尽量使用concurrentHashMap。

在JDK1.8中官方彻底修复这个问题,将头插法修改为了尾插法,解决的思路是解决之前乱序插入的问题,维持链表的顺序一致,这样就可以保证不死循环了

22. ConcurrentHashMap和HashTable的区别

我们知道ConcurrentHashMap和HashTable是线程安全容器,其具体区别在于实现线程安全的不同

而且在JDK1.8和1.7的实现有很大区别

• 底层数据结构:JDK1.7的ConcurrentHashMap是采用分段的数组和链表实现的,JDK1.8采用的数据结构跟HashMap结构是一样的,数组+链表/红黑树,HashTable是采用数组+链表实现的
• JDK1.7中是基于分段锁的方式实现线程安全的,详解讲解,每一把锁只锁容器中的一部分数据,多线程访问不同数据段的时候,就不会产生锁竞争的问题,只有当访问同一个数据段的时候才会产生锁竞争的问题

分段锁能够解决线程安全的问题,但是其缺点是段的概念决定了锁的粒度太大了,比如说存在数据段中有节点Segment{Node1{1},Node2{2},Node3{3}},当用户只想访问Node1的时候,这时候却会将Node2和Node3进行加锁,粒度控制得不够细腻,将会影响并发度,具体的数据结构见下图

在实现中,可以看到它是基于Segment数组结构和HashEntry数组结构组成的

• JDK1.8中是基于Node节点加锁的方式实现线程安全的,详细讲解:

在1.8中,完全摈弃了Segment的概念,而是直接用Node数组+红黑树/链表的方式来作为底层数据结构,而在并发安全中,为了提高并发度,同时使用了悲观锁和乐观锁,也就是使用了synchronized 和CAS机制

值得注意的是,当哈希桶中的是链表的时候,使用的是Node结构,当哈希桶中是红黑树的时候,使用的是TreeNode,当冲突链表达到一定的长度的时候,链表会转换为红黑树

TreeNode是存储红黑树节点，被TreeBin包装。TreeBin通过root属性维护红黑树的根结点，因为红黑树在旋转的时候，根结点可能会被它原来的子节点替换掉，在这个时间点，如果有其他线程要写这棵红黑树就会发生线程不安全问题，所以在 ConcurrentHashMap 中TreeBin通过waiter属性维护当前使用这棵红黑树的线程，来防止其他线程的进入。

static final class TreeBin<K,V> extends Node<K,V> {
        TreeNode<K,V> root;
        volatile TreeNode<K,V> first;
        volatile Thread waiter;
        volatile int lockState;
        // values for lockState
        static final int WRITER = 1; // set while holding write lock
        static final int WAITER = 2; // set when waiting for write lock
        static final int READER = 4; // increment value for setting read lock
...
}

23. ConcurrentHashMap是如何实现线程安全的

这道题考察的是底层实现原理,可以综合22题学到的知识进行回答

在JDK1.7以前,ConcurrentHashMap是基于Segment+HashEntry的结构进行实现的,Segment本质上是一种可重入锁,它具有锁的功能。

一个 ConcurrentHashMap 里包含一个 Segment 数组，Segment 的个数一旦初始化就不能改变。 Segment 数组的大小默认是 16，也就是说默认可以同时支持 16 个线程并发写。

那么是如何写的呢?假设一个线程要写HashEntry中的某个元素,那么它必须获得这个HashEntry所对应的Segment的锁,否则的话将被阻塞

---

在JDK1.8以后,ConcurrentHashMap是基于桶哈希+Node结构和CAS+synchorized实现并发安全的,在1.7中锁定的可能是哈希数组中的多个索引,但是在1.8之后,基于Node数组,它只锁定当前链表或者红黑树的首节点,只要读取的不是同一个hash值所对应的节点,那么就不会造成阻塞。

细化了锁的粒度,提高了并发效率

个人认为还可以加上读写锁和意向锁,进一步提高效率

24. JDK 1.7 和 JDK 1.8 的 ConcurrentHashMap 实现有什么不同？

线程安全实现方式 ：JDK 1.7 采用 Segment 分段锁来保证安全， Segment 是继承自 ReentrantLock。JDK1.8 放弃了 Segment 分段锁的设计，采用 Node + CAS + synchronized 保证线程安全，锁粒度更细，synchronized 只锁定当前链表或红黑二叉树的首节点。

Hash 碰撞解决方法 : JDK 1.7 采用拉链法，JDK1.8 采用拉链法结合红黑树（链表长度超过一定阈值时，将链表转换为红黑树）。

并发度 ：JDK 1.7 最大并发度是 Segment 的个数，默认是 16。JDK 1.8 最大并发度是 Node 数组的大小，并发度更大。

25. HashMap中的参数了解多少?

• loadFactor 加载因子

loadFactor 加载因子是控制数组存放数据的疏密程度，loadFactor 越趋近于 1，那么 数组中存放的数据(entry)也就越多，也就越密，也就是会让链表的长度增加，loadFactor 越小，也就是趋近于 0，数组中存放的数据(entry)也就越少，也就越稀疏。

loadFactor 太大导致查找元素效率低，太小导致数组的利用率低，存放的数据会很分散。loadFactor 的默认值为 0.75f 是官方给出的一个比较好的临界值。

给定的默认容量为 16，负载因子为 0.75。Map 在使用过程中不断的往里面存放数据，当数量达到了 16 * 0.75 = 12 就需要将当前 16 的容量进行扩容，而扩容这个过程涉及到 rehash、复制数据等操作，所以非常消耗性能

加载因子决定了HashMap的两个特征信息

• 存储数据在数组中的疏密程度,当加载因子太小,就会导致数组的存储过于稀疏,数组利用率很低,太大话将导致很多哈希碰撞,导致红黑树/链表的规模太大。
• 每个节点的维护代价

• threshold

threshold = capacity * loadFactor，当 Size>=threshold的时候，那么就要考虑对数组的扩增了，也就是说，这个的意思就是 衡量数组是否需要扩增的一个标准。