Set接口

HashSet：线程不安全，存取速度快

　　　　　底层实现是一个HashMap（保存数据），实现Set接口

　　　　　默认初始容量为16（为何是16，见下方对HashMap的描述）

　　　　　加载因子为0.75：即当 元素个数 超过 容量长度的0.75倍 时，进行扩容

　　　　　扩容增量：原容量的 1 倍

　　　　　如 HashSet的容量为16，一次扩容后是容量为32

          1 . Set中是不能出现重复数据的。

          2 . Set中可以出现空数据。

          3 . Set中的数据是无序的。

LinkedHashSet：这个相对于HashSet来说有一个很大的不一样是LinkedHashSet是有序的。

TreeSet：

         1.写入的数据是有序的。

         2.不写入重复数据

问：TreeSet和TreeMap的关系

TreeSet 底层是通过 TreeMap 来实现的（如同HashSet底层是是通过HashMap来实现的一样），底层数据结构都是红黑树

相同点：

TreeMap和TreeSet都是有序的集合，也就是说他们存储的值都是排好序的。

TreeMap和TreeSet都是非同步集合，因此他们不能在多线程之间共享，不过可以使用方法Collections.synchroinzedMap()来实现同步

运行速度都要比Hash集合慢，他们内部对元素的操作时间复杂度为O(logN)

不同点：

最主要的区别就是TreeSet和TreeMap非别实现Set和Map接口

TreeSet只存储一个对象，而TreeMap存储两个对象Key和Value（仅仅key对象有序）

TreeSet中不能有重复对象，而TreeMap中可以存在

List接口

ArrayList、Vector、stack默认初始容量为10

Vector：线程安全，但速度慢

　　　　底层数据结构是数组结构

　　　　加载因子为1：即当 元素个数 超过 容量长度 时，进行扩容

　　　　扩容增量：原容量的 2倍

ArrayList：线程不安全，查询速度快

　　　　底层数据结构是数组结构

　　　　扩容增量：扩容50%

linkedList ：底层是双向链表，新增和删除比arrayList更好。但是查找和修改不如arrayList。

Stack：stack继承自vector，那么底层也是数组实现的。他的方法如下

1. public push  （item ）  把项压入栈顶。  返回： item 参数  

2. public pop () 移除栈顶对象，并作为函数的值 返回该对象

返回：栈顶对象  

3. public peek() 查看栈顶对象而不移除它

返回：栈顶对象 

4.public boolean empty （测试堆栈是否为空。）

问：ArrayList、Vector、stack、linkedList区别

问：iterator 和 listiterator

在使用java集合的时候，都需要使用Iterator。但是java集合中还有一个迭代器ListIterator,在使用List、ArrayList、LinkedList和Vector的时候可以使用。

Iterator迭代器：

next()     hasNext()

remove()将会删除上次调用next方法时返回的元素，如果想要删除指定位置上的元素，需要越过这个元素，如果调用remove之前没有调用next将是不合法的，如果这样做，将会抛出一个IllegalStateException异常。删除集合中Iterator指向位置后面的元素

ListIterator迭代器

add(E e): 在指定位置插入一个元素。

hasPrevious()

previous()

Queue

PriorityQueue：保存队列元素的顺序不是按照元素添加的顺序来保存的，而是在添加元素的时候对元素的大小排序后再保存的。因此在PriorityQueue中使用peek()或pool()取出队列中头部的元素，取出的不是最先添加的元素，而是最小的元素。

Map

HashMap:

1.  HashMap不是线程安全的 

2. HashMap的键和值都可以为null 

问：为什么HashMap是线程不安全的?

一：如果多个线程同时使用put方法添加元素，而且假设正好存在两个put的key(调用hashcode（）)发生了碰撞(hash值一样)，那么根据HashMap的实现，这两个key会添加到数组的同一个位置，这样最终就会发生其中一个线程的put的数据被覆盖。

