当前位置: 首页>后端>正文

Java集合类总结(含面试常问问题)

对Java集合类和在面试中经常被问到的集合类的相关问题进行总结。记住这些,在面后端以及大数据岗位时,在被面到涉及Java集合相关问题的时候,基本是没什么问题了。


文章目录

  • Java集合类总结
  • 面试常问集合类问题
  • - 比较集合和数组的优缺点
  • - 写出Arrays类常用的6个方法并解释
  • - 写出Collections的6个方法并解释
  • - List,Set,Map区别
  • - Collection和Collections的区别
  • - 说出ArrayList,LinkedList,Vector的区别
  • - HashMap和Hashtable的区别
  • - Set里的元素是不能重复的,用什么方法来区分是否重复?是用==还是equals()?有何区别?
  • - 如何对一个对象排序,有几种方法
  • - 去掉Vector集合中重复的元素
  • - List转换
  • + HashMap原理等相关问题
  • - HashMap数据结构
  • - 重写hashCode和equals方法
  • - HashMap put原理
  • - HashMap get原理
  • - 负载因子
  • - 如果HashMap的大小超过了负载因子(load factor)定义的容量,怎么办?
  • - 你了解重新调整HashMap大小存在什么问题吗?
  • - 为什么String, Interger这样的wrapper类适合作为键?
  • - 我们可以使用自定义的对象作为键吗?
  • - 我们可以使用CocurrentHashMap来代替Hashtable吗?
  • - 使用匿名内部类初始化HashMap


Java集合类总结

Java集合类总结(含面试常问问题),Java集合类总结(含面试常问问题)_数组,第1张

Java集合类总结(含面试常问问题),Java集合类总结(含面试常问问题)_链表_02,第2张

  • Collection
  • List
    有序列表;可有重复元素
  • ArrayList
  • 内部由数组实现,数组是一块连续的内存单元
  • 增删元素慢,因为需要拷贝整个数组,但查询速度快
  • 0.5倍扩容 + 1。实例化无参构造函数默认初始化长度为10,如果增加的元素个数超过10,用Arrays.copyOf进行扩容。
  • LinkedList
  • 内部由链表实现,链表是不连续的内存单元(LinkedList的第一个单元和最后一个单元都会指向header,因此形成了一个双向的链表结构)
  • 增删元素快,因为只需要修改引用,但查询没ArrayList快
  • Vector
  • 内部由数组实现
  • 线程安全,可在多线程环境下使用,效率低于ArrayList
  • 扩容为原来的2倍
  • Set
    无序集合(但是对Set进行迭代,每次顺序都一致);不可重复。
  • HashSet
  • 无序
  • 可以放入null
  • LinkedHashSet
  • 保留插入顺序,迭代时按照添加顺序返回。
  • TreeSet
  • 是二叉树实现的
  • TreeSet实现Set接口和SortedSet接口
  • 它将元素按照顺序来存储,此顺序不是插入元素的顺序,而是元素的大小顺序。
  • 不可以存null
  • Queue
    队列,先进先出,Queue的实现类:LinkedList
  • Map
    key不可重复(插入相同的key会被覆盖),value可重复。
  • HashMap
  • 无序
  • 允许有null的键和值
  • 扩容机制:初始size=16,newsize = oldsize * 2。Map中元素总数超过Entry数组75%,触发扩容。size一定为2的n次幂,因为这样能使散列分布的更加均匀并且提高散列表的查询效率。
  • HashMap没有实现iterable接口,因此不能使用foreach进行遍历。但是它的keySet方法可以返回其key的集合。
  • LinkedHashMap
  • 保留元素插入顺序。迭代时按插入顺序返回。
  • 适用于在Map中插入、删除元素
  • TreeMap
  • 适用于按自然顺序(元素的key的大小)或自定义顺序遍历键(key)
  • 基于红黑树实现。TreeMap没有调优选项,因为该树总是处于平衡状态。
  • Hashtable
  • 不允许有null的键和值
  • 线程安全:实现线程安全的方式是,在修改数据时,锁住整个Hashtable,效率低于HashMap
  • 底层数组 + 链表实现
  • 扩容机制:初始size=11,newsize = oldsize * 2 + 1

