一 .概述

说明:

1.list接口和set接口继承自collection接口，Map是独立接口

2.List下有ArrayList，Vector，LinkedList

3.Set下有HashSet，LinkedHashSet，TreeSet

4.Map下有Hashtable，LinkedHashMap，HashMap，TreeMap

二 .List

存放有序，可重复元素

1.ArrayList

实现RandomAccess(标记接口)代表ArrayList是支持快速随机访问 ,实现Cloneable(标记接口)代表ArrayList是可以拷贝 ,实现Serializable(标记接口)代表ArrayList是可以序列化的

(1) ArrayList数组线性表的特点为:类似数组的形式进行存储，因此它的随机访问速度极快

(2) ArrayList数组线性表的缺点为:不适合于在线性表中间需要频繁进行插入和删除操作。因为每次插入和删除都需要移动数组中的元素

(3) 如果在初始化ArrayList的时候没有指定初始化长度的话，默认的长度为10

(4) ArrayList在增加新元素的时候如果超过了原始的容量的话，ArrayList扩容ensureCapacity方案为“原始容量*3/2"

(5) ArrayList是线程不安全的，在多线程的情况下不要使用,如果要在多线程下使用可以使vector，用法基本一致区别在于Vector中的绝大部分方法都使用了同步关键字修饰，这样在多线程的情况下不会出现并发错误 ArrayList是通过原始容量*3/2+1而Vector是允许设置默认的增长长度Vector的默认扩容方式为原来的2倍

(6) 在用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的内容进行了修改（增加、删除、修改），则会抛出ConcurrentModificationException；为了防止删除时出现这个问题，使用Iterator中的remove方法

2.LinkedList

继承了AbstractSequentialList，它可以被当作堆栈、队列或双端队列进行操作 ;实现 Deque 接口代表LinkedList可以当作双端队列使用 ;实现Cloneable(标记接口)代表LinkedList是可以拷贝实现Serializable(标记接口)代表LinkedList是可以序列化的

（1） LinkedList的链式线性表的特点为: 适合于在链表中间需要频繁进行插入和删除操作

（2） LinkedList的链式线性表的缺点为:随机访问速度较慢。查找一个元素需要从头开始一个一个的找

（3）是一种双向循环链表的链式线性表，只不过存储的结构使用的是链式表而已

（4） LinkedList的内部是基于双向循环链表的结构来实现的在LinkedList中有一个类似于c语言中结构体的Entry内部类

（5）在Entry的内部类中包含了前一个元素的地址引用和后一个元素的地址引用类似于c语言中指针

三 .Set

Set中的元素实现了不重复，有点象集合的概念，无序，不允许有重复的元素,最多允许有一个null元素对象

虽然Set中元素没有顺序，但是元素在set中的位置是有由该元素的HashCode决定的，其具体位置其实是固定的

Set中存储的值，其实就是Map中的key，它们都是不允许重复的

对象A和对象B，本来是不同的两个对象，正常情况下它们是能够放入到Set里面的，但是

如果对象A和B的都重写了hashcode和equals方法，并且重写后的hashcode和equals方法是相同的话。那么A和B是不能同时放入到Set集合中去的，也就是Set集合中的去重和hashcode与equals方法直接相关

1.Hashset

（1）底层数据结构是哈希表

（2） Hashset中允许出现一个null值

（3）由于HashSet底层是基于Hash算法实现的，使用了hashcode，所以HashSet中相应的元素的位置是固定的

（4）线程不安全

2 .LinkHashSet

（1）底层数据结构是链表和哈希表，由链表保证元素有序，由哈希表保证元素唯一

（2）线程不安全

3.TreeSet

（1）线程不安全

（2）底层数据结构是红黑树。(唯一，有序)

（3）当向TreeSet中添加自定义的对象时，有两种排序:自然排序定制排序

（4）向TreeSet中添加元素时，首先按照compareTo()进行比较，一旦返回0，虽然仅是两个对象的此属性值相同，但是程序会认为这两个对象是相同的，进而后一个对象就不能添加进来

四 .Map

1.HashMap

(1) 允许key为null，也允许value为null

(2) Hash表是一个数组+链表的结构这种结构能够保证在遍历与增删的过程中，如果不产生hash碰撞，仅需一次定位就可完成但是如果散列表中的hash碰撞过多时当一个hash值上的链表长度大于8时，该节点上的数据就不再以链表进行存储，而是转成了一个红黑树。

(3) hash碰撞两个元素通过hash函数计算出的值是一样的，是同一个存储地址当后面的元素要插入到这个地址时，发现已经被占用了这时候就产生了hash冲突

一些初始化的值

构造方法

（4）hashMap的put方法实现思路：

1.table[]是否为空

2.判断table[i]处是否插入过值

3.判断链表长度是否大于8，如果大于就转换为红黑二叉树，并插入树中

4.判断key是否和原有key相同，如果相同就覆盖原有key的value，并返回原有value

5.如果key不相同，就插入一个key，记录结构变化一次

（5）hashMap的get方法的实现思路：

1.判断表或key是否是null，如果是直接返回null

2.判断索引处第一个key与传入key是否相等，如果相等直接返回

3.如果不相等，判断链表是否是红黑二叉树，如果是，直接从树中取值

4.如果不是树，就遍历链表查找

五 .集合的遍历

1.list的遍历

方法1

方法2

2.Map的遍历

方法1

方法2

方法3

方法4

java集合