容器

底层数据结构
Collection

List：（有序，可重复）

  • ArrayList：Object数组
  • Vector： Object数组
  • LinkedList：双向链表（JDK1.6之前为循环链表，JDK1.7取消了循环），更擅长进行插入、删除、修改等操作

Set：

  • HashSet（无序，唯一）：基于HashMap实现的，底层采用HashMap来保存元素
  • LinkedHashSet：LinkedHashSet继承于HashSet，并且其内部是通过LinkedHashMap来实现的。
  • TreeSet（有序，唯一）：红黑树（自平衡的排序二叉树）。

唯一性:是要靠元素重写HashCode()和equals()方法,如果不重写则无法保证元素唯一

Map
  • HashMap：JDK1.8之前HashMap是由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解哈希冲突而存在的（“拉链法”解决哈希冲突）。JDK1.8之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）并且数组长度大于64时，将链表转化为红黑树，以减少搜索时间

注意：如果链表长度大于阈值（默认为8）时并且数组的长度小于64时，链表不会转换为红黑树，而是将数组进行扩容。这样做的目的考虑到数组的长度较小，尽量避开红黑树，这种情况下，转为红黑树，反而会降低效率问题，因为红黑树需要左旋，右旋，变色操作来保持平衡，所以当数组长度小于64，搜索时间会相对快些，考虑到性能和减少搜索的时间，只有当链表长度大于阈值（默认为8）时并且数组的长度大于64时，链表将会转换为红黑树。

  • LinkedHashMap：LinkedHashMap继承自HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap在上面结构的基础上，增加一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。
  • TreeMap：红黑树（自平衡的排序二叉树）。
  • Hashtable：数组+链表组成的，数组是Hashtable的主体，链表则是主要为了解决哈希冲突而存在的
扩容机制
ArrayList

以无参构造方法创建ArrayList时，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为10。

  /**
   * Default initial capacity.
   */
   private static final int DEFAULT_CAPACITY = 10;

   /**
    * Shared empty array instance used for empty instances.
    */
   private static final Object[] EMPTY_ELEMENTDATA = {};

因为在源代码中，int newCapacity = oldCapacity + (oldCapacity >> 1)，所以ArrayList每次扩容之后容量都会变为原来的1.5倍。

  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);
    }

ArrayList扩容的核心方法grow( )，下面将针对三种情况对该方法进行解析：

  1. 当前数组是由默认构造方法生成的空数组并且第一次添加数据。此时minCapacity等于默认的容量（10）那么根据下面逻辑可以看到最后数组的容量会从0扩容成10。而后的数组扩容才是按照当前容量的1.5倍进行扩容；

  2. 当前数组是由自定义初始容量构造方法创建并且指定初始容量为0。此时minCapacity等于1那么根据下面逻辑可以看到最后数组的容量会从0变成1。这边可以看到一个严重的问题，一旦我们执行了初始容量为0，那么根据下面的算法前四次扩容每次都 +1，在第5次添加数据进行扩容的时候才是按照当前容量的1.5倍进行扩容。

  3. 当扩容量（newCapacity）大于ArrayList数组定义的最大值后会调用hugeCapacity来进行判断。如果minCapacity已经大于Integer的最大值（溢出为负数）那么抛出OutOfMemoryError（内存溢出）否则的话根据与MAX_ARRAY_SIZE的比较情况确定是返回Integer最大值还是MAX_ARRAY_SIZE。这边也可以看到1. ArrayList允许的最大容量就是Integer的最大值（-2的31次方~2的31次方减1）。

  private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
HashMap

  • capacity 即容量，默认16。

  • loadFactor 加载因子，默认是0.75

  • threshold 阈值。阈值=容量*加载因子。默认12。当元素数量超过阈值时便会触发扩容。

什么时候触发扩容？

一般情况下，当元素数量超过阈值时便会触发扩容。每次扩容的容量都是之前容量的2倍。

