Java小知识

2020 年 8 月 20 日
筆記
C#、java学习

1.ArrayList与LinkedList的区别

可以从它们的底层数据结构、效率、开销进行阐述

ArrayList是数组的数据结构，LinkedList是链表的数据结构。
随机访问的时候，ArrayList的效率比较高，因为LinkedList要移动指针，而ArrayList是基于索引（index）的数据结构，可以直接映射到。
插入、删除数据时，LinkedList比较高，因为ArrayList要移动数据。
LinkedList比ArrayList开销更大，因为LinkedList的节点除了存储数据，还需要存储引用。

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

Collections.sort是对List进行排序，Arrays.sort是对数组进行排序。

2.1 Collections.sort底层实现：

Collection.sort方法调用了list.sort方法:

/Unchecked/
public static <T extends Comparable<? super T>> void sourt(List<T> list){
  list.sourt(c:null);  
}

list.sourt方法调用了Arrays.sort()的方法：

@Override
public void sourt (Comparator<? super E> c){
  Arrays.sort(a,c);  
}

因此，Collections.sort()方法底层接收调用的Array.sort方法。

2.2 Arrays.sort底层实现：

Arrays的sort方法如下：

public static <T> void sort (T[] a, Comparator<? super T> c){
  if(c == null){
        sort(a);
    } else{
        if(LegacyMergeSort.userRequested){
            LegacyMergeSort(a,c);
        }
        else{
            TimSort.sort(a,lo:0,a.length,c,work:null,work:null,workBase:0,workLen:0);
        }
    }
}

如果比较器为null，进入sort(a)方法。如下：

public static void sort(Object[] a){
  if(LegacyMergeSort.userRequested){
    LegacyMeergeSort(a);
    }else{
     ComparableTimSort.sort(a,lo:0,a.length,work:null,workBase:0,wokeLen:0);
    }  
}

因此，Arrays的sort方法底层就是：

legacyMergeSort(a)，归并排序，ComparableTimSort.sort()：即Timsort排序。

2.3Timesort排序：

Timsort排序是结合了合并排序（merge.sort）和插入排序（insertion sort）而得出的排序方法；

1.当数组长度小于某个值，采用的是二分插入排序算法，如下：

static <T> void sort(T[] a,int lo,int hi,Comparator <? super T> c,T[] work,int workBase,int workLen){
  assert c != null && a != null && lo >= 0 &&lo <= hi  && hi <= a.length  

  int nRemaining = hi - lo;
  if(nRemaining < 2){
    return;
  }
  if(nRemaining < MIN_MERGE){
      int initRunLen = countRunAndMakeAscending(a,lo,hi,c);
      binarySort(a,lo,hi,start:lo + initRunLen,c);
      return;      
  }  
}

2.找到各个run，并入栈。

do{
      int runLen = countRunAndMakeAscending(a,lo,hi,c);

      if(runLen < minRun){
        int force = nRemaining <= minRun ? nRemaining : minRun;
        binary(a,lo,hi:lo+force,start:lo+runLen,c);
        runLen = force;
    }

    ts.pushRun(lo,runLen);
    ts.mergeCollapse();

    lo += runLen;
    nRemaining -= runLen;
}while(nRemaining !=0);

assert lo == hi;
ts.mergeForceCollapse();
assert ts.stackSize == 1;

3.按规则合并run。

private void mergeForceCoolapse(){
  while(stackSizs > 1){
    int n = stackSize - 2;
    if(n>0 && runLen[n-1] < runLen[n+1]){
        n--;
        }
    mergeAt(n);
    }  
}

3.HashMap原理，java8做了什么改变

