java--ArrayList、LinkedList、HashSet、HashMap、Hashtable、Collection、Collections详解

ArrayList是List接口的实现类，一种大小可变数组，随着元素的增多，容量会自动扩充，默认初始容量值是10，也可以自己指定初始容量

采用的数据结构：数组
（线性表：数组、链表、队列、栈
非线性表：二叉树、堆、图等）

ArrayList优点：
查询速度快
ArrayList缺点：
新增和删除元素比较慢

查询速度快的原因：
ArrayList底层是数组实现的，根据下标查询，不需要比较，查询方式为，首地址+（元素长度＊下标），基于这个位置读取相应的字节数，所以非常快；

新增和删除慢的原因：
增删会带来元素的移动，增加数据会向后移动，删除数据会向前移动，所以影响效率

适用场景：
如果应用程序对数据有较多的随机访问使用ArrayList较好

2.LinkedList

LinkedList也是List接口的实现类,和ArrayList功能类似，但LinkedList新增几个功能 ，如addFirst(),addLast(),getFirst(),getLast()等

数据结构：双向链表

链式存储，在内存中不是连续存储的，每个元素存储包括三部分，前一个元素的内存地址、数据部分、后一个元素内存地址，因此在进行元素的新增和删除时效率比较高，但查询时比较慢
链式存储方式与数组的连续存储方式相比，其实对内存的利用率更高

3.HashSet

HashSet是Set接口的实现类，最大的特点就是内部元素无序、并且不能重复（重复添加的话调用add()方法会返回false，添加失败），默认初始容量16

HashSet数据结构：哈希表（数组+链表）

HashSet存储原理：

Set set=new HashSet();
set.add(object);

存储过程为:
定义x=object.hashCode,得到obj对象的哈希码x，再对x进行hash散列运算，对数组长度进行求余，假如长度为20，则返回一个0-19之间的值，然后这个值就是存在HashSet数组中的下标。如果下标位置没有对象，则把object加到该位置；如果已有对象，则用equals判断两对象是否相等，相等则舍弃object，不相等，则把object以链表的方式加在该对象下面

原则1：让equals相等的对象返回相同的hashCode（为了过滤掉相等的元素）
原则2：尽量保证equals不相同的对象返回不同的hashCode（为了添加不同的元素）
存储过程图解如下：

HashSet的add()方法底层使用的是HashMap的存储方式，看源码可以知道

add()方法

4.HashMap

map是存放键值对的。
HashMap是Map接口的实现类，也是采用了hash算法。

其实向HashSet中放值，就是向HashMap中放值

Key不可以一样，如果key一样，在内存中存储的位置相同，后一个会把前一个key覆盖，value可以一样
key和value均可以为null
HashMap的存储键的过程和HashSet一样，不过HashMap在根据key获取value时的原理如下：
前面也是根据对象获取哈希码，进行哈希运算求下标（哈希码%容量），如果下标位置只有一对key-value,就直接取得value，如果有多个key-value键值对，然后再根据key获取value。

HashMap的数据结构
数组+单链表（数组中的每个元素都是单链表的头节点）
使用链表的原因是解决哈希冲突的（即不同的key映射到了数组的同一位置处，就将其放入单链表中）

ConcurrentHashMap

HashMap是线程不安全的
Hashtable是HashMap的兄弟。HashMap跟HashTable用法基本一样

它们两个区别就是HashTable是线程安全的

线程安全：
10个人同时操作HashTable，只有一个人操作，剩下的九个人等待。操作完毕后，剩下的9个人中的一个人操作HashTable,剩下8个人等待

线程不安全：
10个人同时操作

例子： 第一个人拿原始值， 如10
第二个人修改原始值 10-》20

如果二个人修改了原始值，会造成后面的人再拿数据时，会拿到第二个人修改后的数据（脏数据）

5.Hashtable

Hashtable和HashMap功能类似，都是用来保存键值对，但两者之间又有区别
区别：
1.Hashtable中不允许保存null的，而HashMap可以保存空的null和value
2…Hashtable线程安全
HashMap线程不安全
3.Hashtable继承自Dictionary类，而HashMap继承自AbstractMap类。但二者都实现了Map接口

6.Collection

collection是list和set接口的父接口，是一个集合接口

7.Collections

Collections 是一个包装类。它包含有各种有关集合操作的静态多态方法。此类不能实例化，就像一个工具类
常用方法如下：
Collections.sort()
Collections.reverse()
Collections.binarySearch()方法
为二分法查找，所以数组必须是有序的或者是用sort()方法排序之后的。
binarySearch(Object[], Object key)
方法的object[]参数是要查找的数组，key参数为要查找的key值。