集合

1. 常见数据结构

• 数组

最常见的数据结构，长度固定，无法扩容，只能存储一种类型数据，新增、删除慢，因为要移动其他数据。

• 栈

先进后出的数据结构，只能在一端操作的特殊线性表，先入栈的数据后执行，后入栈的数据先执行。

• 队列

先进先出的数据结构，只能在一端进行插入，另一端进行删除的特殊线性表，先进入的数据会被先读取。

• 链表

链表是一种物理存储单元上非连续、非顺序的存储结构，其物理结构不能只表示数据元素的逻辑顺序，是由链表中的指针链接次序来实现的；链表是由一系列结点组成，结点可以在运行时动态生成，根据指针的指向，链表能生成不同的结构，如单链表、双向链表、循环列表等。

• 树

是计算机中非常重要的一种数据结构，能描述家谱、单位组织架构等等；有二叉树、平衡树、红黑树、B 树、B+ 树。

• 散列

也称哈希，根据键和值直接访问的数据结构。

• 堆

通常可以被看作是一棵完全二叉树的数组对象。

• 图

由一顶点和一组能将两个顶点相连的边组成。

2. 集合和数组的区别

• 数组长度固定；集合长度可变。
• 数组只能存储一种类型数据；集合能存储对象。

3. List、Map、Set区别

List 和 Set 是存储单列数据集合；Map 是存储键值这样双列数据集合。

• List 有序，值可重复
• Map 无序，键不允许重复，值可以重复
• Set 无序，不可重复，元素位置由元素的 hashcode 决定

4. 集合实现类

Collection 接口

• List

• • ArrayList
  • 底层结构是数组，查询块，增删慢，线程不安全，效率高。 
  • Vector（已舍弃）
  • 底层结构是数组，查询快，增删慢，线程安全，效率低。 
  • LinkedList
  •  底层结构是链表，查询慢，增删块，线程不安全，效率高。
• Set

• • HashSet
  • 底层数据结构是哈希表，无序，不可重复，通过 hashCode() 和 equals() 保证元素唯一 。
  • LinkedHashSet
  • 底层数据结构是链表和哈希表，有序，不可重复，通过链表实现有序，哈希表实现唯一。 
  • TreeSet
  • 底层数据结构是红黑树，有序，不可重复，通过自然排序、比较器排序，再根据比较返回值是否为 0 来实现唯一。 

• Map

• • HashMap
  • 基于 hash 表的 Map 接口实现，键和值允许为 null ，线程不安全，效率高。 
  • HashTable
  • 键和值不允许为  null， 线程安全，效率低。
  • LinkedHashMap
  • 是 HashMap 一个子类，有序，线程安全，效率低。 
  • TreeMap
  •  默认按键值升序排序，线程不安全，效率高。

5. HashMap 底层原理

JDK 1.8 之前由数组 + 链表组成，之后由数组 + 链表 + 红黑树组成，提高了查询效率，当链表长度超过 8 自动转为红黑树，小于 6 自动转为链表。

当 new HashMap() 底层没有创建数组，首次调用 put() 方法时，底层会创建长度为 16 的数组，JDK 8 底层数组是 Node[] 而非 Entry[]，用数组容量大小乘以加载因子得到一个值，一旦数组元素个数超过该值就会调用 rehash() 将数组容量扩大 2 倍，称为扩容；扩容时会生成一个新数组，需要将原来数组元素重新计算 hash 值放入新数组中，非常消耗性能。

HashMap 默认长度为 16，加载因子默认 0.75，当长度超过 12 自动扩容。

Java 中任何对象都有哈希值，哈希算法就是通过哈希值与自己行向右位移 16 的异或运算，是为了计算出来的值足够随机，足够分散，产生的数组下标足够随机。

put 原理

首先将键和值封装到 Node 对象中，调用键的 hashCode() 方法获取哈希值，并通过哈希算法转化成数组下标，下标位置如果没有元素，就把 Node 对象添加到这个位置，如果存在元素，就用键与节点上键进行 equals()，如果返回 false 就将 Node 对象添加到链表末尾，如果返回  ture 就将此节点值覆盖。

get 原理

首先调用键的 hashCode() 方法获取哈希值，通过哈希算法转换成数组下标，下标位置如果没有元素直接返回 null，如果存在元素，就用键与节点上的键进行 equals()，如果返回 false 直接返回 null，如果返回 true 就将此节点值取出返回。

6. HashMap 与 HashTable 区别

• HashMap 线程不安全；HashTable 线程安全。
• HashMap 允许键值为 null；HashTable 不允许。
• HashMap 效率比 HashTable 高。
• HashTable 是同步的。

HashTable 是遗留类，内部实现很多没优化和冗余，即使在多线程环境下，有同步的 ConcurrentHashMap 替代。

7. HashTable 与 ConcurrentHashMap 区别

HashTable 使用 Synchronized 关键字修饰；ConcurrentHashMap 在 JDK 1.7 使用分段锁保证线程安全，JDK 1.8 取消了 Segment 分段锁，使用 CAS 和 Synchronized 保证并发线程安全，数据结构为数组 + 链表 + 红黑树。

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