二：多个线程同时检测到元素个数超过数组大小*loadFactor（负载因子），这样就会发生多个线程同时对数组进行扩容，都在重新计算元素位置以及复制数据，但是最终只有一个线程扩容后的数组会赋给table，也就是说其他线程的都会丢失

问：hashMap底层实现

数组连续内存空间，查找速度快，增删慢；链表充分利用了内存，存储空间是不连续的，首尾存储上下一个节点的信息，所以寻址麻烦，查找速度慢，但是增删快；哈希表呢，综合了它们两个的优点，一个哈希表，由数组和链表组成。

HashMap的内部存储结构其实是数组和链表的结合。当实例化一个HashMap时，系统会创建一个长度为Capacity的Entry数组，这个长度在哈希表中被称为容量(Capacity)，在这个数组中可以存放元素的位置我们称之为“桶”(bucket)，每个bucket都有自己的索引，系统可以根据索引快速的查找bucket中的元素。 每个bucket中存储一个元素，即一个Entry对象，但每一个Entry对象可以带一个引用变量，用于指向下一个元素，因此，在一个桶中，就有可能生成一个Entry链。 

HashMap有四种构造方法： 
  HashMap()：初始容量16，默认加载因子0.75 
  HashMap(int initialCapacity)：自定义初始容量 
  HashMap(int initialCapacity,float loadFactor)   
  HashMap(Map<? extends K,? extends V> m) 
       这四个构造方法其实都受两个参数的影响：容量和加载因子。容量是哈希表中桶的数量，初始容量为16。加载因子是对哈希表的容量在自动增加resize()之前所达到尺度的描述。当哈希表中的条目数超过threshold(=Capacity*loadFactor) 的值时，要对哈希表进行rehash操作。

      默认加载因子 (.75) 在时间和空间成本上寻求一种折中。加载因子过高虽然减少了空间开销，但同时也增加了查询成本（在大多数 HashMap 类的操作中，包括 get 和 put 操作，都反映了这一点）。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地减少 rehash 操作次数。

问：HashMap插入值与解决冲突方法

put(key, value)存储对象到HashMap中，使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时，我们先对键调用hashCode()方法，返回的hashCode用于找到bucket位置来储存Entry对象。

hashcode相同，所以它们的bucket位置相同，‘碰撞’会发生,存入对应链表

“如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？”除非你真正知道HashMap的工作原理，否则你将回答不出这道题。默认的负载因子大小为0.75，也就是说，当一个map填满了75%的bucket时候，和其它集合类(如ArrayList等)一样，将会创建原来HashMap大小的两倍的bucket数组，来重新调整map的大小，并将原来的对象放入新的bucket数组中。这个过程叫作rehashing，因为它调用hash方法找到新的bucket位置。

解决哈希表的冲突-开放地址法和链地址法

1 开放地址法

这个方法的基本思想是：当发生地址冲突时，按照某种方法继续探测哈希表中的其他存储单元，直到找到空位置为止。这个过程可用下式描述： 
H i ( key ) = ( H ( key )+ d i ) mod m ( i = 1,2,…… ， k ( k ≤ m – 1)) 

增量 d 可以有不同的取法，并根据其取法有不同的称呼： 
（ 1 ） d i ＝ 1 ， 2 ， 3 ， …… 线性探测再散列； 
（ 2 ） d i ＝ 1^2 ，－ 1^2 ， 2^2 ，－ 2^2 ， k^2， -k^2…… 二次探测再散列； 
（ 3 ） d i ＝ 伪随机序列 伪随机再散列； 

2、链地址法 

     将所有哈希地址相同的记录都链接在同一链表中图形类似于图2。也就是说，当HashMap中的每一个bucket里只有一个Entry，不发生冲突时,Hashmap是一个数组，根据索引可以迅速找到Entry,但是，当发生冲突时，单个的bucket里存储的是一个Entry链，系统必须按顺序遍历每个Entry,直到找到为止。

