ArrayList 详解

底层是数组，查询快增删慢，线程不安全，效率高。初始化长度10

说一下ArrayList底层实现方式？

①ArrayList通过数组实现，一旦我们实例化ArrayList无参数构造函数默认为数组初始化长度为10
②add方法底层实现如果增加的元素个数超过了10个，那么ArrayList底层会新生成一个数组，长度为原数组的1.5倍+1，然后将原数组的内容复制到新数组当中，并且后续增加的内容都会放到新数组当中。当新数组无法容纳增加的元素时，重复该过程。是一旦数组超出长度，就开始扩容数组。扩容数组调用的方法 Arrays.copyOf(objArr, objArr.length + 1);

结构图

https://blog.csdn.net/u013309870/article/details/72519272

image.png

public class ArrayList<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, Serializable

由上可知ArrayList继承AbstractList 并且实现了List和RandomAccess，Cloneable, Serializable接口。

ArrayList的方法使用和源码解析

①构造方法

//1-----------------------
public ArrayList() {
        this(10);
        //调用ArrayList(10) 默认初始化一个大小为10的object数组。
    }

//2-------------------------
public ArrayList(int initialCapacity) {    
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
         //如果用户初始化大小小于0抛异常，否则新建一个用户初始值大小的object数组。                                      
        this.elementData = new Object[initialCapacity];
    } 

//3--------------------------
public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        size = elementData.length;
        // 当c.toArray返回的不是object类型的数组时，进行下面转化。
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }

由上面三种构造方法可知，默认情况下使用ArrayList会生成一个大小为10的Object类型的数组。也可以调用ArrayList(int initialCapacity) 来初始化Object数组的大小。并且用户可以往ArrayList中传入一个容器只要这个容器是Collection类型的。调用ArrayList(Collection<? extends E> c)接口的时候会将容器数组化处理并将这个数组值赋给Object数组。
实例：

public static void main(String[] args) {
        ArrayList<Integer> list_2=new ArrayList<Integer>(20);
        //list_2中添加元素
        for(int i=0;i<10;i++)
            list_2.add(i);

        ArrayList<Integer> list_3=new ArrayList<Integer>(list_2);
        //输出list_2中元素
        for(Integer a:list_2)
            System.out.print(a+" ");
        //输出list_3中元素
        for(Integer a:list_3)
            System.out.print(a+" ");
    }
//输出
/*
list_2 : 0 1 2 3 4 5 6 7 8 9 
-----------------------
list_3 : 0 1 2 3 4 5 6 7 8 9 
*/

②indexOf(Object o)方法

功能：查找某个元素在ArrayList中第一次出现的位置。

public int indexOf(Object o) {
  //ArrayList中的元素可以为null，如果为null返回null的下标
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;

        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        //如果没有找到对应的元素返回-1。
        return -1;
    }

对于indexof方法做几点说明：ArrayList中可以存放null元素，indexof是返回elementData数组中值相同的首个元素的下标，indexof中比较方法是equals而equals是比较元素的值，因此必须对null单独查找。如果未找到该元素则返回-1 。

public static void main(String[] args) {

        ArrayList<Integer> list=new ArrayList<Integer>();

        list.add(1);        
        list.add(2);        
        list.add(null);     
        list.add(2);
        list.add(3);

        System.out.println("null: "+list.indexOf(null));
        System.out.println("-------------------------");
        System.out.println("2: "+list.indexOf(2));
        System.out.println("-------------------------");
        System.out.println("4: "+list.indexOf(4));
    }
    //输出
    /*
    null: 2
    -------------------------
    2: 1
    -------------------------
    4: -1
    */

③lastIndexOf(Object o)方法

功能：查找某个元素在ArrayList中最后出现的位置。