HashMap是以键值对存储数据的集合容器
HashMap是非线性安全的。
HashMap底层数据结构：数组+(链表、红黑树)，jdk8之前是用数组+链表的方式实现，jdk8引进了红黑树
Hashmap数组的默认初始长度是16，key和value都允许null的存在
HashMap的内部实现数组是Node[]数组，上面存放的是key-value键值对的节点。HashMap通过put和get方法存储和获取。
HashMap的put方法，首先计算key的hashcode值，定位到对应的数组索引，然后再在该索引的单向链表上进行循环遍历，用equals比较key是否存在，如果存在则用新的value覆盖原值，如果没有则向后追加。
jdk8中put方法：先判断Hashmap是否为空，为空就扩容，不为空计算出key的hash值i，然后看table[i]是否为空，为空就直接插入，不为空判断当前位置的key和table[i]是否相同，相同就覆盖，不相同就查看table[i]是否是红黑树节点，如果是的话就用红黑树直接插入键值对，如果不是开始遍历链表插入，如果遇到重复值就覆盖，否则直接插入，如果链表长度大于8，转为红黑树结构，执行完成后看size是否大于阈值threshold，大于就扩容，否则直接结束。
Hashmap解决hash冲突，使用的是链地址法，即数组+链表的形式来解决。put执行首先判断table[i]位置，如果为空就直接插入，不为空判断和当前值是否相等，相等就覆盖，如果不相等的话，判断是否是红黑树节点，如果不是，就从table[i]位置开始遍历链表，相等覆盖，不相等插入。
HashMap的get方法就是计算出要获取元素的hash值，去对应位置获取即可。
HashMap的扩容机制，Hashmap的扩容中主要进行两步，第一步把数组长度变为原来的两倍，第二部把旧数组的元素重新计算hash插入到新数组中，jdk8时，不用重新计算hash，只用看看原来的hash值新增的一位是零还是1，如果是1这个元素在新数组中的位置，是原数组的位置加原数组长度，如果是零就插入到原数组中。扩容过程第二部一个非常重要的方法是transfer方法，采用头插法，把旧数组的元素插入到新数组中。
HashMap大小为什么是2的幂次方？效率高+空间分布均匀

4. List 和 Set，Map 的区别

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

5. poll()方法和 remove()方法的区别？

Queue队列中，poll() 和 remove() 都是从队列中取出一个元素，在队列元素为空的情况下，remove() 方法会抛出异常，poll() 方法只会返回 null 。

6. HashMap，HashTable，ConcurrentHash的共同点和区别

HashMap

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

HashTable

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

ConcurrentHashMap

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

7. 写一段代码在遍历 ArrayList 时移除一个元素

因为foreach删除会导致快速失败问题，fori顺序遍历会导致重复元素没删除，所以正确解法如下：

第一种遍历，倒叙遍历删除

for(int i=list.size()-1; i>-1; i--){
  if(list.get(i).equals("jay")){
    list.remove(list.get(i));
  }
}

第二种，迭代器删除

