# 【JAVA面试题】数据结构及算法
## ArrayList和Vector的异同
首先是两者的相同点：
+ 都实现了List接口（List接口继承自Collection接口）
+ 都是有序集合，即存储在两个集合中的元素的位置都是有顺序的。相当于一种动态的数组，可以按位置索引取出元素。
+ 元素允许重复，这与HashSet之类的集合最大不同之处。
然后是两者的不同点：
1) 同步性
  Vector是线程安全的，它的方法之间是线程同步的，而ArrayList不是。因为ArrayList不考虑线程安全，效率相对高。
  Vector&ArrayList和Hashtable&HashMap之间的比较，要考虑线程因素，记住Vector和Hashtable是旧的，是java一诞生就提供的，是线程安全的。ArrayList和HashMap是Java2时才提供的，线程不安全的。
2) 数据增长
  ArrayList和Vector都有一个初始的容器大小，储存的元素超过容器大小时，需要增加存储空间。Vector默认增加为原来二倍。ArrayList的增长策略没有明确规定（源代码中看应该是增长到原来的1.5倍）
  ArrayList和Vector都可以设置初始的空间大小，Vector可以设置增长的空间大小，而ArrayList没有提供设置增长空间的方法。
## HashMap和Hashtable的区别
先说相同点：
+ HashMap是Hashtable的轻量级实现，两者都实现了Map接口，主要区别在于HashMap允许空键值，由于非线程安全，在只有一个线程访问的情况下，效率更高。
+ HashMap允许将Null作为一个entry的Key或者value，而Hashtable不允许
+ HashMap去掉了contains方法，改成了containsValue和containsKey因为contains容易产生误解
+ Hashtable继承自Dictionary类，而HashMap是Java1.2引入的Map interface的实现。
+ Hashtable的方法是Synchronize的，而HashMap不是。在多个线程访问Hashtable时，不需要为其方法实现同步，而HashMap就必须为其提供外同步。
## List和Map区别？
一个存储单元数据的集合，另一个存储键和值这样的双列数据的集合，List中存储的数据是有顺序，并且允许重复。Map中存储的数据没有顺序，并且不能重复，但是值可以重复。
## List，Set和Map均继承自Collection接口？
List和Set继承子Collection，但Map不是。
## List、Set和Map这三个接口，在存取元素时，各有什么特点？
List和Set实现了同一个接口Collection。Set中不允许有重复的值。Set中的元素是无序的。
List表示有先后顺序的集合。
Map是一个双列的集合，其中有put方法，每次存储时，要存储一对key/value，不能存储重复的Key
## 说说ArrayList、Vector和LinkedList的存储性能和特性
ArrayList和Vector使用数组方式存储数据，此数值元素数量大于实际存储数据以便增加和插入元素，都允许直接按序号索引元素，但是插入元素要时尚设计数据元素移动等内存操作，所以索引搜索数据块，插入数据慢
Vector使用了synchronized方法，通常性能较ArrayList差。
LinkedList使用双向链表实现存储，按序号索引数据需要进行前向或后向遍历，但是插入数据只需要记录本项的前后项即可，所以插入速度快。
## 去掉一个Vector集合中重复的元素
```JAVA
Vector newVector = new Vector();
for (int i =0,i<vector.size();i++){
    Object obj = vector.get(i);
    if (!newVector.contains(obj):
      newVector.add(obj);
}
```
还有一种简单的方式：
```JAVA
HashSet set = new HashSet(vector);
```
## Collection和Collections的区别
Collection是集合类的上级接口，继承与他的接口主要有Set和List。
Collection是针对集合类的一个帮助类，提供了一系列的静态方法实现对各种集合的搜索、排序、线程安全性等操作。
## Set中元素不能重复，使用什么区分重复？==还是equals()?有何区别？
Set中的元素是不能重复的，元素重复与否是使用equalss()方法进行判断的。
equals()和==方法引用值是指向同一个对象equals在类中的覆盖，为了是当两个分离的对象的内容和类型相配的话，返回真。
## 你所知道的集合类都有哪些？主要方法？
最常见的集合类有List和Map。
List的具体实现包括ArrayList和Vector，是可变大小的列表，比较适合构建、存储和操作任何类型对象的元素列表。List适合语按数值索引访问的元素的情形。
Map提供了一个更通用的元素存储方法。Map集合类用于存储元素对（称作键值对），其中每个键映射一个值，且不可以重复
方法，对于set主要有add、remove和contains，对于map有put、remove和contains等。
set没有get方法，list和map有get方法，list和set都是可迭代出所有元素，迭代时可以迭代出所有元素，所以set和list都有一个iterator方法，用于返回那个iterator对象。