public int lastIndexOf(Object o) {
        if (o == null) {
        //如果o为null从后往前找到第一个为null的下标
            for (int i = size-1; i >= 0; i--)
                if (elementData[i]==null)
                    return i;
        } else {
        //从后往前找到第一个值为o的下标
            for (int i = size-1; i >= 0; i--)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

上面代码做几点说明：lastIndexOf(Object o)在ArrayList中从后往前找到第一个跟要查找值相同的元素的下标，因为是按值查找所以对于 null 要单独查找。如果未找到则返回-1；

④get(int index)方法

功能：返回ArrayList中指定下标为index的元素。

 //检查index的值是否大于ArrayList的大小
        rangeCheck(index);
 //返回index下标的元素       
        return elementData(index);
    }

   E elementData(int index) {
        return (E) elementData[index];
    }  
 //这里值检查index >= size的情况，因为index<0时会自动抛出异常，所以并未检查index<0的情况。
 private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }```
对上面代码做几点说明：上面代码中只检查了index>=size的情况，在index<0的情况下也会抛出异常，只是这个异常是由系统抛出的。index>=size要检查的原因是有可能数组的大小大于index，然而有效里面的元素<index这时不抛异常就会返回无效值。举个例子ArrayList的初始化大小为10，现在往里面放5个元素，如果index>=5时，应该要抛出异常，而不是返回 null。因为null 是可以主动放在ArrayList中的。

###⑤set(int index, E element)方法 
功能：将element放到ArrayList下标为index的位置，如果index<0或index>=size 抛异常，set(int index, E element)只能覆盖ArrayList中原来的元素，返回值为被覆盖的元素。
```//1
public E set(int index, E element) {
//检查index是否小于size，如果不是抛异常
        rangeCheck(index);
        E oldValue = elementData(index);
        elementData[index] = element;
        //覆盖ArrayList中index上的元素。
        return oldValue;
        //返回被覆盖的元素。
    }
//2    
 private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

⑥add(E e)方法

功能：往ArrayList中添加元素。

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // 加入元素前检查数组的容量是否足够
        elementData[size++] = e;
        return true;
    }