为了减少数据的遍历，冲突的元素都是直接插入到第一个Entry后面的，所以，最早放入bucket中的Entry，位于Entry链中的最末端。这从put(K key，V value)中也可以看出，在同一个bucket存储Entry链的情况下，新放入的Entry总是位于bucket中。 

问：如何线程安全使用hashmap

HashMap配合Collections工具类使用实现线程安全Collections.synchronizedMap()。

同时还有ConcurrentHashMap可以选择，该类的线程安全是通过Lock的方式实现的，所以效率高于Hashtable。

LinkedHashMap:

保存了元素插入的顺序

问：hashMap遍历方式

第一种:迭代器
　　Map map = new HashMap();
　　Iterator iter = map.entrySet().iterator();
　　while (iter.hasNext()) {
　　 Map.Entry entry = (Map.Entry) iter.next();
　　 Object key = entry.getKey();
　　 Object val = entry.getValue();
　　}（效率高）

Map map = new HashMap();
　　Iterator iter = map.keySet().iterator();
　　 while (iter.hasNext()) {
　　 Object key = iter.next();
　　 Object val = map.get(key);
　　}(效率低)

第二种：for each遍历

for(Entry<Integer ,String>entry :hs.entrySet()){

System.out.println("key:"+entry.getKey()+" value:"+entry.getValue()); }

HashTable:

1.  Hashtable线程安全，但效率低，因为是Hashtable是使用synchronized的，所有线程竞争同一把锁

2.HashTable键值不能为空

TreeMap:

1.  不是线程安全的 

2. 底层是红黑树

3.元素键值按某种顺序排列

问：HashMap和Hashtable 、ConcurrentHashMap 区别

HashMap和Hashtable 

a.  HashMap不是线程安全的；Hashtable线程安全，但效率低，因为是Hashtable是使用synchronized的，所有线程竞争同一把锁；

b. HashMap的键和值都可以为null，HashTable不可以。 

ConcurrentHashMap 

通过分析Hashtable就知道，synchronized是针对整张Hash表的，即每次锁住整张表让线程独占，ConcurrentHashMap允许多个修改操作并发进行，其关键在于使用了锁分离技术。它使用了多个锁来控制对hash表的不同部分进行的修改。  

ConcurrentHashMap内部使用segment数组来分别表示这些不同的部分，每一个segment都包含了一个Entry数组的hashtable，每个段其实就是一个小的hashtable，它们有自己的锁。只要多个修改操作发生在不同的段上，它们就可以并发进行。

有些方法需要跨段，比如size()和containsValue()，它们可能需要锁定整个表而不仅仅是某个段，这需要按顺序锁定所有段，操作完毕后，又按顺序释放所有段的锁。这里“按顺序”是很重要的，否则极有可能出现死锁

问：包装类是否适合作为hashmap键值

包装类都是不可变的（final），而且已经重写了equals()和hashCode()方法了。 

我们重写了equals()和hashCode()方法的类也可以作为键。

问：synchronized

1. 修饰一个代码块，被修饰的代码块称为同步语句块，其作用的范围是大括号{}括起来的代码，作用的对象是调用这个代码块的对象。其他线程无法访问此对象的所有同步代码块，但可以访问非同步代码块。 
2. 修饰一个方法，被修饰的方法称为同步方法，其作用的范围是整个方法，作用的对象是调用这个方法的对象； 
3. 修改一个静态的方法，其作用的范围是整个静态方法，作用的对象是这个类的所有对象； 

synchronized和lock、volatile

lock:

加锁和解锁处需要通过lock()和unlock()显示指出。会在finally块中写unlock()以防死锁。

是一个类

线程需要的锁被占用，就是可以尝试获得锁，线程可以不用一直等待

大量同步的情况使用明显提高性能

Synchronized:

synchronized可以加在方法上，也可以加在特定代码块中

Java的关键字，在jvm层面上

线程需要的锁被占用，会一直等待

少量同步的情况使用

volatile

用volatile修饰的变量，线程在每次使用变量的时候，都会读取变量最新值。volatile很容易被误用，用来进行原子性操作。