面试常问集合类问题

- 比较集合和数组的优缺点

  • 数组类型是具有相同数据类型的数据集合;集合是多个对象的容器,可以将不同数据类型的多个对象组织在一起。
  • 数组不是动态的,一个数组一旦创建,它的容量就是固定的不能被修改,为了添加新的元素,需要创建一个容量更大的数组,并且将数据拷贝到新的数组中;集合是动态的,集合允许动态的添加,删除元素。当元素的数量超过集合的容量时,集合会自动扩容。
  • 数组是很多语言都支持的底层数据结构,性能上是最高的。

- 写出Arrays类常用的6个方法并解释

Arrays是数组的一个工具类
sort()对数组进行排序
binarySearch()通过二分搜索法进行查找,如果找到key,返回索引,否则返回负数。数组必须提前排好序。
copyOf(T[],length)复制数组中指定长度的元素
equals()判断两个数组元素是否相等
fill(T[],key)填充数组各个元素的值为key
asList()将数组转换为List
toString()转化为字符串

- 写出Collections的6个方法并解释

sort()对集合进行排序
shuffle()打乱集合中元素顺序
addAll()将一个集合添加到另一个集合中
max()判断集合中最大值
min()判断集合中最小值
copy()将一个集合中的元素复制到另一个集合中
fill()将一个集合中的元素全部替换成指定元素

- List,Set,Map区别

Java中的集合包括三大类:List,Set,Map。都处于java.util包中。List,Set,Map都是接口,都有各自的实现类。List的实现类主要有ArrayList,LinkedList,Set的实现类主要有HashSet,TreeSet,Map的实现类主要有HashMap,TreeMap。

List
存储:有序的、可重复的
访问:for,foreach,iterator
List中的对象按照索引位置排序,可以有重复对象,允许按照对象在集合中的索引位置检索对象,如通过list.get(i)的方式来获取集合中的元素。

Set
存储:无序的、不重复的
访问:foreach,iterator
Set中的对象不按特定方式排序,并且没有重复对象。但它的有些实现类能对集合中的对象按特定方式排序。可以通过实现java.util.Comparator接口自定义排序方式。

Map
存储:存储的是一对一对的映射“key=value”,key是无序的,不重复的,value可重复。
访问:可以map中的key转换为Set存储,迭代这个set,用map.get(key)获取value。也可以转换为entry对象,用迭代器迭代。
Map中每一个元素包含一个键对象和值对象,成对出现,键不能重复,值可以重复。

- Collection和Collections的区别

Collection是集合类的上级接口,继承于它的接口主要有List,Set。
Collections是针对集合类的一个帮助类,它提供了一系列静态方法,实现了集合的排序,搜索和线程安全等操作。

- 说出ArrayList,LinkedList,Vector的区别

ArrayList是最常用的List实现类,内部是通过数组实现的,它允许对元素进行快速随机访问。数组的缺点是每个元素之间不能有间隔,当数组大小不满足时需要增加存储能力,就要将已经有数组的数据复制到新的存储空间中。当从ArrayList的中间位置插入或者删除元素时,需要对数组进行复制、移动、代价比较高。因此,它适合随机查找和遍历,不适合插入和删除。扩容时为原来的1.5倍。
Vector与ArrayList一样,也是通过数组实现的,有序的,且都允许直接按序号索引元素。不同的是它支持线程的同步,即某一时刻只有一个线程能够写Vector,避免多线程同时写而引起的不一致性,但实现同步需要很高的花费,因此,访问它比访问ArrayList慢。扩容时为原来的2倍。
LinkedList是用链表结构存储数据的,很适合数据的动态插入和删除,随机访问和遍历速度比较慢。另外,他还提供了List接口中没有定义的方法,专门用于操作表头和表尾元素,可以当作堆栈、队列和双向队列使用。

- HashMap和Hashtable的区别

  • HashMap的键值都可以为null,Hashtable的键值都不可以为null;
  • HashMap线程不安全,Hashtable线程安全。
    一般情况下用HashMap。

