Java集合

ArrayList和linkedList的区别

• 两者都不同步，也就是不保证线程安全。
• 底层数据结构：A用的是Object数组，L使用双向链表。（1.6之前是循环列表，JDK1.7取消循环）
• 插入和删除元素是否受元素位置影响：A是数组，默认追加到末尾，但是如果指定i位置插入和删除（add(int index, E element)）时间复杂度是$O(n-i)$，因为顺序后移。L是链表，插入删除是O（1）。如果是在I位置插入删除，时间复杂度是O(n)，因为需要先移动都指定位置。
• 快速随机访问：L不支持，A支持。
• 内存占用空间：A浪费体现在list列表的结尾会预留一定的容量空间。而L体现在他的每一个元素消耗更多空间（存放直接后继和前驱以及数据）。

ArrayList和Vector区别，为什么用A取代V

• A是List的主要实现类，适用于频繁的查找，线程不安全。
• V是List的古老实现类，底层Object数组，线程安全。

ArrayList的扩容机制

扩容机制

hashMap和Hashtable区别

• 线程安全

  M非线程安全，T线程安全。因为T内部的方法经过synchronized修饰

• 效率

  因为线程安全，M效率高，T淘汰，不使用。

• 对null key和Null value的支持

  M可以存储null的K和V，但是null作为K只能有一个，作为V可以多个。T不可。

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

  • 不指定初始：T默认11，每次扩2n+1；M初始16，每次2倍
  • 给定：T直接使用给定大小，M将其扩充为2的幂次方。

• 底层数据结构

  DK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。Hashtable 没有这样的机制。

M带有初始容量的构造函数

public HashMap(int initialCapacity, float loadFactor) {
      if (initialCapacity < 0)
          throw new IllegalArgumentException("Illegal initial capacity: " +
                                             initialCapacity);
      if (initialCapacity > MAXIMUM_CAPACITY)
          initialCapacity = MAXIMUM_CAPACITY;
      if (loadFactor <= 0 || Float.isNaN(loadFactor))
          throw new IllegalArgumentException("Illegal load factor: " +
                                             loadFactor);
      this.loadFactor = loadFactor;
      this.threshold = tableSizeFor(initialCapacity);
  }
   public HashMap(int initialCapacity) {
      this(initialCapacity, DEFAULT_LOAD_FACTOR);
  }

下面的方法保证了M总是使用2的幂次方作为哈希表的大小

/**
 * Returns a power of two size for the given target capacity.
 */
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

HashMap和HashSet的区别

S底层就是基于M实现的。

M	S
实现了Map接口	实现了Set接口
存储键值对	仅存储对象
调用put添加元素	调用Add添加元素
使用键计算hashcode	成员对象计算hashcode。对象hash可能相等，用equals()判断对象的相等性

HashSet如何检查重复

先计算hashcode值判断对象加入位置，同时与其他加入的对象的hc值比较，没有相符，假设对象没有重复出现。有相同，调用equals()方法检查hc相等的对象是否真的相等。相等，就不会加入。

hashcode和equals()的规定

• 对象相等，则hashcode相同
• 对象相等，对两个equals()返回true
• 两个对象有相同的hashcode值，也不一定相等。

综上，如果一个类的equals()方法被覆盖过，则hashcode()也必须被覆盖。

==与equals的区别

• 基本类型来说，==比较的是值相等
• 对于引用类型，==比较的是两个引用是否指向同一个对象地址。
• 对于引用类型，equals 如果没有被重写，对比它们的地址是否相等；如果 equals()方法被重写（例如 String），则比较的是地址里的内容。

hashMap的底层实现原理

Node对象，有key,value,hash,next.

hash字段的值是key.hashcode()二次加工得到的，高16位于低16位异或(实际的table长度不会很大，一般在16位以内，这么一来，高16位就浪费了)。寻址算法是hash&(table.length-1)，长度一定是2的次方树，length转化为二进制一定是1高位。其余是0，减1之后，就全是1了。

Put写数据的流程。先获得slot，这里有四种情况：

• slot是null，直接放。
• slot不是null，但是没有链化。先判断node对象的key和当前对象的key是不是完全相等，相等就replace操作，否则就是hash冲突。
• slot链化，但是没有树化。不一致则加链。判断有没有达到树化阈值，有的话则转化为红黑树
• slot已经树化，则红黑树的平衡操作。

在JDK1.8之前

在1.8之前，HashMap的底层是散列表。通过Key的hashcode经过扰动函数处理得到hash值，通过(n-1)&hash判断当前元素的存放位置，位置存在元素，判断该元素与要存入的元素的hash值以及Key是否相同，相同直接覆盖，不相同通过拉链法解决冲突。

