投稿
  1. 首页
  2. java

Java集合

code • 2022-4-30 • java • 阅读 27

Java集合,第1张

1、Java中的容器有哪些？

答：容器主要包括Collection 和 Map 两种，其中Collection 中存储着对象的集合，Map 中存储两个对象的映射表（键值对）。

图后续补充

2、详细介绍一下集合有哪些类，和各自的特点
  • List 
    • ArrayList ：是基于动态数组实现的，支持随机访问
    • LinkedLits ：基于双向链表实现的，只能顺序访问，但是支持快速的在链表中插入和删除元素，还可以用作栈，队列 和双向队列
    • Vector ：和ArrayList 类似，但是他是线程安全的。
  • Set 
    • TreeSet ：基于红黑树实现的，支持有序性 *** 作，如根据一个范围查找元素。但是查找选了不如HashSet, 查找的时间复杂度为O(logN)
    • HashSet ：基于HashMap 实现的，支持快速的查找，但是不支持有序性 *** 作。查找的时间复杂度为O(1)。失去了元素的插入顺序信息，就是说，用Iterator 去遍历的时候，得到的结果顺序可能是不确定的。
    • LinkedHashSet 是 HashSet 的子类，不能过去内部是通过LinkedHashMap 实现的，内部使用双向链表维护插入顺序，因此是有序的。
  • Queue
    • LinkedList 可以用它来实现双向队列。
    • PriorityQueue 基于堆结构实现，可以用它来实现优先队列。
    • ArrayQueue基于数组实现，可以用它实现双端队列，也可以作为栈。

3、说一下Map 有哪些实现类和他们的各自特点
  • TreeMap : 基于红黑树实现的，是有序的
  • HashMap :  jdk7 基于数组加链表实现，jdk8以后基于数组加链表加红黑树实现。
  • HashTbale : 与 HashMap类似，但是是线程安全的
  • LinkedHashMap : 继承于 HashMap，使用双向链表维护元素的顺序。
4、说一下ArrayList和LinkedList的区别？

ArrayList和LinkedList是List接口两种不同的实现方式，他们最本质的区别就是ArrayList 内部是用动态数组来存储元素，而LinkedList内部使用双线链表来存储元素。

根据存储元素的方式不同，导致他们的相对应的方法具有不同的时间复杂度。

首先对于ArrayList来说，随机查询get（int index）的时间复杂度是O(1)，因为是直接从底层数组根据下标获取的，和数组的长度没有关系。这也是ArrayList最大的有点。

插入元素时add（E e）方法回自动将元素插到数组的末尾，如果不需要考虑扩容，时间复杂度是O(1)，如果需要扩容，内部执行的Arrays.copyOf()是耗时的关键，因为需要把原有数组中的元素复制到扩容之后的新数组中。

如果指定位置插入元素 add(int index, E element) ，就会涉及到元素的赋值，因此时间复杂度为O(N)；

对于删除元素，remove(int index) 方法回将指定位置的元素删除，这个步骤也会涉及到底层元素的复制，因此时间复杂度为O（n）;

其次对于LinkedList来说，get（int index）的时间复杂度是O(N)，因为每次查询都要遍历链表，由于是双向链表结结构，因此在遍历时，下标小于长度一半从前往后遍历，否则从后往前遍历，这样从理论上来说，时间可以节省一半。getFirst() 和 getLast()两个方法的时间复杂度是O(1)。因为first 和 last 在链表中是直接存储的。

插入元素时add（E e）方法默认将元素添加到链表的末尾，因此时间复杂度是O(1)。

如果指定位置插入元素 add(int index, E element)，需要先遍历这个元素，然后在插入，时间复杂度为O(N)

对于删除元素，remove(int index)，因为要考虑到查到元素，因此时间复杂度也是O(N)。

以上是通过时间复杂度对ArrayList和LinkedList的比较，需要注意的是，如果列表很大的时候，两个在内存上使用也是不同的，LinkedList 的每个元素都有更多开销，因为要存储上一个和下一个元素的地址，而ArrayList 没有这样的开销。但是ArrayList占用的内存是连续的，不论是否有那么多元素存储，内存都是已经占用了的。

5、说一下Vector 和 ArrayList 的区别？

Vector也是List接口的实现类之一，底层数据结构也是数组，同样具有查找快，增删满的特点。