- Set里的元素是不能重复的,用什么方法来区分是否重复?是用==还是equals()?有何区别?

用iterator()方法来区分重复与否。
equals方法(是String类从它的超类Object中继承的)被用来检测两个对象是否相等,即两个对象内容是否相等。
==用于比较引用和基本数据类型时具有不同的功能:
比较基本数据类型,如果两个值相等,则结果为true;
比较引用时,如果引用指向内存中同一对象,则结果为true。

- 如何对一个对象排序,有几种方法

把对象放入List集合中,用Collections工具类调用sort()方法进行排序,但是这个类必须实现Comparable接口才行。活着把对象放在Set中,用TreeSet实现类对集合直接排序。

- 去掉Vector集合中重复的元素

通过Vector.contains()方法判断是否包含该元素,如果没有包含就添加到新的集合中,适用于数据较小的情况下。

- List转换

// 将List转变为逗号分隔的字符串
List<String> cities = Arrays.asList("Milan", "London",  "New York")
String str = String.join(",", cities)
// 逗号分隔的字符串转list
List<String> cities = Arrays.asList("Milan", "London",  "New York")

+ HashMap原理等相关问题

参考链接

http://www.importnew.com/7099.html

http://www.oracle.com/technetwork/cn/articles/maps1-100947-zhs.html

- HashMap数据结构

Entry[]数组+链表的数据结构

- 重写hashCode和equals方法

Object类自带hashCode和equals方法,因此其所有的子类都具备这两个方法。但是这个两个方法的实现在通常情况下并不合理。hashCode方法应该能使key在散列表上均匀分布,并且有效避免散列冲突。equals方法也不能只比较对象的内存地址,应该根据实际的情况来实现。幸运的是,如果我们使用String来作为key的类型,那么就不用关心这个两个方法的实现,因为String类重写了Object类的这两个方法。

Java对于eqauls方法和hashCode方法是这样规定的:

  1. 如果两个对象相同(equals方法返回true),那么它们的hashCode值一定要相同;equals()方法不相等的两个对象,hashCode()有可能相等(哈希碰撞)。
  2. 如果两个对象的hashCode相同,它们并不一定相同。hashCode()不等,一定能推出equals()也不等。
  3. 当equals方法被重写时,通常有必要重写 hashCode 方法,以维护 hashCode方法的常规协定,该协定声明相等对象必须具有相等的哈希码。
  4. java中(引用类型)的==是比较两个对象在JVM中的地址。
/** JNI,调用底层其它语言实现 */  
public native int hashCode();  

/** 默认同==,直接比较对象 */  
public boolean equals(Object obj) {  
	return (this == obj);  
}

// String类中重写了equals方法,比较的是字符串值,看一下源码实现:
public boolean equals(Object anObject) {  
    if (this == anObject) {  
        return true;  
    }  
    if (anObject instanceof String) {  
        String anotherString = (String) anObject;  
        int n = value.length;  
        if (n == anotherString.value.length) {  
            char v1[] = value;  
            char v2[] = anotherString.value;  
            int i = 0;  
            // 逐个判断字符是否相等  
            while (n-- != 0) {  
                if (v1[i] != v2[i])  
                        return false;  
                i++;  
            }  
            return true;  
        }  
    }  
    return false;  
}

重写equals要满足几个条件:

  • 自反性:对于任何非空引用值 x,x.equals(x) 都应返回 true。
  • 对称性:对于任何非空引用值 x 和 y,当且仅当 y.equals(x) 返回 true 时,x.equals(y) 才应返回 true。
  • 传递性:对于任何非空引用值 x、y 和 z,如果 x.equals(y) 返回 true,并且 y.equals(z) 返回 true,那么 x.equals(z) 应返回 true。
  • 一致性:对于任何非空引用值 x 和 y,多次调用 x.equals(y) 始终返回 true 或始终返回 false,前提是对象上 equals 比较中所用的信息没有被修改。
    对于任何非空引用值 x,x.equals(null) 都应返回 false。

- HashMap put原理

