集合 - 图1

集合（容器）是个接口

结构特点

  1. **List**和**Set**是存储单列数据的集合，**Map**是存储键值对这样的双列数据的集合；
    1. **List**中存储的数据是有顺序的，并且值允许重复；
    2. **Map**中存储的数据是无序的，它的key是不允许重复的，但是value是允许重复的；
    3. **Set**中存储的数据是**无顺序**的，并且**不允许重复**，但元素在集合中的位置是由元素的hashcode决定，即位置是固定的（Set集合是根据hashcode来进行数据存储的，所以位置是固定的，但是这个位置不是用户可以控制的，所以对于用户来说set中的元素还是无序的）。

1.List

ArrayList 和 LinkedList的异同

  1. ArrayList：
    1. List的主要实现类
    2. 线程不安全，效率高
    3. 底层使用Object [] elementDate数组
  2. 关于ArrayList的源码分析：
    1. JDK1.7：
      1. 创建实例的时候，开辟了一个空间大小为10的数组，
      2. 添加元素的时候，如果容器不够，则会扩容，默认情况下，扩容那为原来的1.5倍（右移一位，+原来的长度）。同时将原来的数组复制过去，
    2. JDK1.8
      1. 创建实例没有创建数组，第一次指向add（）方法时，底层创建了个数组，长度为10。
  3. LinkList：
    1. 底层使用双向链表存储数据，对于频繁的插入和删除，效率高
  4. Vector：
    1. 线程安全，效率低，底层使用数组。

2 Set

HashSet

存储无序（根据每个元素的hashCode来决定），不可重复的元素（按照equals()方法来判断）。
HashSet实现了Set接口，它不允许集合中有重复的值，当我们提到HashSet时，第一件事情就是在将对象存储在HashSet之前，要先确保对象重写equals()和hashCode()方法，这样才能比较对象的值是否相等，以确保set中没有储存相等的对象。

LinkedSet

..

TreeSet

…

3.Map

说说 HashTable 和 HashMap

  • 他们都是Map接口的实现类，HashMap作为主要实现类，线程不够安全，但是效率高，而hashtable是古老的实现类，线程安全，但是效率不够高。
  • HashMap是非synchronized，而Hashtable是synchronized，这意味着Hashtable是线程安全的，多个线程可以共享一个Hashtable；而如果没有正确的同步的话，多个线程是不能共享HashMap的。Java 5提供了ConcurrentHashMap，它是HashTable的替代，比HashTable的扩展性更好。
  • HashMap允许将null作为一个entry的key或者value，而Hashtable不允许。

    说说HashMap的底层原理

    以 JDK8来说明：
  1. 第一次创建实例的时候，底层没有创建长度为16的数组，第一次调用put（）方法的时候，开辟空间。
  2. 调用put（key1，value）方法的时候：
    1. key1的所在类的hashcode（）会计算key1的哈希值，此哈希值通过某种算法后，得到Entry数组存放的位置
    2. if 该位置没有元素
      1. entry添加成功
    3. if（）有元素（ 存在一个或者多个元素 ‘s’）
      1. 比较key1 和 s 的 hash值
      2. if （key1 的hash值 ≠ ‘s’的哈希值）
        1. 添加成功 以链表方式存储的
      3. if（ = ）
        1. 调用key1 的equals（）方法，判断
          1. 相同，覆盖，用新的value 覆盖 ‘s’的value。
          2. 不i同，添加成功 以链表方式存储的
    4. image.png

1.关于扩容

  • 默认扩容方式为原来的2倍，并且将原来的数据复制过来。
  • 当超出临界值（默认加载因子（0.75）* 数组长度） && 存放的位置为非空时候，扩容。

    问题1：数组容量的大小为什么要取2的指数幂？

  1. 通过 key的hashcode 和数组长度 -1 进行与运算。 ：（n-1）&hash 得到存储的位置。
  2. n-1 的二进制（n为2 的指数幂） 值 的特征为 左0 右1 ，这样能保证 与运算后， 相应的位数既可能是0 ，有可能是1，取决于hashcode 的值，就保证了散列的均匀，同时运算效率高。
  3. 可以便于动态扩容后，重新计算的哈希值能均匀分布元素：
    1. 动态扩容按照2的指数幂：
      1. 即按位与操作的值的变化：二进制高位+1 ，比如 16—>32，0000 1111 -> 0001 1111
      2. 因此这种变化，会使得要扩容的元素的哈希值重新按位与操作后，所得的下标要么不变，要么+16（扩容后的一半）。这样灰灰使得原本一个链表上的元素，均匀分布到新的hash表中。

        问题2：Hash Map中的hash（）方法中，调用key . hashcode（）方法后，为什么还进行对hash值右移和异或运算。

  • 使hash值的二进制中的高位尽可能 多的参与 按位与操作， 为了减少哈希冲突。

    Q 3：底层结构

    hashMap 的底层结构为：数组+ 链表+红黑树

    • 某个索引位置上的数据个数 > 8 且数组长度为64 以上 ，链表改为红黑树储存。
    • 对于移除，当同一个索引位置的节点在移除后达到 6 个，并且该索引位置的节点为红黑树节点，会触发红黑树节点转链表节点（untreeify）