HashMap的容量是有上限的，必须小于2^30，即1073741824。如果容量超出了这个数，则不再增长，且阈值会被设置为Integer.MAX_VALUE（ [图片上传失败...(image-44e830-1602040324581)]

，即永远不会超出阈值了）。

JDK8的扩容机制

JDK8的扩容做了许多调整。

HashMap的容量变化通常存在以下几种情况：

  1. 空参数的构造函数：实例化的HashMap默认内部数组是null，即没有实例化。第一次调用put方法时，则会开始第一次初始化扩容，长度为16。

  2. 有参构造函数：用于指定容量。会根据指定的正整数找到不小于指定容量的2的幂数，将这个数设置赋值给阈值（threshold）。第一次调用put方法时，会将阈值赋值给容量，然后让阈值=容量×负载因子。（因此并不是我们手动指定了容量就一定不会触发扩容，当元素数量超过阈值后一样会扩容！！）

  3. 如果不是第一次扩容，则容量变为原来的2倍，阈值也变为原来的2倍。（容量和阈值都变为原来的2倍时，负载因子还是不变）

此外还有几个细节需要注意：

  • 首次put时，先会触发扩容（算是初始化），然后存入数据，然后判断是否需要扩容；

  • 不是首次put，则不再初始化，直接存入数据，然后判断是否需要扩容；

List集合的四种遍历方式
//(1)集合的迭代器遍历。
 Iterator<String> it=list.iterator();
 while (it.hasNext())
     System.out.println(it.next());

 System.out.println("===================");

 //(2)使用增强for循环遍历
 for (String ele:list)
     System.out.println(ele);

 System.out.println("===================");

 //(3)使用JDK1.8后的新技术，lambda表达式。
 list.forEach(e-> System.out.println(e));

 System.out.println("===================");

 //(4)for循环结合索引遍历

 for (int i = 0; i <list.size() ; i++) {
     System.out.print(list.get(i)+" ");
 }
 System.out.println();
ArrayList和LinkedList的区别是什么？为什么要用ArrayList取代Vector？
ArrayList与LinkedList的区别

  1. 是否保证线程安全：ArrayList和LinkedList都是不同步的，也就是不保证线程安全

  2. 底层数据结构：ArrayList底层使用的是Object数组；LinkedList底层使用的是双向链表数据结构（JDK1.6之前为循环链表，JDK1.7取消了循环。注意双向链表和双向循环链表的区别，下面有介绍到）

  3. 插入和删除是否受元素位置的影响：① ArrayList采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。比如：执行add(E e)方法的时候，ArrayList会默认在指定的元素追加到此列表的末尾，这种情况的时间复杂度就是O(1)。但是如果要在指定位置i插入和删除元素的话(add ( int index, E element))时间复杂度就是O(n-i)。因为在进行上述操作的时候集合中第i和第i个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。② LinkedList采用链表存储，所以对于add(E e)方法的插入，删除元素时间复杂度不受元素位置的影响，近似O(1)，如果是要在指定位置i插入和删除元素的话，(add ( int index, E element))时间复杂度近似为O(n)，因为需要先移动到指定位置再插入。

  4. 是否支持快速随机访问：LinkedList不支持高效的随机元素访问，而ArrayList支持。快速随机访问就是通过元素的序号快速获取元素对象（对应于get(int index) 方法）。

  5. 内存空间占用：ArrayList的空间浪费主要体现在 在list列表的结尾会预留一定的容量空间，而LinkedList的容量空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间（因为要存放直接后继和直接前驱以及数据）。

ArrayList取代Vector的原因

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

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

HashMap与Hashtable的区别

  1. 线程是否安全：HashMap是非线程安全的，Hashtable是线程安全的；Hashtable内部的方法基本都经过synchronized修饰。（如果一定要保证线程安全的话可以使用ConcurrentHash）；

  2. 效率：因为线程安全的问题，HashMap要比Hashtable效率高一点。另外，Hashtable基本被淘汰，不要在代码中使用它；

  3. 对 Null key 和 Null value 的支持：HashMap中，null可以作为键，这样的键只有一个，可以有一个或多个键所对应的值为null。但是在Hashtable中put进的键值只要有一个null，就直接抛出 NullPointerException。

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

  5. 底层数据结构：JDK1.8以后的HashMap在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为8）时，将链表转换为红黑树，以减少搜索时间。Hashtable没有这样的机制。