其内通过一个哈希表管理所有元素。当我们调用put存值时,HashMap首先会调用K的hashCode方法,获取哈希码,通过哈希码快速找到某个存放位置,这个位置可以被称之为bucketIndex。理论上,hashCode可能存在冲突的情况,有个专业名词叫碰撞,当碰撞发生时,计算出的bucketIndex也是相同的,这时会取到bucketIndex位置已存储的元素,最终通过equals来比较,equals方法就是哈希码碰撞时才会执行的方法。HashMap通过hashCode和equals最终判断出K是否已存在:

  1. 如果bucketIndex位置上没有元素 ,则存放新的键值对<K, V>到bucketIndex位置。
  2. 如果已存在,对象相同,则使用新V值替换旧V值,并返回旧V值。
  3. 如果bucketIndex位置上有元素了,也就是hashCode相同,但对象或equals不同,也会将新元素放到这个位置,将新元素加入链表表头,通过next指向原有的元素。
// 源码
public V put(K key, V value) {  
    // 处理key为null,HashMap允许key和value为null  
    if (key == null)  
        return putForNullKey(value
    // 得到key的哈希码  
    int hash = hash(key);  
    // 通过哈希码计算出bucketIndex  
    int i = indexFor(hash, table.length);  
    // 取出bucketIndex位置上的元素,并循环单链表,判断key是否已存在  
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {  
        Object k;  
        // 哈希码相同并且对象相同时  
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  
            // 新值替换旧值,并返回旧值  
            V oldValue = e.value;  
            e.value = value;  
            e.recordAccess(this);  
            return oldValue;  
        }  
    }  
  
    // key不存在时,加入新元素  
    modCount++;  
    addEntry(hash, key, value, i);  
    return null;  
}

- HashMap get原理

  1. 当 HashMap 的每个 bucket 里存储的 Entry 只是单个 Entry ——也就是没有通过指针产生 Entry 链时,此时的 HashMap 具有最好的性能:当程序通过 key 取出对应 value 时,系统只要先计算出该 key 的 hashCode() 返回值,在根据该 hashCode 返回值找出该 key 在 table 数组中的索引,然后取出该索引处的 Entry,最后返回该 key 对应的 value 即可。
  2. 在发生“Hash 冲突”的情况下,单个 bucket 里存储的不是一个 Entry,而是一个 Entry 链,系统只能必须按顺序遍历每个 Entry,直到找到想搜索的 Entry 为止 。
// 源码
public V get(Object key)   
{   
	 // 如果 key 是 null,调用 getForNullKey 取出对应的 value   
	 if (key == null)   
	     return getForNullKey();   
	 // 根据该 key 的 hashCode 值计算它的 hash 码  
	 int hash = hash(key.hashCode());   
	 // 直接取出 table 数组中指定索引处的值,  
	 for (Entry<K,V> e = table[indexFor(hash, table.length)];   
	     e != null;   
	     // 搜索该 Entry 链的下一个 Entr   
	     e = e.next)         // ①  
	 {   
	     Object k;   
	     // 如果该 Entry 的 key 与被搜索 key 相同  
	     if (e.hash == hash && ((k = e.key) == key   
	         || key.equals(k)))   
	         return e.value;   
	 }   
	 return null;   
}

- 负载因子

当创建 HashMap 时,有一个默认的负载因子(load factor),其默认值为0.75,这是时间和空间成本上一种折衷:

  • 增大负载因子可以减少 Hash 表(就是那个 Entry 数组)所占用的内存空间,但会增加查询数据的时间开销,而查询是最频繁的的操作(HashMap 的 get() 与 put() 方法都要用到查询);如果程序比较关心空间开销、内存比较紧张,可以适当地增加负载因子
  • 减小负载因子会提高数据查询的性能,但会增加 Hash 表所占用的内存空间。如果程序比较关心时间开销,内存比较宽裕则可以适当的减少负载因子