扰动函数就是hash方法，是为了防止一些实现比较长的hashcode()方法，减少碰撞。

在JDK1.8之后

解决冲突有大变化，当链表长度大于阈值（默认是8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，减少搜索时间。

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

为了存取高效，减少碰撞，尽量把数据分配均匀。hash的值范围是-2147483648到2147483647，加起来大概40亿的映射空间，只要哈希函数映射的比较均匀，一般不太容易碰撞。但是40亿长度的数组，内存放不下。所以这个散列值不能直接拿来用。用之前还要对数组的长度取模运算，得到的余数才是要存放的数组下标。数组下标的计算方法是(n-1)&hash。n是数组长度，这也就解释了为什么长度是2的幂次方。

算法如何设计？

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

M多线程导致死循环问题

并发情况下的Rehash会造成元素之间形成一个循环链表。不过jdk1.8之后解决了这个问题，但是多线程可能导致其他的问题比如数据丢失，并发情况下推荐使用ConcurrenthashMap。

ConcurrentHashMap和hashTable的区别

主要体现在实现线程安全的方式不同。

• 底层数据结构

  1.7的C底层采用分段的数组+链表实现，1.8的数据结构是数组+链表/红黑树。

  T是数组+链表，数组是主体，链表是为了解决冲突。

• **实现线程安全的方式(重要)**：

  • 1.7的时候，C对数组进行分割，锁只锁一部分数据，多线程访问不同数据段的数据，不存在锁竞争。1.8的时候摒弃分段的概念，直接采用Nod数组+链表+红黑树的数据结构，并发使用synchronized和CAS来操作。看起来就像是优化且线程安全的hashMap，虽然在1.8还能看到分割的数据结构，但是简化了属性。
  • T使用synchronized保证线程安全，效率低下，当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或者轮训状态，如果使用put添加元素，另一个线程就不能put，也不能get。

  DK1.8 的 ConcurrentHashMap 不在是 Segment 数组 + HashEntry 数组 + 链表，而是 Node 数组 + 链表 / 红黑树。不过，Node 只能用于链表的情况，红黑树的情况需要使用 **TreeNode**。当冲突链表达到一定长度时，链表会转换成红黑树。

ConcurrentHashMap线程安全的具体实现方式

JDK1.7

数据分段，每段加锁，当一个线程占用锁访问数据时，其他的数据可以被其他线程访问。

SegMent实现了ReentranLock，所以是一种可重入锁，扮演锁的角色，HashEntry用于存储键值对数据。

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

JDK1.8

采用CAS和synchronized保证线程安全。数据结构是数组+链表/红黑树，超过8就转化为红黑树。

synchronized 只锁定当前链表或红黑二叉树的首节点，这样只要 hash 不冲突，就不会产生并发，效率又提升 N 倍。

hashSet、LinkedHashSet和treeSet三者异同

HashSet 是 Set 接口的主要实现类 ，HashSet 的底层是 HashMap，线程不安全的，可以存储 null 值；

LinkedHashSet 是 HashSet 的子类，能够按照添加的顺序遍历；

TreeSet 底层使用红黑树，能够按照添加元素的顺序进行遍历，排序的方式有自然排序和定制排序。

底层数据结构总结

Collection

• List
  • ArrayList：Object[]数组
  • Vector：Object[]数组
  • LinkedList：双向链表
• Set
  • hashSet：基于hashMap实现，底层采用hashMap来保存元素。
  • LinkedHashSet：LinkedHashSet 是 HashSet 的子类，并且其内部是通过 LinkedHashMap 来实现的。有点类似于我们之前说的 LinkedHashMap 其内部是基于 HashMap 实现一样，不过还是有一点点区别的
  • TreeSet（有序，唯一）： 红黑树(自平衡的排序二叉树)

Map

• HashMap： JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间
• LinkedHashMap： LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。
• Hashtable： 数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的
• TreeMap： 红黑树（自平衡的排序二叉树）

如何选用

根据特点，比如我们需要根据键值获取到元素值时就选用 Map 接口下的集合，需要排序时选择 TreeMap,不需要排序时就选择 HashMap,需要保证线程安全就选用 ConcurrentHashMap。

当我们只需要存放元素值时，就选择实现Collection 接口的集合，需要保证元素唯一时选择实现 Set 接口的集合比如 TreeSet 或 HashSet，不需要就选择实现 List 接口的比如 ArrayList 或 LinkedList，然后再根据实现这些接口的集合的特点来选用。