java集合中list、set、map接口间的区别

参考链接： Java集合接口

集合框架 

集合是数据的容器，可以保存大量数据，集合的长度可以自动扩展。 

collection 接口list接口元素是有顺序的，元素可以重复因为每个元素有自己的角标（索引）set接口元素是无序的，且不可以重复（存入和取出的顺序不一定一致），线程不同步，数据不能单独访问。 

map接口这个集合是存储键值对的，一对一对往里存，而且要确保键的唯一性（键不能重复）

List接口 

LinkedList类： 底层使用的是链表数据结构，特点是：增 删很快，查询慢(LinkedList中的get方法是要依照顺序从列表的一端開始检查，直到另一端)。 

 不要使用常规的for循环遍历linkedList 

ArrayList类： 底层的数据结构是数组结构，特点是：查询很快，增 删 稍微慢点(由于ArrayList要移动数据)，线程不同步，在 Java1.2 版本引入的。 

 数据的扩容：ArrayList默认添加原来的0.5倍，ArrayList没有提供相关的方法来让我们自己设置增长的大小。 

Vector类： 底层是数组数据结构，线程同步，被ArrayList代替了，现在用的只有他的枚举,在 Java1.0 版本引入的。 

 数据的扩容：Vector默认添加原来的一倍，能够由我们自己来设置增长的大小。 

。 

Set接口 

HashSet类：底层是哈希表数据结构。根据hashCode和equals方法来确定元素的唯一性。TreeSet类：可以对Set集合中的元素进行排序（自然循序），底层的数据结构是二叉树,也可以自己写个类实现Comparable 或者 Comparator 接口，定义自己的比较器，将其作为参数传递给TreeSet的构造函数。LinkedHashSet类:能保留数据的原始添加顺序。 

map接口 

HashTable类：底层是哈希表数据结构，不可以存入null键和null值，该集合线程是同步的，效率比较低。出现于JDK1.0。 

 从Hashtable示例的源码可以看出，Hashtable是用synchronized关键字来保证线程安全的，由于synchronized的机制是在同一时刻只能有一个线程操作，其他的线程阻塞或者轮询等待，在线程竞争激烈的情况下，这种方式的效率会非常的低下。 Hashtable的扩容 ：newSize = 2 * oldSize + 1 

HashMap类：底层是哈希表数据结构，可以存入null键和null值，线程不同步，效率较高，代替了HashTable，出现于JDK 1.2。 

 我想线程安全，但是我又想效率高怎么办？ 

 jdk1.5之后，推出了ConcurrentHashMap,通过把整个Map分为N个Segment（类似于HashTable）,可以提供相同的线程安全，但是效率提高N倍，默认提升16倍。 

HashMap线程不安全，它的线程不安全主要发生在put等对HashEntry有直接写操作的地方:

从put操作的源码不难看出，线程不安全主要可能发生在这两个地方：

key已经存在，需要修改HashEntry对应的value； key不存在，在HashEntry中做插入。

TreeMap类:底层是二叉树数据结构，线程不同步，可以用于个map集合中的键进行排序。LinkHashMap类：能保留键的原始添加顺序。 

HashMap是如何添加\查找数据的： 

添加： 1、通过键的hashCode计算出数组的下标 2、通过下标找到该位置，如果该位置上数据为null，就把数据存入该位置的节点 3、如果该位置数据不为null，调用键的equals方法和该节点的键比较 4、如果equals返回为true，将新的数据覆盖原有数据 5、如果equals返回为false，就和下一个节点比较，最后把数据放到链表末尾。 查找： 1、通过键的hashCode计算出数组的下标 2、如果该位置有值，就调用equals进行比较 3、equals为true，返回数据的值 4、如果为false，就在链表依次往后查找，直到找到为止 

HashTable和ConcurrentHashMap的区别； 

HashTable容器使用synchronized来保证线程安全，但在线程竞争激烈的情况下HashTable的效率非常低下。 因为当一个线程访问HashTable的同步方法时，其他线程访问HashTable的同步方法时，可能会进入阻塞或轮询状态。 如线程1使用put进行添加元素，线程2不但不能使用put方法添加元素，并且也不能使用get方法来获取元素，所以竞争越激烈效率越低 

ConcurrentHashMap使用的锁分段技术，首先将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问 

HashMap的底层实现，以及ConcurrentHashMap的底层实现； 

在Java编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，HashMap也不例外。 HashMap实际上是一个“链表的数组”的数据结构，每个元素存放链表头结点的数组，即数组和链表的结合体。HashMap底层就是一个数组，数组中的每一项又是一个链表。当新建一个HashMap的时候，就会初始化一个数组 ConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成。Segment是一种可重入锁ReentrantLock，在ConcurrentHashMap里扮演锁的角色，HashEntry则用于存储键值对数据。 一个ConcurrentHashMap里包含一个Segment数组，Segment的结构和HashMap类似，是一种数组和链表结构， 一个Segment里包含一个HashEntry数组， 每个HashEntry是一个链表结构的元素， 每个Segment守护者一个HashEntry数组里的元素,当对HashEntry数组的数据进行修改时，必须首先获得它对应的Segment锁。 

如何实现HashMap顺序存储：可以参考LinkedHashMap的底层实现； 

方法一： 维护一张表，存储数据插入的顺序，可以使用vector。但是如果删除数据呢，首先得在vector里面找到那个数据，再删除，而删除又要移动大量数据。性能效率很低。 使用list，移动问题可以解决，但是查找数据的O(n)时间消耗，如果删除m次，那查找数据的性能就是0（n*m)，那总体性能也是 O(n2)。性能还是没法接受。 

方法二： 可以在hashmap里面维护插入顺序的id, 在value建一个字段存储id值，再维护一张表vector，并且id对应vector里面的值。 插入的时候，id＋＝1， hashmap.insert，vector.push_back. 删除的时候，先hashmap.find(key), 得到value, 并从value中得到id, 通过id把对应vector值置为无效。 更新：删除＋插入。 维护工作OK了，输出的时候直接输出vector里面的值就可以了， 无效的就continue。 算法复杂度为O(n) 

方法三： Java里面有个容器LinkedHashMap, 它能实现按照插入的顺序输出结果。 它的原理也是维护一张表，但它是链表，并且hashmap中维护指向链表的指针，这样可以快速定位链表中的元素进行删除。 它的时间复杂度也是O(n), 空间上要比上面少些。 

 加波关注，不迷路！！感谢各位老铁们的帮助。