面试题-04-集合

HashMap 和 Hashtable 的区别：

相同点：
都是实现来Map接口（hashTable还实现了Dictionary 抽象类）。

不同点：
历史原因:Hashtable 是基于陈旧的 Dictionary 类的，HashMap 是 Java 1.2 引进的 Map 接口 的一个实现，

HashMap把Hashtable 的contains方法去掉了，改成containsvalue 和containsKey。因为contains方法容易让人引起误解。

同步性:Hashtable 的方法是 Synchronize 的，线程安全；
而 HashMap 是线程不安全的，不是同步的。所以只有一个线程的时候使用hashMap效率要高。

值：HashMap对象的key、value值均可为null。HahTable对象的key、value值均不可为null。

容量：HashMap的初始容量为16，Hashtable初始容量为11，两者的填充因子默认都是0.75。

HashMap扩容时是当前容量翻倍即:capacity × 2，Hashtable扩容时是容量翻倍+1 即:capacity × 2+1。

HashMap可以通过下面的语句进行同步：
Map m = Collections.synchronizeMap(hashMap);
或者改用 ConcurrentHashMap

	HashMap	HashTable	ConcurrentHashMap
null键	允许	不允许	不允许
null值	允许	不允许	不允许
效率	非常高	低	高
线程安全	不安全	安全	安全
数据结构	数组+链表+红黑树	数组+链表	数组+链表+红黑树
同步方式	无	synchronized同步方法	1.7版本：基于segment分段锁机制，基于ReentrantLock实现；1.8版本：基于CAS+synchronized实现，空节点插入使用CAS，有Node节点则使用synchronized加锁
迭代器类型	fail-fast迭代器：在遍历时不断更新元素，否则将抛出异常	fail-safe迭代器：基于容器的克隆，因此遍历操作时元素的更新不影响遍历	fail-safe迭代器：基于容器的克隆，因此遍历操作时元素的更新不影响遍历

---

HashSet 和 HashMap 区别：

HashSet 底层就是基于 HashMap 实现的。只不过HashSet里面的HashMap所有的value都是同一个Object而已，因此HashSet也是非线程安全的。

---

ArrayList 与 Vector 的区别：

共同点： 都实现了List接口，都是有序的集合，按索引号取出元素，数据都是可重复的，这是与hashSet最不同的，hashSet不可以按照索引号去检索其中的元素，也不允许有重复的元素。

区别：
Vector是线程安全 ArrayList线程不安全
Vector扩容默认为原来2倍，ArrayList扩容为原来的1.5倍。
ArrayList 与 Vector 都可以设置初始的空间大小，Vector 还可以设置增长的空间大小，而 ArrayList 没有提供设置增长空间的方法。

---

HaspMap 与 TreeMap的区别：

HashMap通过hashcode对其内容进行快速查找，而TreeMap中所有的元素都保持着某种固定的顺序，如果你需要得到一个有序的结果你就应该使用TreeMap（HashMap中元素的排列顺序是不固定的）。

---

Collection、Map和Collections的区别

Collection是单列集合的顶层接口,
Map是双列集合的顶层接口
Collections是一个集合的工具类，提供了排序、查找等操作集合的一些常用方法。

---

Collection框架中实现比较要怎么做？

第一种，实体类实现Comparable接口，并实现 compareTo(T t) 方法，我们称为内部比较器。
用法 Collections.sort(List list);

第二种，创建一个外部比较器，这个外部比较器要实现Comparator接口的 compare(T t1, T t2)方法。
用法Collections.sort(List list,Comparator<> c); list.sort(Comparator<> c);

comparable 和 comparator的区别？

comparable接口实际上是出自java.lang包，它有一个 compareTo(Object obj)方法用来排序
comparator接口实际上是出自 java.util包，它有一个compare(Object obj1, Object obj2)方法用来排序
一般我们需要对一个集合使用自定义排序时，我们就要重写compareTo方法或compare方法，当我们需要对某一个集合实现两种排序方式，比如一个song对象中的歌名和歌手名分别采用一种排序方法的话，我们可以重写compareTo方法和使用自制的Comparator方法或者以两个Comparator来实现歌名排序和歌手名排序

---

ConcurrentHashMap

jdk1.8中：放弃了Segment，直接用 Node数组+链表+红黑树的数据结构来实现，并发控制使用Synchronized + CAS来操作，整个看起来就像是优化过且线程安全的HashMap

---

遍历一个 List 有哪些不同的方式？

1、for 循环遍历，基于计数器。

在集合外部维护一个计数器，然后依次读取每一个位置的元素，当读取到最后一个元素后停止。

2、迭代器遍历，Iterator。

Iterator 是面向对象的一个设计模式，目的是屏蔽不同数据集合的特点，统一遍历集合的接口。Java 在 Collections 中支持了 Iterator 模式。

增强for循环是迭代器的一种简化形式。迭代器灵活性更高，可以进行增删操作，并且可以在遍历过程中修改集合的元素。而增强for循环更简洁方便，但功能相对较弱，只适用于遍历，不能进行元素的增删操作。

3、foreach 循环遍历。

foreach 内部也是采用了 Iterator 的方式实现，使用时不需要显式声明 Iterator 或计数器。优点是代码简洁，不易出错；缺点是只能做简单的遍历，不能在遍历过程中操作数据集合，例如删除、替换。

System.out.println("-----------forEach遍历-------------");
list.parallelStream().forEach(k -> {
    System.out.println(k);
});
System.out.println("-----------for遍历-------------");
for (Student student : list) {
    System.out.println(student);
}
System.out.println("-----------Iterator遍历-------------");
Iterator<Student> iterator = list.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}

---

数组和 List 之间的转换

数组转List：使用 Arrays工具类静态方法asList(数组) 返回List集合
List转数组：使用 List自带的toArray() 返回数组

---

hashCode（）与equals（）

1 如果两个对象相等，则hashcode一定也是相同的
2 两个对象相等,对两个equals方法返回true
3 两个对象有相同的hashcode值，它们也不一定是相等的（哈希冲突）
综上，equals方法被重写过，则hashCode方法也必须被重写
hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写hashCode()，则该class的两个对象无论如何都不会相等（即使这两个对象指向相同的数据）。

HashMap原理、哈希冲突的解决

简单总结一下HashMap是使用了哪些方法来有效解决哈希冲突的：
1 使用链地址法（使用散列表）来链接拥有相同hash值的数据；
2 使用2次扰动函数（hash函数）来降低哈希冲突的概率，使得数据分布更平均；
3 引入红黑树进一步降低遍历的时间复杂度，使得遍历更快；

HashMap什么时候进行扩容？

JAVA7:

void addEntry(int hash, K key, V value, int bucketIndex) {
　　　　//1、判断当前个数是否大于等于阈值
　　　　//2、当前存放是否发生哈希碰撞
　　　　//如果上面两个条件否发生，那么就扩容
　　　　if ((size >= threshold) && (null != table[bucketIndex])) {
　　　　　　//扩容，并且把原来数组中的元素重新放到新数组中
　　　　　　resize(2 * table.length);
　　　　　　hash = (null != key) ? hash(key) : 0;
　　　　　　bucketIndex = indexFor(hash, table.length);
　　　　}
 
　　　　createEntry(hash, key, value, bucketIndex);
　　}
Hashmap的扩容需要满足两个条件：
1 当前数据存储的数量（即size()）>=阈值(默认0.75)；
2 当前加入的数据发生hash冲突。

理解如下：
如果一直不发生hash冲突 直到数组装满 再进行add的时候 必然会hash冲突 此时会扩容
如果添加一直hash冲突 只占用数组的某个位置(链表、红黑树解决冲突) 
不满足第一个条件 也不会扩容 因为没有必要 数组其他位置都很空余


抄自https://www.cnblogs.com/yanzige/p/8392142.html
因为上面这两个条件，所以存在下面这些情况

（1）、就是hashmap在存值的时候（默认大小为16，负载因子0.75，阈值12），
可能达到最后存满16个值的时候，再存入第17个值才会发生扩容现象，因为前16个值，
每个值在底层数组中分别占据一个位置，并没有发生hash碰撞。

（2）、当然也有可能存储更多值（超多16个值，最多可以存27个值）都还没有扩容。
原理：前11个值全部hash碰撞，存到数组的同一个位置
（虽然hash冲突，但是这时元素个数小于阈值12，
并没有同时满足扩容的两个条件。所以不会扩容），
[在存入第12个元素的时候，还是存入前面11个元素所在的下标位置，
因为存入之前此时比较当前元素个数 11<12(16*0.75)，所以在存入第12个元素的时候不会发生扩容，
那么还有15个数据下标的位置是空的，
后面所有存入的15个值全部分散到数组剩下的15个位置
（这时元素个数大于等于阈值，但是每次存入的元素并没有发生hash碰撞，
也没有同时满足扩容的两个条件，所以叶不会扩容），
前面11+15=26（12+15=27评论指正，20201230日晚验证后修改为27），
所以在存入第28个值的时候才同时满足上面两个条件，这时候才会发生扩容现象。

JAVA8:
Java8不再像Java7中那样需要满足两个条件，
Java8中扩容只需要满足一个条件：
当前存放新值的时候已有元素的个数>=阈值
（1）扩容一定是放入新值的时候，该新值不是替换以前位置的情况下（说明：put（“name”,”zhangsan”），而map里面原有数据<”name”,”lisi”>，则该存放过程就是替换一个原有值，而不是新增值，则不会扩容）
（2）扩容发生在存放后，即是数据存放后（先存放后扩容），判断当前存入对象的个数，如果大于阈值则进行扩容。

当hashmap中的元素个数超过数组大小 × loadFactor 时，就会进行数组扩容，loadFactor的默认值为0.75，也就是说，默认情况下，数组大小为16，那么当hashmap中元素个数超过16 × 0.75=12的时候，就把数组的大小扩展为2 × 16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知hashmap中元素的个数，那么预设数组的大小能够有效的提高hashmap的性能。

比如说，我们有1000个元素new HashMap(1000)， 但是理论上来讲new HashMap(1024)更合适，不过上面已经说过，即使是1000，hashmap也自动会将其设置为1024。 但是new HashMap(1024)还不是更合适的，因为0.75×1024 < 1000, 也就是说为了让0.75 × size > 1000， 我们必须这样new HashMap(2048)才最合适，避免了resize的问题。

---