//2----------------------- 
private void ensureCapacityInternal(int minCapacity) {
        modCount++;
        // 如果添加元素后大于当前数组的长度，则进行扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    } 
//3-----------------------  
private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //将数组的长度增加原来数组的一半。
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
            //如果扩充一半后仍然不够，则 newCapacity = minCapacity;minCapacity实际元素的个数。
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
            //数组最大位2^32
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

add方法比较复杂，涉及到扩充数组容量的问题。其中要弄清楚size和elementData.length的区别，size指的是数组中存放元素的个数，elementData.length表示数组的长度，当new一个ArrayList系统默认产生一个长度为10的elementData数组，elementData.length=10，但是由于elementData中还未放任何元素所有size=0。如果加入元素后数组大小不够会先进行扩容，每次扩容都将数组大小增大一半比如数组大小为10一次扩容后的大小为10+5=10;ArrayList的最大长度为 2^32 .

⑦add(int index, E element)方法

功能：往ArrayList指定index上添加元素，添加元素后ArrayList的大小增1。index及以后的元素都会向后移一位。

public void add(int index, E element) {
        rangeCheckForAdd(index);
//检查index的值是否在0到size之间，可以为size。
        ensureCapacityInternal(size + 1);  // 看elementData的长度是否足够，不够扩容
 //将elementData从index开始后面的元素往后移一位。       
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }
//2-------------------------
private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
 //3-------------------------  
 private void ensureCapacityInternal(int minCapacity) {
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }```
add(int index, E element)往指定index中加入元素，加入元素之前先检查数组的大小，如果小了在原来基础上增大一半，将ArrayList只能怪index及以后的元素往后移一位，将element放到index位置。

###⑧remove(int index)方法 
功能：删除ArrayList指定位置的元素。

public E remove(int index) {
rangeCheck(index);
//如果index>=size抛出异常
modCount++;
E oldValue = elementData(index);
//获取删除元素的值
int numMoved = size - index - 1;
//将index后面所有的元素往前移一位。
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // Let gc do its work
//返回要删除的原数。
return oldValue;
}```

⑨remove(Object o)方法

功能：删除ArrayList中值为o的元素

        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

ArrayList和LinkedList的大致区别如下:

1.ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。
2.对于随机访问 ，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。
3.对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。

说一下LinkedList底层实现方式？

LinkedList底层的数据结构是基于双向循环链表的，且头结点中不存放数据,如下：

image.png

双向链表数据结构：称之为节点，节点实例保存业务数据，前一个节点的位置信息和后一个节点位置信息，如下图所示：

image.png

初始化长度

1.StringBuffer和StringBuilder初始化默认大小为16个字符
2.HashMap初始化默认大小16，自增为2n.
3.HashTable默认初始值为11，加载因子为0.75，自增为2n+1
4.ArrayList初始化默认值为10，自增为1.5n
5.Vector初始化默认值为10，自增为2n

ArrayList 和 Vector 的区别

这两个类都实现了 List 接口(List 接口继承了Collection 接口),他们都是有序集合,即存储在这两个集合中的元素的位置都是有顺序的,相当于一种动态的数组,我们以后可以按位置索引号取出某个元素,并且其中的数据是允许重复的,
ArrayList 与 Vector 的区别,这主要包括两个方面:.

(1)同步性:

Vector 是线程安全的,
ArrayList 是线程序不安全的。
单线程使用arraylist，多线程使用vector

(2)数据增长:

ArrayList初始化默认值为10，自增为1.5n
Vector初始化默认值为10，自增为2n

List 和Set、Map 区别?

Java中的集合包括三大类，它们是Set、List和Map，它们都处于java.util包中，Set、List和Map都是接口，它们有各自的实现类。Set的实现类主要有HashSet和TreeSet，List的实现类主要有ArrayList，Map的实现类主要有HashMap和TreeMap。
Set中的对象不按特定方式排序，并且没有重复对象。但它的有些实现类能对集合中的对象按特定方式排序，例如TreeSet类，它可以按照默认排序，也可以通过实现java.util.Comparator<Type>接口来自定义排序方式。
List中的对象按照索引位置排序，可以有重复对象，允许按照对象在集合中的索引位置检索对象，如通过list.get(i)方式来获得List集合中的元素。
Map中的每一个元素包含一个键对象和值对象，它们成对出现。键对象不能重复，值对象可以重复。

说一下HashMap底层实现方式？

HashMap是由数组+链表组成
put方法底层实现:
通过key的hash值%Entry[].length得到该存储的下标位置，如果多个key的hash值%Entry[].length值相同话就就会存储到该链表的后面。

Collection 和 Collections 的区别。

Collection是集合类的上级接口，继承于它的接口主要有Set和List。 Collections是针对集合类的一个帮助类，它提供了一系列静态方法实现了对各种集合的排序，搜索和线程安全等操作。

List、Map、Set 三个接口,存取元素时,各有什么特点?

• list：存储： 有序的 可重复的
  访问：可以for循环,foreach循环，iterator迭代器。

• set：存储：无序的 不重复的
  访问：可以foreach循环，iterator迭代器 迭代

• map：存储：存储的是一对一对的映射 ”key=value“，key值 是无序，不重复的。value值可重复
  访问：可以map中key值转为为set存储，然后迭代这个set，用map.get(key)获取value
  ,也可以转换为entry对象用迭代器迭代

HashMap 和 Hashtable 的区别

• hashmap:线程不安全,允许有null的键和值,效率高.HashMap是Hashtable的轻量级实现
  有containsvalue和containsKey方法,HashMap 是Java1.2 引进的Map interface 的一个实现

• hashtable:线程安全不允许有null的键和值,效率低.方法是Synchronize的.有contains方法 、Hashtable 继承于Dictionary 类.

  
  
  image.png

HashMap，HashTable，ConcurrentHashMap的区别。

http://www.cnblogs.com/skywang12345/p/3310835.html

HashMap简介

HashMap 是一个散列表，它存储的内容是键值对(key-value)映射。
HashMap 继承于AbstractMap，实现了Map、Cloneable、java.io.Serializable接口。
HashMap 的实现不是同步的，这意味着它不是线程安全的。它的key、value都可以为null。此外，HashMap中的映射不是有序的。

HashMap 的实例有两个参数影响其性能：“初始容量10” 和 “加载因子0.75”。容量 是哈希表中桶的数量，初始容量 只是哈希表在创建时的容量。加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。
通常，默认加载因子是 0.75, 这是在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查询成本（在大多数 HashMap 类的操作中，包括 get 和 put 操作，都反映了这一点）。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地减少 rehash 操作次数。如果初始容量大于最大条目数除以加载因子，则不会发生 rehash 操作。

去掉一个 Vector 集合中重复的元素

通过Vector.contains（）方法判断是否包含该元素，如果没有包含就添加到新的集合当中，适用于数据较小的情况下。

Set 里的元素是不能重复的.

set里的元素是不能重复的，用iterator()方法来区分重复与否。

HashMap的工作原理

HashMap基于hashing原理，我们通过put()和get()方法储存和获取对象。当我们将键值对传递给put()方法时，它调用键对象的hashCode()方法来计算hashcode，让后找到bucket位置来储存值对象。当获取对象时，通过键对象的equals()方法找到正确的键值对，然后返回值对象。HashMap使用链表来解决碰撞问题，当发生碰撞了，对象将会储存在链表的下一个节点中。 HashMap在每个链表节点中储存键值对对象。
当两个不同的键对象的hashcode相同时会发生什么？ 它们会储存在同一个bucket位置的链表中。键对象的equals()方法用来找到键值对。
因为HashMap的好处非常多，我曾经在电子商务的应用中使用HashMap作为缓存。因为金融领域非常多的运用Java，也出于性能的考虑，我们会经常用到HashMap和ConcurrentHashMap。你可以查看更多的关于HashMap的文章:

说一下什么是哈希表

那么我们能不能综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构？答案是肯定的，这就是我们要提起的哈希表。哈希表（(Hash table）既满足了数据的查找方便，同时不占用太多的内容空间，使用也十分方便。
　　哈希表有多种不同的实现方法，我接下来解释的是最常用的一种方法—— 拉链法，我们可以理解为“链表的数组” ，如图：

image.png

image.png

请说下Iterator的作用

迭代器可以实现Collection接口的方法，可以一个一个地获取集合中的元素
在遍历集合时 可判断是否有下一个元素

说下ArrayList和LinkedList的区别和联系，并说明什么情况下用它们

区别:ArrayList用于对象的随机访问速度快,没有顺序
LinkedList实现机制是链表式的,和顺序有关,速度比ArrayList慢
联系:ArrayList和LinkedList都是List接口的实现类
当要快速获取一个值时,用ArrayList,用于顺序插入操作时,用LinkedList.

说下List，Set，Map三种集合各有什么特征

List集合中的元素可以重复,
Set集合中的元素不可以重复
Map集合用键-值映射存放对象,Map容器中的键对象不能重复,值对象可以重复

HashSet和TreeSet有什么区别，什么时候用它们

区别:HashSet中的元素不能重复,没有顺序
TreeSet中的元素不能重复,但有顺序
排序使用TreeSet，不排序使用HashSet，效率比排序快。

HaspMap扩容是怎样扩容的

HashMap中的变量
首先要了解HashMap的扩容过程，我们就得了解一些HashMap中的变量：
Node<K,V>：链表节点，包含了key、value、hash、next指针四个元素
table：Node<K,V>类型的数组，里面的元素是链表，用于存放HashMap元素的实体
size：记录了放入HashMap的元素个数
loadFactor：负载因子
threshold：阈值，决定了HashMap何时扩容，以及扩容后的大小，一般等于table大小乘以loadFactor

• 定义初始容量大小（table数组的大小，缺省值为16），定义负载因子（缺省值为0.75）的形式

HaspMap扩容是怎样扩容的，为什么都是2的N次幂的大小。

• 定义初始容量大小（table数组的大小，缺省值为16），定义负载因子（缺省值为0.75）的形式
  有几个重要的常量：

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;//默认的桶数组大小
static final int MAXIMUM_CAPACITY = 1 << 30;//极限值（超过这个值就将threshold修改为Integer.MAX_VALUE（此时桶大小已经是2的31次方了），表明不进行扩容了）
static final float DEFAULT_LOAD_FACTOR = 0.75f;//负载因子（请阅读下面体会这个值的用处）

https://blog.csdn.net/gaopu12345/article/details/50831631地址

HashMap与LinkedHashMap,和TreeMap的区别。

共同点：HashMap,LinkedHashMap,TreeMap都属于Map的实现类.
不同点: 1.HashMap里面存入的键值对在取出的时候是随机的,
2.TreeMap取出来的是排序后的键值对。但如果您要按自然顺序或自定义顺序遍历键，那么TreeMap会更好。
3.LinkedHashMap 是HashMap的一个子类，如果需要输出的顺序和输入的相同,那么用LinkedHashMap可以实现.

什么是for each循环，它可以循环那些数据类型

也可以叫增强型循环，通过对象拿到集合里的值，因为扩展性比较强，建议多使用，可以用来循环集合和数组

什么是泛型，怎么使用的，有什么好处？

定义一个集合时，可以知道里面定义的是什么类型
使用:在集合类型后面加< 数据类型 >

• 使用泛型后,从集合中取得元素后就不用再用强转

比较下集合和数组的优缺点

• 集合：是多个对象的容器,可以将不同数据类型的多个对象组织在一起
• 数组：是有相同数据类型的数据集合,数组是很多语言都支持的底层数据结构,性能上是最高的

在List里面怎么去掉重复的数？

通过把List里面的数据放入HashSet可以去除重复

HashMap和ArrayList是不是都是线程不安全的？

ArrayList是线程不安全的；
HashMap是线程不安全的；
还有我们常见的一些JAVA集合都是线程不安全,这样做是为了提高性能在JDK5以后提供了线程安全的并发包java.util.concurrent并发包,譬如里面的类CopyOnWriteArrayList,
CopyOnWriteArraySet,ConcurrentHashMap等

ArrayList集合加入1万条数据，应该怎么提高效率

因为ArrayList的底层是数组实现,并且数组的默认值是10,如果插入10000条要不断的扩容,耗费时间,所以我们调用ArrayList的指定容量的构造器方法ArrayList(int size) 就可以实现不扩容,就提高了性能