List、Set、Map三者的区别

  • List（有序、重复）：

    List接口存储一组不唯一（可以有多个元素引用相同的对象），有序的对象

  • Set（无序、不重复）：

    不允许重复的集合。不会有多个元素引用相同的对象。

  • Map（KV键值对集合）：

    使用键值对来存储。Map会维护与Key有关联的值。两个Key可以引用相同的对象。但Key不能重复，典型的Key是String类型，但也可以是任何对象。

RandomAccess接口
public interface RandomAccess {
}

通过查看源码可以发现实际上RandomAccess接口中什么都没有定义。所以我认为RandomAccess接口只是一个标识，标识实现这个接口的类具有随机访问功能。

在binarySearch( ) 方法中，它要判断传入的list是否为RandomAccess接口的实现类的实例，如果是，调用indexBinarySearch( )方法，如果不是，则调用iteratorBinarySearch( )方法。

public static <T>
    int binarySearch(List<? extends Comparable<? super T>> list, T key) {
        if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
            return Collections.indexedBinarySearch(list, key);
        else
            return Collections.iteratorBinarySearch(list, key);
}

ArrayList实现了RandomAccess接口，而LinkedList没有实现。是什么原因？

我认为还是与底层数据结构有关。ArrayList底层是数组，而LinkedList底层是链表。数组天然支持随机访问，时间复杂度为O(1)，所以称为快速随机访问。链表需要遍历到特定位置才能访问到特定位置的元素，时间复杂度为O(n)，所以不支持快速随机访问。ArrayList实现了RandomAccess接口，就表明了他具有快速随机访问功能。RandomAccess接口只是标识，并不是说ArrayList实现RandomAccess接口才具有快速随机访问功能的！

ConcurrentHashMap

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

当需要put元素的时候，并不是对整个hashmap进行加锁，而是先通过hashcode来知道他要放在那一个分段中，然后对这个分段进行加锁，所以当多线程put的时候，只要不是放在一个分段中，就实现了真正的并行的插入。

但是，在统计size的时候，可就是获取hashmap全局信息的时候，就需要获取所有的分段锁才能统计。

分段锁的设计目的是细化锁的粒度，当操作不需要更新整个数组的时候，就仅仅针对数组中的一项进行加锁操作。

举个直观一点的例子：

既然不能全锁（HashTable）又不能不锁（HashMap），所以就搞个部分锁，只锁部分，用到哪部分就锁哪部分。一个大仓库，里面有若干个隔间，每个隔间都有锁，同时只允许一个人进隔间存取东西。但是，在存取东西之前，需要有一个全局索引，告诉你要操作的资源在哪个隔间里，然后当你看到隔间空闲时，就可以进去存取，如果隔间正在占用，那你就得等着。

comparable 和 Comparator 的区别

  1. comparable 接口实际上是出自java.lang包 它有一个 compareTo(Object obj)方法用来排序

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

  2. Comparable是排序接口，若一个类实现了Comparable接口，就意味着“该类支持排序”。而Comparator是比较器，我们若需要控制某个类的次序，可以建立一个“该类的比较器”来进行排序。

  3. Comparable相当于“内部比较器”，而Comparator相当于“外部比较器”。

    两种方法各有优劣， 用Comparable 简单， 只要实现Comparable 接口的对象直接就成为一个可以比较的对象，但是需要修改源代码。 用Comparator 的好处是不需要修改源代码， 而是另外实现一个比较器， 当某个自定义的对象需要作比较的时候，把比较器和对象一起传递过去就可以比大小了， 并且在Comparator 里面用户可以自己实现复杂的可以通用的逻辑，使其可以匹配一些比较简单的对象，那样就可以节省很多重复劳动了（灵活，扩展性强）。

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。