创建网站的免费软件国内,个人网站首页布局,南京网站推广排名,宿迁seo一、集合容器的概述
1. 什么是集合
集合框架#xff1a;用于存储数据的容器。 集合框架是为表示和操作集合而规定的一种统一的标准的体系结构。 任何集合框架都包含三大块内容#xff1a; 对外的接口、接口的实现和对集合运算的算 法。 接口#xff1a;表示集合的抽象数据…一、集合容器的概述
1. 什么是集合
集合框架用于存储数据的容器。 集合框架是为表示和操作集合而规定的一种统一的标准的体系结构。 任何集合框架都包含三大块内容 对外的接口、接口的实现和对集合运算的算 法。 接口表示集合的抽象数据类型。接口允许我们操作集合时不必关注具体实现 从而达到“多态”。在面 向对象编程语言中接口通常用来形成规范。 实现集合接口的具体实现是重用性很高的数据结构。 算法在一个实现了某个集合框架中的接口的对象身上完成某种有用的计算的方 法例如查找、排序 等。这些算法通常是多态的因为相同的方法可以在同一个 接口被多个类实现时有不同的表现。事实 上算法是可复用的函数。 它减少了程序设计的辛劳。
2. 集合的特点
集合的特点主要有如下两点 对象封装数据对象多了也需要存储。集合用于存储对象。 对象的个数确定可以使用数组对象的个数不确定的可以用集合。因 为集合是可变长度的
3. 集合和数组的区别
数组是固定长度的集合可变长度的。 数组可以存储基本数据类型也可以存储引用数据类型集合只能存储引用数据类型。 数组存储的元素必须是同一个数据类型集合存储的对象可以是不同 数据类型。
4. 常用的集合类有哪些
Map接口和Collection接口是所有集合框架的父接口 1. Collection接口的子接口包括Set接口和List接口 2. Map接口的实现类主要有HashMap、TreeMap、Hashtable、 ConcurrentHashMap以及 Properties等 3. Set接口的实现类主要有HashSet、TreeSet、LinkedHashSet等 4. List接口的实现类主要有ArrayList、LinkedList、Stack以及Vector等 5. ListSetMap三者的区别
List、Set、Map 是否继 承自Collection 接口List、Map、Set 三个接口存取 元素时各有什么 特点 Java 容器分为 Collection 和 Map 两大类Collection集合的子接口有Set、 List、Queue三种子接口。 我们比较常用的是Set、ListMap接口不是 collection的子接口。 Collection集合主要有List和Set两大接口 List一个有序元素存入集合的顺序和取出的顺序一致容器元素可以重 复可以插入多个 null元素元素都有索引。常用的实现类有 ArrayList、LinkedList 和 Vector。 Set一个无序存入和取出顺序有可能不一致容器不可以存储重复元素 只允许存入一个 null元素必须保证元素唯一性。Set 接口常用实现类是 HashSet、 LinkedHashSet 以及 TreeSet。 Map是一个键值对集合存储键、值和之间的映射。 Key无序唯一value 不要求有序允许重复。 Map没有继承于Collection接口从Map集合中检索元 素时只要给出键对象就会返回对应的值对 象。 Map 的常用实现类HashMap、TreeMap、HashTable、LinkedHashMap、 ConcurrentHashMap
6. 集合框架底层数据结构
Collection List Arraylist Object数组 Vector Object数组 LinkedList 双向循环链表 Set HashSet无序唯一基于 HashMap 实现的底层采用 HashMap 来保存元素 LinkedHashSet LinkedHashSet 继承与 HashSet并且其内部是通过 LinkedHashMap 来实现 的。有点类似于我们之前说的LinkedHashMap 其内部是基 于 Hashmap 实现一样不过还是有一 点点区别的。 TreeSet有序唯一 红黑树(自平衡的排序二叉树。) Map HashMap JDK1.8之前HashMap由数组链表组成的数组是HashMap的主 体链表则是主要 为了解决哈希冲突而存在的“拉链法”解决冲突.JDK1.8以后 在解决哈希冲突时有了较大的变化当链表长度大于阈值默认为8时将链表转 化为红黑树 以减少搜索时间 LinkedHashMapLinkedHashMap 继承自 HashMap所以它的底层仍然是 基于拉链式散列结 构即由数组和链表或红黑树组成。另外LinkedHashMap 在上面 结构的基础上增加了一条双向 链表使得上面的结构可以保持键值对的插入顺序。 同时通过对链表进行相应的操作实现了访问顺序相关逻辑。 HashTable 数组链表组成的数组是 HashMap 的主体链表则是主要为 了解决哈希冲突而存 在的 TreeMap 红黑树自平衡的排序二叉树
7. 哪些集合类是线程安全的
hashtable就比hashmap多了个线程安全
8. 怎么确保一个集合不能被修改
可以使用 Collections. unmodifiableCollection(Collection c) 方法来创建一个 只读集合这样改变集合 的任何操作都会抛出 Java. lang. UnsupportedOperationException 异常。 示例代码如下
List list new ArrayList();list.add(呀);Collection collection Collections.unmodifiableCollection(list);collection.add(hah);//运行时此行会报错
二、Collection接口
1. List接口
1.1 Iterator是什么
是迭代器Iterator 接口提供遍历任何 Collection 的接口。我们可以从一个 Collection 中使用迭代器方法来获取迭代器实例。迭代器允许调用者在迭代过程中移除元素
Iterator iterator list.iterator();while(iterator.hasNext()){System.out.println(iterator.next());}
Iterator 的特点是只能单向遍历但是更加安全因为它可以确保在当前遍历的集合元素被更改的时候就会抛出 ConcurrentModificationException 异常。
1.2 如何边遍历边移除 Collection 中的元素
边遍历边修改 Collection 的唯一正确方式是使用 Iterator.remove() 方法如下 IteratorInteger it list.iterator();while(it.hasNext()){it.remove();
}
一种 常见的错误代码如下
for(Integer i : list){list.remove(i)}
运行以上错误代码会报 ConcurrentModificationException 异常。这是因为当使用 foreach(for(Integeri : list)) 语句时会自动生成一个iterator 来遍历该 list但同时该 list 正在被 Iterator.remove() 修改。Java 一般不允许一个线程在遍历 Collection 时另一个线程修改它
1.3 Iterator 和 ListIterator 有什么区别
Iterator 可以遍历 Set 和 List 集合而 ListIterator 只能遍历 List。 Iterator 只能单向遍历而 ListIterator 可以双向遍历向前/后遍历。 ListIterator 实现 Iterator 接口然后添加了一些额外的功能比如添加一个元 素、替换一个元 素、获取前面或后面元素的索引位置。
1.4 集合的遍历方式
1. for 循环遍历基于计数器。在集合外部维护一个计数器然后依次读 取每一个位置的元素当读 取到后一个元素后停止。 2. 迭代器遍历Iterator。Iterator 是面向对象的一个设计模式目的是屏 蔽不同数据集合的特点 统一遍历集合的接口。Java 在 Collections 中支 持了 Iterator 模式。 3. foreach 循环遍历。foreach 内部也是采用了 Iterator 的方式实现使 用时不需要显式声明 Iterator 或计数器。优点是代码简洁不易出错缺 点是只能做简单的遍历不能在遍历过程中操 作数据集合例如删除、替 换。
最佳实践Java Collections 框架中提供了一个 RandomAccess 接口用来标 记 List 实现是否支持 Random Access。 如果一个数据集合实现了该接口就意味着它支持 Random Access按位置读 取元素的平均时间 复杂度为 O(1)如ArrayList。 如果没有实现该接口表示不支持 Random Access如LinkedList。 推荐的做法就是支持 Random Access 的列表可用 for 循环遍历否则建议 用 Iterator 或 foreach 遍历。
1.5 ArrayList的优缺点
ArrayList 底层以数组实现是一种随机访问模式。ArrayList 实现了 RandomAccess 接口因此查 找的时候非常快。 ArrayList 在顺序添加一个元素的时候非常方便
ArrayList 的缺点如下 删除元素的时候需要做一次元素复制操作。如果要复制的元素很多那么就会比较耗费性能。 插入元素的时候也需要做一次元素复制操作缺点同上。 ArrayList 比较适合顺序添加、随机访问的场景。
1.6 多线程场景下如何使用 ArrayList
ArrayList 不是线程安全的如果遇到多线程场景可以通过 Collections 的 synchronizedList 方法将其转换成线程安全的容器后再使用。例如像下面这样
1 ListString synchronizedList Collections.synchronizedList(list);
2 synchronizedList.add(aaa);
3 synchronizedList.add(bbb);
4
5 for (int i 0; i synchronizedList.size(); i) {
6 System.out.println(synchronizedList.get(i));
7 }
1.7 List 和 Set 的区别
List , Set 都是继承自Collection 接口 List 特点一个有序元素存入集合的顺序和取出的顺序一致容器元素可以重复可以插入多个null 元素元素都有索引。常用的实现类有 ArrayList、LinkedList 和 Vector
Set 特点一个无序存入和取出顺序有可能不一致容器不可以存储重复元素只允许存入一个null元素必须保证元素唯一性。Set 接口常用实现类是HashSet、LinkedHashSet 以及 TreeSet。 另外 List 支持for循环也就是通过下标来遍历也可以用迭代器但是set只能用迭代因为他无序无法用下标来取得想要的值。 Set和List对比 Set检索元素效率低下删除和插入效率高插入和删除不会引起元素位置改变。 List和数组类似List可以动态增长查找元素效率高插入删除元素效率低因为会引起其他元素位置改变
1.8 ArrayList扩容机制
ArrayList是一个数组结构的存储容器默认情况下数组的长度是10。
当然我们也可以在构建ArrayList对象的时候自己指定初始长度。
随着在程序里面不断的往ArrayList中添加数据当添加的数据达到10个的时候ArrayList就没有多余容量可以存储后续的数据。
这个时候ArrayList会自动触发扩容。
扩容的具体流程很简单
首先创建一个新的数组这个新数组的长度是原来数组长度的1.5倍。 然后使用Arrays.copyOf方法把老数组里面的数据拷贝到新的数组里面。 扩容完成后再把当前要添加的元素加入到新的数组里面从而完成动态扩容的过程。
1.9 为什么扩容因子是1.5
扩容的目的需要综合考虑这两种情况
扩容容量不能太小防止频繁扩容频繁申请内存空间 数组频繁复制
扩容容量不能太大需要充分利用空间避免浪费过多空间
而扩容固定容量很难决定到底取多少值合适取任何具体值都不太合适因为所需数据量往往由数组的客户端在具体应用场景决定。依赖于当前已经使用的量 * 系数 比较符合实际应用场景。
比如我现在已经用到一个数组100的容量接下来很可能会有这个数量级的数据需要插入。
为什么是1.5而不是1.21.251.8或者1.75
因为1.5 可以充分利用移位操作减少浮点数或者运算时间和运算次数。
ArrayList采用1.5倍扩容的主要原因是在平衡内存空间的利用率和性能之间。通过选择1.5倍的扩容可以在一定程度上减少频繁扩容的次数同时也避免了过多的内存浪费。这种折中的策略在大多数情况下都能够提供较好的性能和内存利用率
2. Set接口
2.1 HashSet 的实现原理
HashSet 是基于 HashMap 实现的HashSet的元素存放于HashMap的key上HashMap的value统一为PRESENT因为hashmap的key不可重复从而保证了hashset元素不可重复因此 HashSet 的实现比较简单相关 HashSet 的操作基本上都是直接调用底层HashMap 的相关方法来完成
解析不重复
向HashSet 中add ()元素时判断元素是否存在的依据不仅要比较hash值同时还要结合equles 方法比较。 HashSet 中的add ()方法会使用HashMap 的put()方法。
先看下面这个案例
public static void main(String[] args) {HashSetStudent students new HashSet();Student s1 new Student(张三, 10);Student s2 new Student(张三, 10);Student s3 new Student(张三, 10);students.add(s1);students.add(s2);students.add(s3);
System.out.println(students.size());for (Student student : students) {System.out.println(student);}
}
输出结果为
结果好像与我们设想的不太一致HashSet不是不允许元素重复吗这里却有三个重复的元素
因为hashset底层是基于hashmap实现的所以要仔细研究一下hashmap的add方法打开源码
(k p.key) key || (key ! null key.equals(k))
当我们调用一次add方法添加一个对象s1后再调用添加s2就会判断s1s2判断地址显然两个对象的地址值不同所以继续判断s1.equal(s2)但是我们没有重写对象的equals方法就会直接判断地址值即也是s1s2。两次判断都是false所以判断为新的元素就添加到hashmap中了
总结所以要实现去除重复数据是要重写对象的equals方法和hashcode方法也就是比较成员属性值是否是一样的
2.2 和equals
与equals的区别 1. 是判断两个变量或实例是不是指向同一个内存空间 equals是判断两个变量或实例所指向的内存 空间的值是不是相同 2. 是指对内存地址进行比较 equals()是对字符串的内容进行比较3. 指引用是否相同 equals()指的 是值是否相同
2.3 hashCode与equals
如果两个对象相等则hashcode一定也是相同的
两个对象相等,对两个equals方法返回true
两个对象有相同的hashcode值它们也不一定是相等的
2.4 为什么重写equals方法也要重写hashcode方法
equals和hashcode是用来协同判断两个对象是否相等的如果只重写了equals方法而不重写hashcode就会导致某些场景下程序异常
比如给Set集合中插入两个对象时因为这两个对象引用地址不同但是属性值都相同那么正常情况下不能重复插入才对。然而因为未重写hashcode所以导致判断hashcode不同因为hashcode是使用Object类的native的hashcode所以就认为它们是不同的对象这样就会将两个相同的对象都存储到Set集合中这显然是有问题的因为使用Set集合就是用来去重的结果这样一来存入了两个相同的对象与我们的期望不符
3. Map接口
3.1 hashmap的实现原理
HashMap概述 HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作 并允许使用null值和null键。此类不保证映射的顺序特别是它不保证该顺序恒久不变。 HashMap的数据结构 在Java编程语言中 基本的结构就是两种一个是数组另外一个是模拟指针 引用所有的数据结构都可以用这两个基本结构来构造的HashMap也不例外。HashMap实际上 是一个“链表散列”的数据结构即数组和链表的结合体。 HashMap 基于 Hash 算法实现的 1. 当我们往Hashmap中put元素时利用key的hashCode重新hash计算出当前对象的元素在数组中 的下标 2. 存储时如果出现hash值相同的key此时有两种情况。(1)如果key相 同则覆盖原始值(2)如果key不同出现冲突则将当前的key-value 放入链表中 3. 获取时直接找到hash值对应的下标在进一步判断key是否相同从而找到对应值。 4. 理解了以上过程就不难明白HashMap是如何解决hash冲突的问题核心就是使用了数组的存储方 式然后将冲突的key的对象放入链表中一旦发现冲突就在链表中做进一步的对比。 需要注意Jdk 1.8中对HashMap的实现做了优化当链表中的节点数据超过八个 之后该链表会转为红黑树来提高查询效率从原来的O(n)到O(logn)
3.2 HashMap在JDK1.7和JDK1.8中有哪些不同
在Java中保存数据有两种比较简单的数据结构数组和链表。数组的特点是寻址容易插入和删除困难链表的特点是寻址困难但插入和删除容易所以我们将数组和链表结合在一起发挥两者各自的优势使用一种叫做拉链法的方式可以解决哈希冲突
JDK1.8之前 JDK1.8之前采用的是拉链法。拉链法将链表和数组相结合。也就是说创建一个链表数组数组中每一 格就是一个链表。若遇到哈希冲突则将冲突的值加到链表中即可。JDK1.8之后 相比于之前的版本jdk1.8在解决哈希冲突时有了较大的变化当链表长度大于阈值默认为8时将链表转化为红黑树以减少搜索时间。JDK1.7 VS JDK1.8 比较 JDK1.8主要解决或优化了一下问题 1. resize 扩容优化 2. 引入了红黑树目的是避免单条链表过长而影响查询效率红黑树算法请参考 3. 解决了多线程死循环问题但仍是非线程安全的多线程时可能会造成数据丢失问题。 3.3 hashmap最全总结
hashmap面试题汇总
三、辅助工具类
1. Array(数组) 和 ArrayList 有何区别
Array 可以存储基本数据类型和对象ArrayList 只能存储对象。 Array 是指定固定大小的而 ArrayList 大小是自动扩展的。 Array 内置方法没有 ArrayList 多比如 addAll、removeAll、iteration 等方法只有 ArrayList 有。 对于基本类型数据集合使用自动装箱来减少编码工作量。但是当处理固定大小的基本数据类型的时候这种方式相对比较慢。
2. 如何实现 Array 和 List 之间的转换
Array 转 List Arrays. asList(array)
List 转 Array List 的 toArray() 方法。
3. Collection 和 Collections 有什么区别
java.util.Collection 是一个集合接口集合类的一个顶级接口。它提供了对集合对象进行基本操 作的通用接口方法。Collection接口在Java 类库中有很多具体的实现。Collection接口的意义是为 各种具体的集合提供了 大化的统一操作方式其直接继承接口有List与Set。 Collections则是集合类的一个工具类/帮助类其中提供了一系列静态方法用于对集合中元素进 行排序、搜索以及线程安全等各种操作。
4. Comparable和Comparator
java的比较器有两类分别是Comparable接口和Comparator接口。
在为对象数组进行排序时比较器的作用非常明显首先来讲解Comparable接口。
让需要进行排序的对象实现Comparable接口重写其中的compareTo(T o)方法在其中定义排序规则那么就可以直接调用java.util.Arrays.sort()来排序对象数组
Comparator“比较器” 使用这种策略来比较时如何进行比较和两个对象本身无关而是由第三者即比较器来完成的。第三方比较器类需要另外专门设计:只要实现Comparator接口任何一个类(对象)都可能成为一个“比较器”但比较器并不是比较自己的实例而是比较其它类的两个不同对象比较器在这里充当“仲裁者”的角色这也就是为什么compare()方法需要两个参数。 比如两个人要比较谁智商更高靠他们自身无法进行这时要借助一个比较器比如智商测试题。
Comparable和Comparator这两个接口和集合接口Collection本身无关但通常和集合内的元素有关因为集合的排序要用到这两个排序接口中的方法二选其一。一个类的多个实例要想实现排序必须实现Comparable或者提供相应的Comparator才能使用Collections.sort()进行排序
5. Vector,ArrayList, LinkedList的区别是什么
1. Vector、ArrayList都是以类似数组的形式存储在内存中LinkedList则以链表的形式进行存储。 2. List中的元素有序、允许有重复的元素Set中的元素无序、不允许有重复元素。 3. Vector线程同步ArrayList、LinkedList线程不同步。 4. LinkedList适合指定位置插入、删除操作不适合查找ArrayList、Vector适合查找不适合指定位置的插入、删除操作。 5. ArrayList在元素填满容器时会自动扩充容器大小的50%而Vector则是100%因此ArrayList更节省空间。
6. HashTable, HashMapTreeMap区别
1. HashTable线程同步HashMap非线程同步。 2. HashTable不允许键,值有空值HashMap允许键,值有空值。 3. HashTable使用EnumerationHashMap使用Iterator。 4. HashTable中hash数组的默认大小是11增加方式的old*21HashMap中hash数组的默认大小 是16增长方式一定是2的指数倍。 5. TreeMap能够把它保存的记录根据键排序默认是按升序排序。
7. HashMap的扩容因子
默认0.75也就是会浪费1/4的空间达到扩容因子时会将list扩容一倍0.75 是时间与空间一个平衡值