如果开始就知道 HashMap 会保存多个 key-value 对,可以在创建时就使用较大的初始化容量,如果 HashMap 中 Entry 的数量一直不会超过极限容量(capacity * load factor),HashMap 就无需调用 resize() 方法重新分配 table 数组,从而保证较好的性能。当然,开始就将初始容量设置太高可能会浪费空间(系统需要创建一个长度为 capacity 的 Entry 数组),因此创建 HashMap 时初始化容量设置也需要小心对待。

- 如果HashMap的大小超过了负载因子(load factor)定义的容量,怎么办?

默认的负载因子大小为0.75,也就是说,当一个map填满了75%的bucket时候,和其它集合类(如ArrayList等)一样,将会创建原来HashMap大小的两倍的bucket数组,来重新调整map的大小,并将原来的对象放入新的bucket数组中。这个过程叫作rehashing,因为它调用hash方法找到新的bucket位置。

- 你了解重新调整HashMap大小存在什么问题吗?

当多线程的情况下,可能产生条件竞争(race condition)。
当重新调整HashMap大小的时候,确实存在条件竞争,因为如果两个线程都发现HashMap需要重新调整大小了,它们会同时试着调整大小。在调整大小的过程中,存储在链表中的元素的次序会反过来,因为移动到新的bucket位置的时候,HashMap并不会将元素放在链表的尾部,而是放在头部,这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了,那么就死循环了。这个时候,你可以质问面试官,为什么这么奇怪,要在多线程的环境下使用HashMap呢?)

处理碰撞时 JDK7用的是链表 , JDK8 貌似就是利用红黑树了,这样查找效率会提高很多 。
所以面试的时候都会问一下如果list太长会怎么处理。一般会说是不是产生hashcode的算法不够好。那就继续问怎么样的算是好的hashcode生成算法;如果能答出来用红黑树,就会再问红黑树的问题。所以这道题差不多就够面很久了。

- 为什么String, Interger这样的wrapper类适合作为键?

String, Interger这样的wrapper类作为HashMap的键是再适合不过了,而且String最为常用。因为String是不可变的,也是final的,而且已经重写了equals()和hashCode()方法了。其他的wrapper类也有这个特点。不可变性是必要的,因为为了要计算hashCode(),就要防止键值改变,如果键值在放入时和获取时返回不同的hashcode的话,那么就不能从HashMap中找到你想要的对象。不可变性还有其他的优点如线程安全。如果你可以仅仅通过将某个field声明成final就能保证hashCode是不变的,那么请这么做吧。因为获取对象的时候要用到equals()和hashCode()方法,那么键对象正确的重写这两个方法是非常重要的。如果两个不相等的对象返回不同的hashcode的话,那么碰撞的几率就会小些,这样就能提高HashMap的性能。

- 我们可以使用自定义的对象作为键吗?

这是前一个问题的延伸。当然你可能使用任何对象作为键,只要它遵守了equals()和hashCode()方法的定义规则,并且当对象插入到Map中之后将不会再改变了。如果这个自定义对象时不可变的,那么它已经满足了作为键的条件,因为当它创建之后就已经不能改变了。

- 我们可以使用CocurrentHashMap来代替Hashtable吗?

这是另外一个很热门的面试题,因为ConcurrentHashMap越来越多人用了。我们知道Hashtable是synchronized的,但是ConcurrentHashMap同步性能更好,因为它仅仅根据同步级别对map的一部分进行上锁。ConcurrentHashMap当然可以代替HashTable,但是HashTable提供更强的线程安全性。看看这篇博客查看Hashtable和ConcurrentHashMap的区别。

底层实现:数组 + 链表

扩容:段内扩容(段内元素超过该段对应Entry数组长度的75%触发扩容,不会对整个Map进行扩容),插入前检测需不需要扩容,有效避免无效扩容)

线程安全:Hashtable的synchronized是针对整张Hash表的,即每次锁住整张表让线程独占;锁分离技术:ConcurrentHashMap允许多个修改操作并发进行,其关键在于使用了锁分离技术。

- 使用匿名内部类初始化HashMap

Map map = new HashMap(){
{
        put("name", "张三")
        put("age", "24")
        put("sex", "man")
    }
}
System.out.println(map.get("name"))



https://www.xamrdz.com/backend/3vf1926486.html

相关文章: