集合总结

1. Arraylist与LinkedList区别

ArrayList是数组的数据结构（默认大小为10），LinkedList是链表的数据结构。
ArrayList随机访问效率高，LinkedList插入删除效率高。
LinkedList因还需存储引用，开销更大。

Arraylist集合插入一万条数据，如何提高效率？

ArrayList的底层是数组实现,并且数组的默认值是10,如果插入10000条要不断的扩容,耗费时间,所以我们调用ArrayList的指定容量的构造器方法ArrayList(int size) 就可以实现不扩容,就提高了性能。

2. Collections.sort和Arrays.sort的实现原理

Collection.sort是对list进行排序，Arrays.sort是对数组进行排序。

Collections.sort方法调用了list.sort方法，而list.sort调用Arrays.sort方法，总结即为Collections.sort方法底层就是调用的Array.sort方法。

Arrays的sort方法底层就是：

legacyMergeSort(a)，归并排序，

ComparableTimSort.sort()：即Timsort排序。

Timsort为结合归并与插入排序得到的排序方法。

3. HashMap原理

HashMap是以键值对存储数据的集合容器
HashMap是非线性安全的。
HashMap底层数据结构：数组+(链表、红黑树)，jdk8之前是用数组+链表的方式实现，jdk8引进了红黑树
Hashmap数组的默认初始长度是16，key和value都允许null的存在
HashMap的put方法，首先计算key的hashcode值，定位到对应的数组索引，然后再在该索引的单向链表上进行循环遍历，用equals比较key是否存在，如果存在则用新的value覆盖原值，如果不存在则向后追加。
HashMap大小为什么是2的幂次方？效率高+空间分布均匀

HashMap解决哈希冲突？

Hashmap解决hash冲突，使用的是链地址法，即数组+链表的形式来解决。put执行首先判断table[i]位置，如果为空就直接插入，不为空判断和当前值是否相等，相等就覆盖，如果不相等的话，判断是否是红黑树节点，如果不是，就从table[i]位置开始遍历链表，相等覆盖，不相等插入。

4. List 和 Set，Map 的区别

List 以索引来存取元素，有序的，元素是允许重复的，可以插入多个null。且List 有基于数组、链表实现两种方式。
Set 不能存放重复元素，无序的，只允许一个null。
Set、Map 容器有基于哈希存储和红黑树两种方式实现。
Set 基于 Map 实现，Set 里的元素值就是 Map的键值。
Map存储键值对映射。

5. HashMap，HashTable，ConcurrentHashMap的共同点和区别

5.1.HashMap

HashMap

底层由链表+数组+红黑树实现
可以存储null键和null值
线性不安全
初始容量为16，扩容每次都是2的n次幂
加载因子为0.75，当Map中元素总数超过Entry数组的0.75，触发扩容操作.
并发情况下，HashMap进行put操作会引起死循环，导致CPU利用率接近100%
HashMap是对Map接口的实现

5.2HashTable

HashTable

HashTable的底层也是由链表+数组+红黑树实现。
无论key还是value都不能为null
它是线性安全的，使用了synchronized关键字。
HashTable实现了Map接口和Dictionary抽象类
Hashtable初始容量为11

5.3ConcurrentHashMap

ConcurrentHashMap

ConcurrentHashMap的底层是数组+链表+红黑树
不能存储null键和值
ConcurrentHashMap是线程安全的
ConcurrentHashMap使用锁分段技术确保线性安全
JDK8为何又放弃分段锁，是因为多个分段锁浪费内存空间，竞争同一个锁的概率非常小，分段锁反而会造成效率低。

6. Java中打印数组？

public class Test {
    public static void main(String[] args) {
        String[] Array = {"xiaoliu", "boy"};
        System.out.println(Arrays.toString(Array));
    }
}
//output
[xiaoliu, boy]

7. HashMap 的扩容过程

Hashmap的扩容：

第一步把数组长度变为原来的两倍，
第二步把旧数组的元素重新计算hash插入到新数组中。
jdk8时，不用重新计算hash，只用看看原来的hash值新增的一位是零还是1，如果是1这个元素在新数组中的位置，是原数组的位置加原数组长度，如果是零就插入到原数组中。扩容过程第二步一个非常重要的方法是transfer方法，采用头插法，把旧数组的元素插入到新数组中。

8. HashSet是如何保证不重复的

其add方法，将HashMap的Key作为值存入，而HashMap的键不允许重复。

9. 哪些集合类是线程安全的？哪些不安全？

线性安全的

Vector：比Arraylist多了个同步化机制。
Hashtable：比Hashmap多了个线程安全。
ConcurrentHashMap:是一种高效但是线程安全的集合。
Stack：栈，也是线程安全的，继承于Vector。

线性不安全的

Hashmap
Arraylist
LinkedList
HashSet
TreeSet
TreeM

10.Collection与Collections的区别是什么？

Collection是Java集合框架中的基本接口，如List接口也是继承于它
```
public interface List<E> extends Collection<E> {}
```

Collections是Java集合框架提供的一个工具类，其中包含了大量用于操作或返回集合的静态方法。如列表的排序：

  public static <T extends Comparable<? super T>> void sort(List<T> list) {
    list.sort(null);
}

11. 快速失败(fail-fast)和安全失败(fail-safe)的区别是什么？

快速失败

在用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的内容进行了修改（增加、删除、修改），则会抛出Concurrent Modification Exception。

public class Test {

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);

        Iterator iterator = list.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
            list.add(3);
            System.out.println(list.size());
        }

    }
}

1
Exception in thread "main" java.util.ConcurrentModificationException
3
	at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
	at java.util.ArrayList$Itr.next(ArrayList.java:859)
	at Test.main(Test.java:12)

安全失败

采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。

public class Test {

    public static void main(String[] args) {
        List<Integer> list = new CopyOnWriteArrayList<>();
        list.add(1);
        list.add(2);

        Iterator iterator = list.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
            list.add(3);
            System.out.println("list size:"+list.size());
        }

    }
}

1
list size:3
2
list size:4

12.HashMap源码中的常量意义

HashMap默认初始化大小为什么是1 << 4（16）？

首先为什么是2的幂：为了更高效使用与运算，数组下标索引定位公式为i = (n - 1) & hash。

而当n的大小为2的倍数时，n%hash等价于(n - 1) & hash。位运算的效率比取余运算高。

其次为什么是16：如果太小，4或者8，扩容比较频繁；如果太大，32或者64甚至太大，又占用内存空间。

HashMap默认加载因子为什么是0.75？

加载因子表示哈希表的填满程度，跟扩容息息相关。如果是0.5，哈希表填到一半就开始扩容，这样会导致扩容频繁，并且空间利用率比较低。如果是1，哈希表完全填满才开始扩容，虽然空间利用提高了，但是哈希冲突机会却大了。

链表转红黑树的阈值为什么是8？

因为理想状态，随机哈希码情况下，链表中元素个数为8时的概率已经非常非常小，故阈值选为8.

树还原为链表的阈值为什么是6？

若设置为7.当HashMap不停插入删除时，链表长度可能在8左右振荡，导致链表和树之间频繁转换。

13.红黑树的特点

每个节点或者是黑色，或者是红色。
根节点是黑色。
每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
如果一个节点是红色的，则它的子节点必须是黑色的。
从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

Java知识

java

本博客所有文章除特别声明外，大部分为学习心得，欢迎与博主联系讨论

SQL语句练习上一篇

二分查找与双指针下一篇