Vector是线程安全的，源码中大量的方法都使用了synchronized关键字，这导致Vector的效率是比ArrayList要低的。

两者都采用了线性连续空间来存储，当需要扩容时，ArrayList默认扩容为原来的50%，而Vector默认扩容为原来的一倍。

//ArrayList
int newCapacity = oldCapacity + (oldCapacity >> 1);

// Vertor
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);

Vector可以设置capacityIncrement，从字面理解就是capacity容量，Increment增加，容量增长的参数，而ArrayList不可以。

6、ArrayList实现 RandomAccess接口有何作用？

RandomAccess接口其实是空的，什么都没有定义，这个接口其实只是一个标记接口，只要List 实现了这个接口，就能支持快速随机访问。 Collections中的 binarySearch() 方法中，会判断是否实现RandomAccess接口来实行查找方式：实现了此接口mid 是直接通过数据下标获得，而未实现则会采用迭代器来遍历。LinkedList没有实现这个接口，是因为他自身链表的属性不支持快速随机访问。

    public static 
    int binarySearch(List> list, T key) {
        if (list instanceof RandomAccess || list.size() midVal = list.get(mid);

// iteratorBinarySearch中通过迭代器找中间值
ListIterator> i = list.listIterator();
Comparable midVal = get(i, mid);
7、ArrayList的扩容机制

先看一下成员属性：默认容量10，两个默认空数组，用于存储元素的elementData，以及一个int类型的size用于记录list所存的容量。

    private static final int DEFAULT_CAPACITY = 10;

    private static final Object[] EMPTY_ELEMENTDATA = {};

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    transient Object[] elementData; // non-private to simplify nested class access

    private int size;

看一下ArraytList 的三个构造器，这里只关注无参构造器，可以看到，调用无参构造器的时候，返回的是一个空数组。因此，第一次添加数据的话，就会触发扩容。

    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

    public ArrayList(Collection c) {
        Object[] a = c.toArray();
        if ((size = a.length) != 0) {
            if (c.getClass() == ArrayList.class) {
                elementData = a;
            } else {
                elementData = Arrays.copyOf(a, size, Object[].class);
            }
        } else {
            // replace with empty array.
            elementData = EMPTY_ELEMENTDATA;
        }
    }

再来看看添加方法：

添加元素的时候，首先调用ensureCapacityInternal方法，并传值size+1，这个方法的作用是，首先判断当前数组是否为空，如果为空就将数组长度扩容为10，否则size+1 是否大于当前数组长度，如果大于，就进行扩容，否则就执行添加元素的 *** 作。

    public boolean add(E e) {
        // 添加元素前首先调用ensureCapacityInternal方法，并传值size+1
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

    private void ensureCapacityInternal(int minCapacity) {
        //调用了两个方法
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    // 计算容量，把当前数组 ，和size+1 传进去
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        // 如果当前数组为空，就返回max(DEFAULT_CAPACITY, minCapacity)，其实就是数组首次扩容，容量为10
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        // 不为空就返回 size+1
        return minCapacity;
    }

    // 
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        // 如果size+1 大于当前数组长度，就触发grow 方法。
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

最后看一下ArrayList扩容的核心方法grow()：新容量采用位运算的方式，计算后值为旧容量的1.5倍。

复制元素的方法调用了本地方法System.arraycopy()

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 首次扩容时，newCapacity计算后仍为0，因此赋值为10
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        // 如果newCapacity 大于 MAX_ARRAY_SIZE ，就调用 hugeCapacity方法
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

   
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

总结下来，ArrayList的扩容发生时机有两种：一个是初始化后第一次插入元素，第一次扩容长度为10 ，另外一个是当前数组已经满了，在往里插元素的时候触发扩容。 其中调用的各种方法都是用于判断是否需要扩容。

8、comparable和comparator的区别？

Comparable是java.lang包下的一个接口，是一个内部比较器，实现了Comparable接口的类可以和自己比较，内部有一个compareTo(Object o)方法,返回值是int类型的 ：

  • 正整数：比较者大于被比较者
  • 零 ：两者相等
  • 负整数：比较者小于被比较者

实现了Comparable接口的并重写了compareTo方法类的对象的列表或数组可以通过Collections.sort或Arrays.sort进行自动排序。

Comparator都是java.util包下的两个接口，可以称作是一个外部比较器；如果我们需要对某个类进行排序但是又不好修改这个类，那么就可以 定义一个实现了Comparator接口的类（类B），来作为类A的“比较器”,然后通过该比较器对类进行排序。

总结：实现两个接口都可以用来进行比较和排序，两者各有优缺点：Comparable 简单，但是需要修改源代码，Comparator虽然要另外实现一个比较器，但是不需要修改源码，并且在Comparator里面用户可以实现自己复杂统一的逻辑。

Comparable和Comparator区别（超详细对比分析）_只要酸菜不要鱼的博客-CSDN博客_comparable和comparator

9、介绍一下PriorityQueue？

PriorityQueue 优先队列，jdk1.5中被引入的，与Queue 的区别在于元素出队的顺序是和优先级相关的，即优先级高的元素总优先出队。

优先队列的使用：

public class TestPriorityQueue {

    public static void main(String[] args) {
        PriorityQueue priorityQueue = new PriorityQueue();

        priorityQueue.offer(new Customer(1, "张三"));
        priorityQueue.offer(new Customer(2, "李四"));
        priorityQueue.offer(new Customer(1, "王五"));
        priorityQueue.offer(new Customer(3, "张无"));
        priorityQueue.offer(new Customer(1, "张四"));

        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
        }
    }
}

class Customer implements Comparable {
    public int level;
    public String name;
    public Customer(int level, String name) {
        this.level = level;
        this.name = name;
    }
    @Override
    public String toString() {
        return "Customer{" + "level=" + level + ", name='" + name + '\'' + '}';
    }
    @Override
    public int compareTo(Customer o) {
        return o.level - level;
    }
}

Print:
Customer{level=3, name='张无'}
Customer{level=2, name='李四'}
Customer{level=1, name='张三'}
Customer{level=1, name='王五'}
Customer{level=1, name='张四'}

PriorityQueue内部存储数据使用的是数组，初始化容量为11，对于扩容，当长度比较小时，容量乘以2+2，长度较大的时候，每次增加50%，内部通过堆排序实现有序，插入和删除堆顶元素的时间复杂度为O(log n)；

【JDK源码】PriorityQueue源码分析_ΘLLΘ的博客-CSDN博客

 10、说一下HashSet的实现原理

底层使用HashMap来存储数据，初始化的时候会创建一个HashMap对象，HashSet的值不允许重复，因此HashSet 的值是作为HashMap的key来存储在HashMap中的。从源码中可以看出，HashSet 的方法都是调用HashMap的方法；

HashSet 有两个特点：无序性和唯一性（允许一个null值）；

public class HashSet  
          extends AbstractSet  
          implements Set, Cloneable, java.io.Serializable  
{  
static final long serialVersionUID = -5024744406713321676L;  

// 底层使用HashMap来保存HashSet中所有元素。  
private transient HashMap map;  
  
// 定义一个虚拟的Object对象作为HashMap的value，将此对象定义为static final。  
private static final Object PRESENT = new Object();  

//  默认的无参构造器，实际底层会初始化一个空的HashMap，并使用默认初始容量为16和加载因子0.75。 
public HashSet() {  
map = new HashMap();  
}  
// 返回此set中的元素的数量（set的容量）。 
public int size() {  
return map.size();  
}  
//  如果此set不包含任何元素，则返回true。 
public boolean isEmpty() {  
return map.isEmpty();  
}  
//  如果此set包含指定元素，则返回true。 
public boolean contains(Object o) {  
return map.containsKey(o);  
}  
public boolean add(E e) {  
       return map.put(e, PRESENT)==null;  
}  
public boolean remove(Object o) {  
return map.remove(o)==PRESENT;  
}  
//  从此set中移除所有元素。此调用返回后，该set将为空。 
//  
//  底层实际调用HashMap的clear方法清空Entry中所有元素。 
 
public void clear() {  
map.clear();  
}
11、HashMap的实现原理和底层数据结构是什么？

jdk1.7 是数组加链表

jdk1.8 以后是数组加链表加红黑树

改成数组加链表加红黑树 主要是为了提升 在hash冲突严重时的查找性能，因为使用链表查询的性能是 O(n)，而使用红黑树是 O(logn)。

对于插入情况：

        默认情况下使用的是链表，当同一个数组索引位置的节点在新增后超过8个，就会触发链表转换为红黑树。（当前，转换的前提是此时数组的长度大于等于64，如果数组长度小于64，因为此时数据量相对较少，会首先选择扩容）

对于移除情况：

        当同一个索引位置的节点在移除之后小于等于6个，并且该节点时红黑树节点时，会触发红黑树转化为链表节点。

链表转化成红黑树的阈值设置为8 是为什么呢？这个主要是和hashcode碰撞次数的泊松分布有关，主要是为了寻找一种时间和空间的平衡，负载因子为默认值0.75的情况下，单个槽内元素个数为8的概率小于百万分之一。

为什么不直接使用红黑树呢？因为红黑树的节点大小占用的内存大概是链表节点的两倍，节点比较少的时候，而红黑树的查找优势并不明显。

为什么红黑树转回链表的节点设置成6而不是8呢，因为如果节点在8个左右徘徊的时候，就会频繁的进行红黑树和链表的转换，这个是十分耗费性能的。

12、HashMap中有哪些重要的属性，他们都是用作什么？

存储元素的数组table，容量size，负载因子loadFactor，扩容阈值threshold

    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    static final int TREEIFY_THRESHOLD = 8;
    static final int UNTREEIFY_THRESHOLD = 6;
    static final int MIN_TREEIFY_CAPACITY = 64;

    transient Node[] table;    //存储元素的 table
    transient int size;  // 容量
    int threshold; // 扩容阈值 = 容量*负载因子
    final float loadFactor; //负载因子

    static class Node implements Map.Entry {
        final int hash;
        final K key;
        V value;
        Node next;
        ......
    }
13、HashMap 的默认初始容量是多少？HashMap 的容量有什么限制吗？

当我们新建一个HashMap对象时，是没有初始化table容量的，只有当插入第一个节点的时候，才会对table进行初始化，避免不必要的空间浪费，table初始化的长度默认是16，当然，也可以在新建HashMap的时候传入一个默认的初始容量，根据实际使用情况设置初始容量其实才是最合理的方案。

而负载因子的默认初始值是0.75，这个也是在时间和空间上权衡的结果，如果负载因子过高，就可增加hash冲突的概率，如果值比较低，虽然hash冲突会降低，但是浪费的空间也增大了。

HashMap的容量需要是2 的N次方，HashMap会根据我们传入的容量计算出一个大于等于该容量的最小的2 的N次方，例如传 7，容量为8，传 9，容量为16

我们看如下的计算代码：

首先解释一下：

  • >>>（无符号右移）：例如 a >>> b 指的是将 a 向右移动 b 指定的位数，右移后左边空出的位用零来填充，移出右边的位被丢弃： 101 >>>1 = 010   010>>>1 = 001
  • a |= b ，可以转成：a = a | b；-----> 101 | 010 = 111

通过五次移位和或 *** 作，我们能够通过n的最高位的1，拿到2个1 、4个1……,最终可以得到一个低位全是1的值，这个值的最高位1 取决于n的值的大小。然后返回的时候在加1，得到的就是一个会比n大的 2 的N次方。

int n = cap - 1 这个是什么意思呢？其实这个是考虑了传入的cap值本身就是2 的N次方的情况，如果cap 本事就是 2 的N次方，一通计算之后，返回的值还是他本身。

    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
14、HashMap的容量为什么必须是2 的N次方？

HashMap中计算元素所以的公式为 ： int index = (n - 1) & hash;  当n 为 2 的N次方的时候，n-1的低位就全是1，那么此时任何值 和n-1进行&运算，得到的结果就是该值的低N位，这样就达到了取模的效果。

比如hash值为15，n为4，即2的2次方 。15&（4-1）=（1111&0011）=0011=3 ，而15%4=3；其实可以理解发现，对于二进制数，能够整除table的，都在高位（位数大于等于3的都算高位），剩下的低位值和4-1进行与运算，结果就是hash与table取模得到的值。

这么设计的原因就是因为位运算的效率要比取模更高。

欢迎分享，转载请注明来源：内存溢出

原文地址: https://outofmemory.cn/langs/756337.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
code code 管理员组
0 0
上一篇 2022-04-30
下一篇 2022-04-30

发表评论

登录后才能评论

评论列表（0条）

保存