Iterator itr = list.iterator();
while(itr.hasNext()) {
      if(itr.next().equals("jay") {
        itr.remove();
      }
}

8. Java中怎么打印数组？

数组是不能直接打印的哈，如下:

public class Test {

    public static void main(String[] args) {
        String[] jayArray = {"jay", "boy"};
        System.out.println(jayArray);
    }
}
//output
[Ljava.lang.String;@1540e19d

打印数组可以用流的方式Strem.of().foreach()，如下:

public class Test {

    public static void main(String[] args) {
        String[] jayArray = {"jay", "boy"};
        Stream.of(jayArray).forEach(System.out::println);
    }
}
//output
jay
boy

打印数组，最优雅的方式可以用这个APi,Arrays.toString()

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

9. TreeMap底层？

TreeMap实现了SotredMap接口，它是有序的集合。
TreeMap底层数据结构是一个红黑树，每个key-value都作为一个红黑树的节点。
如果在调用TreeMap的构造函数时没有指定比较器，则根据key执行自然排序。

10. HashMap 的扩容过程

Hashmap的扩容：

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

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

可以看一下HashSet的add方法，元素E作为HashMap的key，我们都知道HashMap的可以是不允许重复的，哈哈。

 public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

12. HashMap 是线程安全的吗，为什么不是线程安全的？死循环问题？

不是线性安全的。

并发的情况下，扩容可能导致死循环问题。

13. LinkedHashMap的应用，底层，原理

LinkedHashMap维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序（insert-order）或者是访问顺序，其中默认的迭代访问顺序就是插入顺序，即可以按插入的顺序遍历元素，这点和HashMap有很大的不同。
LRU算法可以用LinkedHashMap实现。

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

线性安全的

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

线性不安全的

Hashmap
Arraylist
LinkedList
HashSet
TreeSet
TreeMap

15. ArrayList 和 Vector 的区别是什么？

Vector是线程安全的，ArrayList不是线程安全的。
ArrayList在底层数组不够用时在原来的基础上扩展0.5倍，Vector是扩展1倍。
Vector只要是关键性的操作，方法前面都加了synchronized关键字，来保证线程的安全性。

public synchronized boolean add(E e){
    modCount++;
    ensureCapacityHelper(minCapacity : elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

16. 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);
}

17. 如何决定使用 HashMap 还是TreeMap？

这个点，主要考察HashMap和TreeMap的区别。

TreeMap实现SortMap接口，能够把它保存的记录根据键排序，默认是按key的升序排序，也可以指定排序的比较器。当用Iterator遍历TreeMap时，得到的记录是排过序的。

18. 如何实现数组和 List之间的转换？

List 转 Array

List 转Array，必须使用集合的 toArray(T[] array)，如下：

List<String> list = new ArrayList<String>();
list.add("jay");
list.add("tianluo");

// 使用泛型，无需显式类型转换
String[] array = list.toArray(new String[list.size()]);
System.out.println(array[0]);

如果直接使用 toArray 无参方法，返回值只能是 Object[] 类，强转其他类型可能有问题，demo如下：

List<String> list = new ArrayList<String>();
list.add("jay");
list.add("tianluo");

String[] array = (String[]) list.toArray();
System.out.println(array[0]);

运行结果：

Exception in thread "main" java.lang.ClassCastException: [Ljava.lang.Object; cannot be cast to [Ljava.lang.String;
    at Test.main(Test.java:14)

Array 转List

使用Arrays.asList() 把数组转换成集合时，不能使用修改集合相关的方法啦，如下：

String[] str = new String[] { "jay", "tianluo" };
List list = Arrays.asList(str);
list.add("boy");

运行结果如下：

Exception in thread "main" java.lang.UnsupportedOperationException
    at java.util.AbstractList.add(AbstractList.java:148)
    at java.util.AbstractList.add(AbstractList.java:108)
    at Test.main(Test.java:13)

因为 Arrays.asList不是返回java.util.ArrayList,而是一个内部类ArrayList。

Tags: C#、java学习

Java小知识

1.ArrayList与LinkedList的区别

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

2.1 Collections.sort底层实现：

2.2 Arrays.sort底层实现：

2.3Timesort排序：

3.HashMap原理，java8做了什么改变

4. List 和 Set，Map 的区别

5. poll()方法和 remove()方法的区别？

6. HashMap，HashTable，ConcurrentHash的共同点和区别

HashMap

HashTable

ConcurrentHashMap

7. 写一段代码在遍历 ArrayList 时移除一个元素

8. Java中怎么打印数组？

9. TreeMap底层？

10. HashMap 的扩容过程

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

12. HashMap 是线程安全的吗，为什么不是线程安全的？死循环问题？

13. LinkedHashMap的应用，底层，原理

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

15. ArrayList 和 Vector 的区别是什么？

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

17. 如何决定使用 HashMap 还是TreeMap？

18. 如何实现数组和 List之间的转换？

VirMach 便宜 VPS

QNews

Java小知识

1.ArrayList与LinkedList的区别

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

2.1 Collections.sort底层实现：

2.2 Arrays.sort底层实现：

2.3Timesort排序：

3.HashMap原理，java8做了什么改变

4. List 和 Set，Map 的区别

5. poll()方法和 remove()方法的区别？

6. HashMap，HashTable，ConcurrentHash的共同点和区别

HashMap

HashTable

ConcurrentHashMap

7. 写一段代码在遍历 ArrayList 时移除一个元素

8. Java中怎么打印数组？

9. TreeMap底层？

10. HashMap 的扩容过程

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

12. HashMap 是线程安全的吗，为什么不是线程安全的？死循环问题？

13. LinkedHashMap的应用，底层，原理

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

15. ArrayList 和 Vector 的区别是什么？

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

17. 如何决定使用 HashMap 还是TreeMap？

18. 如何实现数组和 List之间的转换？

分享此文：

Related Posts

权限修饰符和内部类

Nginx初学（一）安装与运行

CAS和锁的相关面试题

Vue管理系统前端系列一vue-cli4.x 初始化项目

VirMach 便宜 VPS

QNews

熱門搜尋