11.集合
- 集合框架的描述
一.集合框架的概述
1.集合,数组都是对多个数据进行存储操作的结构,简称Java容器
说明: 此时的存储,主要指的是内存层面的存储,不涉及到(硬盘)持久化的存储(.txt,.jpg,,avi,数据库中)
2.1.数组在存储多个数据方面的特点:
一旦初始化以后,其长度就确定了.
数组一旦定义好,其元素的类型也就确定了.也就只能操作指定类型的数据了.
比如: String[] arr;int[] arr1; Ojbect[] arr2; 还能往父类中装子类数据
2.2.数组在存储多个数据方面的缺点:
一旦初始化后,其长度就不可修改
数组中提供的方法非常有限,对于添加,删除,插入数据等操作,非常不便,同时效率不高
获取数组中实际元素的个数的需求,数组没有现成的属性或方法可用
数组存储数据的特点: 有序,可重复.对于无序,不可重复的需求,不能满足
- 集合框架及涉及到的api
二.集合框架
Collection接口: 单列集合,用来存储一个一个的对象
List接口: 存储有序的,可重复的数据. --> "动态"数组
ArrayList,LinkedList,Vector
Set接口: 存储无序的,不可重复的数据 --> 高中的"集合"
HashSet,LinkedHashedSet,TreeSet
Map接口: 双列集合,用来存储一对(key-value)一对的数据 --> 高中函数: y = f(x)
HashMap,LinkedHashMap,TreeMap,Hashtable,Properties
- Collection接口的常用方法
结论:
向Collection接口的实现类的对象中添加数据obj时,要求obj所在类要重写equals()
public class CollectionTest {
// 修改了原集合
@Test
public void test4(){
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(new Person("jerry", 20));
coll.add(new String("tom"));
coll.add(false);
//7.hashcode():返回当前对象的哈希值,因为方法定义在Object类中,所有对象都可以调该方法
System.out.println(coll.hashCode());
// 8.集合转化为数组: toArray():
Object[] arr = coll.toArray();// 返回Object类型数组
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
// 拓展: 数组 --> 集合: 调用Arrays类的静态方法asList()
// asList的形参是可变参数,相当于数组,所以也可以传入数组,返回具体的List,是List肯定是Collection,因为数组对应的集合就是List
List<String> list = Arrays.asList(new String[]{"AA", "BB", "CC"});
System.out.println(list);
List arr1 = Arrays.asList(new int[]{1, 2, 3});// 集合不能存基本数据类型,集合把这个整个当成一个参数了
System.out.println(arr1.size());// 1
List arr2 = Arrays.asList(123,456);
System.out.println(arr2.size());// 2
// iterator(): 返回Iterator接口的实例,用于遍历集合元素.放在IteratorTest.java中测试
}
@Test
public void test3(){
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(new Person("jerry", 20));
coll.add(new String("tom"));
coll.add(false);
// 5.retainAll(Collection coll): 交集,获取当前集合和coll1集合的交集,并修改当前集合;保留一样的,删除不一样的
// 保留两个集合都有的元素
// Collection coll1 = Arrays.asList(123, 456, 789);
// coll.retainAll(coll1);
System.out.println(coll);
// 6.equals(Object obj): 要想返回true,需要当前集合和形参集合的元素都相同,关于有没有序看实现类是谁
// 集合与集合比较,并且集合元素都一样才能退返回true,一个一个元素比较,也会涉及到相关元素所在类equals方法的调用
// coll1元素顺序改变,返回false,因为ArrayList实现类是有序的
Collection coll1 = new ArrayList();
coll1.add(123);
coll1.add(456);
coll1.add(new Person("jerry", 20));
coll1.add(new String("tom"));
coll1.add(false);
System.out.println(coll.equals(coll1));// true
}
@Test
public void test2(){
//3.remove(Object obj): 从当前集合中移除obj元素,返回布尔值
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(new Person("jerry", 20));
coll.add(new String("tom"));
coll.add(false);
coll.remove(123);// 也调用equals方法
System.out.println(coll);
coll.remove(new Person("jerry", 20));// Person类重写了equals方法移除成功
// 4.removeAll(Collection coll1): 差集,从当前集合中移除coll1中所有的元素, 该方法调了coll1集合中元素的equals方法
// 移除两个集合都有的元素
Collection coll1 = Arrays.asList(123, 456);
coll.removeAll(coll1);
System.out.println(coll);
}
@Test
public void test1(){
Collection coll = new ArrayList();
coll.add(123);// 传入包装类对象,自动装箱成Integer类
coll.add(456);
coll.add(new Person("jerry", 20));// contains方法判断得到结果后终止调用equals方法
coll.add(new String("tom"));
coll.add(false);// Boolean类型
// 自定义类型
/*Person p = new Person("jerry", 20);
coll.add(p);*/
// 1.contains(Object e): 判断当前集合中是否包含obj(对象)
// 在判断时会调用obj对象所在类的equals方法
boolean contains = coll.contains(123);
System.out.println(contains);// true
System.out.println(coll.contains(new String("tom")));// true;因为String重写了equals方法,比的是内容
// System.out.println(coll.contains(p));// true 比较用 == 或 equals都是true,同一个引用
System.out.println(coll.contains(new Person("jerry", 20)));// false-->true,因为比内容的前提是Person类自己重写了equals方法,没有则调用Object的
//2.containsAll(Collection coll1): 判断形参coll1中的所有元素是否都存在于coll集合中.
Collection coll1 = Arrays.asList(123,456);// 工具类中的方法,返回是ArrayList类型对象,
System.out.println(coll.containsAll(coll1));// true
}
@Test
public void test(){
Collection coll = new ArrayList();// 用ArrayList作为他的子接口的实现类进行测试
// 1.add(Ojbect e): 将元素e添加到集合coll中
coll.add("AA");
coll.add("BB");
coll.add(123);// 基本数据类型,自动装箱,转换包装类了
coll.add(new Date());
// 2.size(): 获取添加的元素个数
System.out.println(coll.size());// 4
// 3.addAll(Collection coll1): 将coll1集合中的元素添加到当前的集合中
Collection coll1 = new ArrayList();
coll1.add(456);
coll1.add("CC");
coll.add(coll1);
System.out.println(coll.size());// 6
System.out.println(coll.toString());// toString是ArrayList实现类重写过的
// clear(): 清空集合元素
coll.clear();
// isEmpty(): 判断当前集合是否为空(元素个数)
System.out.println(coll.isEmpty());// false
}
}
11.3.迭代器Iterator接口
集合元素的遍历操作,使用迭代器Iterator接口
1.内部方法: hasNext()和next()
2.集合对象每次调用iterator()方法都得到一个全新的迭代器对象,默认游标都在集合的第一个元素之前
3.内部定义了remove(),可以在遍历的时候,删除集合中的元素.此方法不同于Collection集合直接调用remove()
- 使用iterator遍历Collection
@Test
public void test1(){
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(new Person("jerry", 20));
coll.add(new String("tom"));
coll.add(false);
// 获取迭代器对象
// 方式一:
Iterator iterator = coll.iterator();// 他是迭代器不是容器,只用于遍历
/*System.out.println(iterator.next());
System.out.println(iterator.next());
System.out.println(iterator.next());
System.out.println(iterator.next());
System.out.println(iterator.next());
// 报异常 NoSuchElementException
System.out.println(iterator.next());*/
// 方式二: 不推荐
/*for (int i = 0; i < coll.size(); i++) {
System.out.println(iterator.next());
}*/
// 方式三: 推荐
// hasNext():判断是否还有下一个元素
while (iterator.hasNext()){
// next(): 指针下移,将下移以后集合位置上的元素返回
System.out.println(iterator.next());
}
}
- 迭代器iterator的执行原理
image.png
- iterator遍历集合的错误写法
@Test
public void test2(){
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(new Person("jerry", 20));
coll.add(new String("tom"));
coll.add(false);
// 错误方式一: 间隔输出,并且报异常
/* Iterator iterator = coll.iterator();
while (iterator.next() != null){
System.out.println(iterator.next());
}*/
// 错误方式二: 集合对象每次调用iterator()方法都得到一个全新的迭代器对象,默认游标都在集合的第一个元素之前
while (coll.iterator().hasNext()){// 每调一次iterator方法,都返回一个迭代器对象,新指针就会在开头
System.out.println(coll.iterator().next());// 始终输出第一个元素
}
}
- 迭代器iterator remove()的使用
// 测试Iterator中的remove(): 删除当前指针指向的集合元素
@Test
public void test3(){
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(new Person("jerry", 20));
coll.add(new String("tom"));
coll.add(false);
// 删除集合中"tom"
Iterator iterator = coll.iterator();
while (iterator.hasNext()){
// iterator.remove();// 报异常
// next值用Object类型的对象接收,因为返回值是Object类型
Object obj = iterator.next();
// 先写tom健壮性更好一些
if ("tom".equals(obj)){// 如果obj存null的话,拿obj调就空指针了
iterator.remove();// 移除当前数据
iterator.remove();// 报异常
}
}
// 重新遍历要重新获取迭代器对象
iterator = coll.iterator();
while (iterator.hasNext()){
System.out.println(iterator.next());
}
}
- 新特性foreach循环遍历
public class ForTest {
@Test
public void test1(){
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(new Person("jerry", 20));
coll.add(new String("tom"));
coll.add(false);
// for (集合元素类型 局部变量 : 集合对象(变量))
// 遍历集合:把集合里的每个元素赋给obj,输出
// 内部仍然调用了迭代器
for (Object obj : coll){// obj:局部变量,相当于int i,可随意指定
System.out.println(obj);
}
}
@Test
public void test2(){
int[] arr = new int[]{1, 2, 3, 4, 5, 6};
// for(数组元素的类型 局部变量 : 数组对象)
for (int i : arr) {
System.out.println(i);
}
}
@Test
public void test3(){
String[] arr = new String[]{"MM", "MM", "MM", "MM"};
// 方式一: 普通for赋值
for (int i = 0; i < arr.length; i++) {
arr[i] = "GG";// 用本身数组元素做修改,用字面量修改,原数组在常量池里重新指向新空间区域
}
// 方式二: 增强for循环
for (String s : arr) {
s = "GG";// 把原数组元素取出赋值给新设定的局部变量s,在s里修改,arr的元素不变
}
for (int i = 0; i < arr.length; i++) {
// 普通for循环输出GG,增强for循环输出MM
System.out.println(arr[i]);
}
}
}
11.4.Collection的子接口之一: List接口
Collection接口: 单列集合,用来存储一个一个的对象
List接口: 存储有序的,可重复的数据. --> "动态"数组,替换原有的数组,本质替换的是List接口
ArrayList: 作为List接口的主要实现类: 线程不安全的,效率高;底层用Object[] elementData存储封装
LinkedList: 对于频繁的插入,删除操作,用此类效率比ArrayList高;底层用双向链表存储
Vector: 作为List接口的古老实现类: 线程安全的,效率低;底层用Object[] elementData存储
2.ArrayList的源码分析:
2.1.jdk7情况下
ArrayList list = new ArrayList();// 底层创建了长度是10的Object[]数组elementData
list.add(123);// elementData[0] = new Integer(123);
....
list.add(11);// 如果此次的添加导致底层elementData数组容量不够,则扩容.
默认情况下,扩容(新造一个数组)为原来的容量的1.5倍(10>>1 = 5,10+5=15,15/10 = 1.5倍),同时要将原有的数组中的数据复制到新的数组中,这个新数组就作为目前的elementData的新值完成扩容
结论: 知道ArrayList中基本要放多少数据,建议开发中用带参构造器: ArrayList list = new ArrayList(int capacity),因为底层不用给你扩容了,提高效率
2.2.jdk8中的ArrayList的变化:
ArrayList list = new ArrayList();// 底层创建了长度是10的Object[]数组elementData初始化为{},并没有创建长度
list.add(123);// 第一次调用add()时,底层才创建了长度10的数组,并将数据123天假到elementData[0]
...
后续的添加和扩容操作与jdk7 无异
2.3.小结: jdk7中的ArrayList的对象创建类似于单例的饿汉式,而jdk8中的ArrayList的对象的创建类似于单例的懒汉式,延迟了数组的创建,节省内存.
3.LinkedList的源码分析:
LinkedList list new LinkedList();// 内部声明了Node类型的first和last属性,默认值为null
list.add(123);//将123封装到Node中,创建了Node对象
其中,Node定义为: 体现了LinkedList的双向链表的说法
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
4.Vector的源码分析: jdk7和jdk8中通过Vector()构造器创建对象时,底层都创建了长度为10的数组.
在扩容方面,默认扩容为原来的数组长度的2倍.
总结常用方法
增: add(Object obj)
删: remove(int index)/remove(Object obj)
改: set(index, Object ele)
查: get(int index)
插: add(int index,Object ele)
面试题: ArrayList,LinkedList,Vector三者的异同?
同: 三个类都是实现了List接口,存储数据的特点相同他: 存储有序的,可重复的数据
不同: 见上
public class ListTest {
@Test
public void test3(){
ArrayList list = new ArrayList();
list.add(123);
list.add(456);
list.add("AA");
list.add(new Person("tom",20));
list.add(456);
//方式一: Iterator迭代器方式
Iterator iterator = list.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
System.out.println("================");
// 方式二: 增强for循环
for (Object obj : list){
System.out.println(obj);
}
System.out.println("=================");
// 方式三: 普通for循环
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
}
@Test
public void test2(){
ArrayList list = new ArrayList();
list.add(123);
list.add(456);
list.add("AA");
list.add(new Person("tom",20));
list.add(456);
// int indexOf(Object obj): 返回obj在集合中首次出现的位置.如不存在,返回-1
int index = list.indexOf(456);
System.out.println(index);// 1
System.out.println(list.lastIndexOf(456));// 4,如不存在返回-1
// Object remove(int index): 移除指定index位置的元素,并返回被移除的元素, 是该方法为重载方法,不是重写,因为形参不一样
Object obj = list.remove(0);
System.out.println(obj);// 123
System.out.println(list);
// Object set(index, Object ele): 把指定index位置的元素改为ele
list.set(1,"CC");
System.out.println(list);
// List subList(int fromIndex, int toIndex):返回从fromIndex到toIndex位置的左闭右开子集合,相当于提供当前list的子list
List subList = list.subList(2,4);
System.out.println(subList);
System.out.println(list);// 原list不变
}
@Test
public void test1(){
ArrayList list = new ArrayList();
list.add(123);
list.add(456);
list.add("AA");
list.add(new Person("tom",20));
list.add(456);
System.out.println(list);
// void add(int index,Object ele): 在index位置插入ele元素
list.add(1, "BB");
System.out.println(list);
// boolean addAll(int index, Collection eles):从index位置开始将eles中的所有元素添加进来
// List list1 = Arrays.asList(new int[]{1, 2, 3});// 整个参数被当做一个整体
List list1 = Arrays.asList(1,2,3);// 自动装箱作为包装类传入
//list.addAll(list1);// 把list1的所有元素当做一个整体参数
list.addAll(list1);// 把元素都加到集合中
System.out.println(list);// 打印元素个数
// Object get(int index): 获取index位置的元素
System.out.println(list.get(0));//123
}
}
11.5.Collection子接口之二: Set接口
- Set接口的实现类的对比
- Set接口的框架:
Collection接口: 单列集合,用来存储一个一个的对象
Set接口: 存储无序的,不可重复的数据 --> 高中的"集合"
HashSet: 作为Set接口的主要实现类: 线程不安全的;可以存储null值
LinkedHashedSet: 作为HashSet的子类;遍历其内部数据时,可以按照添加的顺序遍历,为频繁遍历操作准备的一个类
对于频繁的遍历操作,LinkedHashSet效率高于HashSet
TreeSet: 可以按照添加对象的指定属性,进行排序.
- Set的无序性和不可重复性的理解
1.Set接口中没有额外定义新的方法,用的都是Collection中声明过的方法.Set无序也就没有索引了,也就没有新的方法
Set接口: 存储无序的,不可重复的数据
1.无序性: 不等于随机性,有固定顺序.存储的数据在底层数组中并非按照数组索引的顺序添加,而是根据数据的哈希值决定的.
指添加的时候,存放的位置不是一个挨一个的顺序放的
2.不可重复性: 保证添加的元素按照equals()判断时,不能返回true.即: 相同的元素只能添加一个
@Test
public void test1(){
// 实例化HashSet实现类
// 哈希值用对象属性来计算的
Set set = new HashSet();
set.add(456);
set.add(123);
set.add("AA");
set.add("CC");
set.add(new User("tom",20));
set.add(new User("tom",20));
set.add(129);
Iterator iterator = set.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
}
public class User implements Comparable{
private String name;
private int age;
@Override
public String toString() {
return "User{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
public User(String name, int age) {
this.name = name;
this.age = age;
}
public User() {
}
@Override
public boolean equals(Object o) {
System.out.println("User equals()...");
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
User user = (User) o;
if (age != user.age) return false;
return name != null ? name.equals(user.name) : user.name == null;
}
// 如果User类没有重写hashcode方法,则会调用Object类的hashcode方法,而Object中的方法是随机计算的,所以就算是相同元素都会计算出不同的哈希值
@Override
public int hashCode() {
int result = name != null ? name.hashCode() : 0;
result = 31 * result + age;
return result;
}
// 重写排序方法,按照姓名从大到小排列,年龄从小到大排列
@Override
public int compareTo(Object o) {
if (o instanceof User){
User user = (User) o;
int compare = -this.name.compareTo(user.name);
if (compare != 0){
return compare;
}else{
return Integer.compare(this.age, user.age);
}
}else{
throw new RuntimeException("输入类型不匹配");
}
}
}
- HashSet中元素添加的过程
image.png
二.添加元素的过程: 以HashSet为例:
向HashSet中添加元素a,首先调用元素a所在类的hashcode方法,计算元素a的哈希值,
此哈希值接着通过某种算法计算出在HashSet底层数组中的存放位置(即为: 索引位置),判断
数组此位置上是否已经有元素:
如果此位置上没有其他元素,则元素a添加成功. --> 情况1
如果此位置上有其他元素b(或以链表形式存在的多个元素), 则比较元素a与元素b的hash值:
如果hash值不相同,则元素a添加成功. --> 情况2
如果hash值相同,进而需要调用元素a所在类的equals方法:
equals()返回true,元素a添加失败
equals()返回false,则元素a添加成功. --> 情况3
对于添加成功的情况2和情况3而言: 元素a 与已经存在指定索引位置上数据以链表的方式存储.
jdk7: 元素a放到数组中,指向原来的元素.(头插法)
jdk8: 原来的元素在数组中,指向元素a.(尾插法)
总结: 七上八下
HashSet底层: 数组+链表的结构
- 关于hashcode()和equals()的重写
2.要求:
①向Set中添加的数据,其所在的类一定要重写hashcode方法和equals方法
②重写的hashcode方法和equals方法尽可能保持一致性,相等的对象必须具有相等的散列码(哈希值)
如果两个对象equals方法比较的属性不一样,算出的哈希值不要一样,如果比较的equals方法的属性相同,让他们算出的哈希值也一样
重写两个方法的小技巧: 对象中用作equals()方法比较的Field,都应该用来计算hashcode
image.png
- LinkedHashSet的使用
// LinkedHashSet的使用
//LinkedHashSet作为HashSet的子类,在添加数据的同时,每个数据还维护了两个引用,记录此数据的前一个数据和后一个数据.
// 优点: 对于频繁的遍历操作,LinkedHashSet效率高于HashSet
// 缺点: 空间内存大
@Test
public void test2(){
Set set = new LinkedHashSet();
set.add(456);
set.add(123);
set.add("AA");
set.add("CC");
set.add(new User("tom",20));
set.add(new User("tom",20));
set.add(129);
Iterator iterator = set.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
}
image.png
- TreeSet的使用
向TreeSet中添加的数据,要求是相同类的对象
两种排序方式: Java比较器: 自然排序(实现Comparable接口) 和 定制排序
自然排序中,比较两个对象是否相同的标准为: compareTo()返回0,不再是用equals().言外之意,TreeSet不能放相同的数据
定制排序中,比较两个对象是否相同的标准为: compare()返回0,不再是用equals()
image.png
- TreeSet的自然排序
@Test
public void test1(){
TreeSet set = new TreeSet();
//失败: 不能添加不同类的对象
/* set.add(123);
set.add(456);
set.add("AA");
set.add(new User("tom",12));*/
// 举例一: Integer类型排序,包装类已经重写过compareTo方法,默认从小到大排序
/*set.add(34);
set.add(-35);
set.add(12);
set.add(6);*/
// 举例二: 自定义类排序,直接运行报错,没有实现Comparable接口,
// 自定义类要实现Comparable接口并且重写compareTo方法
set.add(new User("Tom", 12));
set.add(new User("Tom", 12));
set.add(new User("Jerry", 32));
set.add(new User("Jim", 65));
set.add(new User("Jack", 33));
// 下面这一条数据没有输出,因为在User类中通过compareTo方法比较name属性的时候,判断这两个对象是一样的,
//相当于在User类里return -this.name.compareTo(user.name);语句中的compareTo方法中返回了0,所以两个对象相等
// 在TreeSet中,判断两个对象相同不相同的标准不再是equals方法,不同于HashSet,LinkedHashedSet,比较是否相同本质上是equals,
// TreeSet本质上,比较是用compareTo方法,若返回0,则两对象相同
set.add(new User("Jack", 56));
Iterator iterator = set.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
}
- TreeSet的定制排序
// 定制排序
@Test
public void test2(){
// 创建一个Comparator接口的匿名实现类的非匿名对象
Comparator com = new Comparator() {
// 按照年龄从小到大排序
@Override
public int compare(Object o1, Object o2) {
if (o1 instanceof User && o2 instanceof User) {
User u1 = (User) o1;
User u2 = (User) o2;
return Integer.compare(u1.getAge(), u2.getAge());
}else{
throw new RuntimeException("输入类型不匹配");
}
}
};
TreeSet set = new TreeSet(com);// 不传入参数则按照自然排序来排,加上参数就按参数方式来排
set.add(new User("Tom", 12));
set.add(new User("Jerry", 32));
set.add(new User("Jim", 65));
// 当要比较的属性一样时,则会先来的输出,后来的去除
set.add(new User("Mary", 33));
set.add(new User("Jack", 33));
set.add(new User("Jack", 56));
Iterator iterator = set.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
}
11.6.Map接口
大厂面试只要说出康师傅讲的和什么时候转化成红黑树即可，小厂被直接问到ConcurrentHashMap底层如何实现，完全不会
- Map接口及其多个实现类的对比
一.Map的实现类的结构:
Map: 双列数据, 存储key-value对的数据 --类似于高中的函数: y = f(x)
HashMap实现类: 作为Map的主要实现类: 线程不安全的,效率高; 可以存储null的key和value
LinkedHashMap(HashMap的子类): 保证在遍历map元素时,可以按照添加的顺序实现遍历
原因: 在原有的HashMap底层结构基础上,添加了一对指针,指向前一个和后一个元素.相当于记录了当前添加的key-value的前一个是谁后一个是谁,使得就能按顺序遍历,查找更方便了
对于频繁的遍历操作,此类执行效率高于HashMap.
TreeMap实现类: 类似于TreeSet,保证按照添加的key-value对进行排序,实现排序遍历.此时考虑key的自然排序或定制排序
底层使用红黑树(平衡二叉查找树)
Hashtable实现类: 作为古老的实现类: 线程安全的,效率低; 不能存储null的key和value
Properties(Hashtable的子类): 常用来处理配置文件. key和value都是String类型
HashMap的底层: 数组+链表 (jdk7及之前)
数组+链表+红黑树;为了提高效率(jdk8)
- Map中存储的key-value的特点
image.png
二.Map结构的理解:
Map中的key: 无序的,不可重复的,用Set存储所有的key,如果是HashMap就用HashSet存,若是LinkedHashMap就用LinkedHashMap存 --> 要求key所在的类要重写equals()和hashcode() (以HashMap为例),重写hashcode是为了效率高点或找key方便点
Map中的value: 无序的,可重复的,用Collection存储所有的value --> value所在的类要重写equals(),判断有没有,为了实现通过value找key的方法
一个键值对: key-value构成一个entry对象,key和value相当于entry的两个属性
Map中的Entry: 无序的,不可重复的,用Set存储所有的Entry
- HashMap在jdk7中底层的实现原理
三.HashMap的底层实现原理? 以jdk7为例说明:
HashMap map = new HashMap();
在实例化以后,底层创建了长度是16的一维数组Entry[] table
...之前可能已经执行过多次put...
map.put(key1,value1): 添加操作
首先,调用key1所在类的hashcode()计算key1哈希值,此哈希值经过某种算法计算以后,得到在Entry数组中的存放位置.(跟HashSet有点像)
若此位置上的数据为空,此时的key1-value1添加成功. -- 情况1;实际上添到数组上的数据是entry,理论上是双列数据,实际上还是一个一个的,比的都是entry,只不过用entry中的key来判断存在哪的一个标准,实际上是entry添加成功
若此位置上的数据不为空,(意味着此位置上存在一个或多个数据(以链表形式存在)),比较key1和已经存在的一个或多个数据的哈希值:
若key1的哈希值与已经存在数据的哈希值不相同,此时key1-value1添加成功.-- 情况2
若key1的哈希值和已经存在的某一个数据(key2-value2)的哈希值相同,继续比较: 调用key1所在类的equals(key2)方法,比较:
若equals()返回false:此时key1-value1添加成功.-- 情况3
若equals()返回true: 用value1替换(覆盖)value2
补充: 关于情况2和情况3: 此时key1-value1和原来的数据以链表的方式存储
在不断地添加过程中,会涉及到扩容问题,当超出临界值(且要存放的位置非空)时,扩容.默认的扩容方式: 扩容为原来容量的2倍,并将原有的数据复制过来
- HashMap在jdk8中底层的实现原理
jdk8相较于jdk7在底层实现方面的不同:
1.new HashMap(): 底层没有创建一个长度为16的数组
2.jdk8底层的数组是: Node[], 而非Entry[]
3.首次调用put()方法时,底层创建长度为16的数组
4.jdk7底层结构只有: 数组+链表. jdk8中底层结构: 数组+链表+红黑树
当数组的某一个索引位置删的元素以链表形式存在的数据个数 > 8 且当前数组的长度 > 64时,
此时此索引位置上的所有数据改为用红黑树存储.采用二分查找的方式,提高查询效率
-
HashMap在jdk7中的源码分析
-
HashMap在jdk8中的源码分析
DEFAULT_INITIAL_ CAPACITY : HashMap的默认容量，16
DEFAULT_LOAD_FACTOR: HashMap的默认加载因子:0.75
DEFAULT_INITIAL_ CAPACITY : HashMap的默认容量，16DEFAULT_LOAD_FACTOR: HashMap的默认加载因子:0.75
threshold:扩容的临界值，=容量填充因子:16 0.75 =>12
TREEIEY_ THRESHOLD: Bucket中链表长度大于该默认值，转化为红黑树:8
MIN_TREEIFY_CAPACITY:桶中的Node被树化时最小的hash表容量:64
- LinkedHashMap的底层实现原理
四.LinkedHashMap的底层实现原理(了解)
LinkedHashMap底层使用的结构与HashMap相同，因为LinkedHashMap继承于HashMap.
区别就在于: LinkedHashMap内部提供了Entry，替换HashMap中的Node.
HashMap中的内部类:Node
源码中:
static class Node<K,V> implements Map.Entry<K,V> {
fina1 int hash;
final K key; value;
Node<K,V>next;
}
LinkedHashMap中的内部类: Entry
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;// 能够记录添加元素的先后顺序
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
- Map中常用的方法
public class MapTest {
@Test
public void test5(){
Map map = new HashMap();
map.put("AA", 123);
map.put(45, 123);
map.put("BB", 56);
// keySet(): 遍历所有的key构成的集合, set是所有的key构成的
Set set = map.keySet();
Iterator iterator = set.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
System.out.println("=========");
// values(): 遍历所有的value集,和key一一对应
Collection values = map.values();
for (Object obj : values){
System.out.println(obj);
}
System.out.println("=========");
// 遍历所有的key-value,可以单独把key或value值取出
// 方式一:
// entrySet(): 获取所有的entry构成的Set集合
Set entrySet = map.entrySet();
Iterator iterator1 = entrySet.iterator();
while (iterator1.hasNext()) {
Object obj = iterator1.next();
// entrySet集合中的元素都是entry,所以可以把obj向下强转
// 向下强转可以单独拿到key和value
Map.Entry entry = (Map.Entry) obj;// Entry接口类型的引用,不是实例对象,接口引用指向实现类的对象，多态
System.out.println(entry.getKey() + "-->" + entry.getValue());
}
// 方式二:
Set keySet = map.keySet();
Iterator iterator2 = keySet.iterator();
while (iterator2.hasNext()) {
Object key = iterator2.next();// 获取map的key值
Object value = map.get(key);// 通过指定的key获取对应的value
System.out.println(key + "==>" + value);
}
}
@Test
public void test4(){
Map map = new HashMap();
map.put("AA", 123);
map.put(45, 123);
map.put("BB", 56);
// Object get(Object key): 获取指定key对应的value,key不存在返回null
System.out.println(map.get(45));// 123
// containsKey(Object key): 是否包含指定的key
boolean isExist = map.containsKey("BB");// 先通过哈希值找到指定key在数组中的位置,再通过equals方法找到对应的key
// containsValue(Object key): 是否包含指定的value,若有多个相同的value,只要找到一个是true后就终止
isExist = map.containsValue(123);
// int size(): 返回map的key-value对的个数
// boolean isEmpty(): 判断当前map是否为空
map.clear();// 只是清空table中的元素,new的对象仍然存在
System.out.println(map.isEmpty());// true 判断是否为空,只要判断size是否为0
// boolean equals(Object obj): 判断当前map和参数对象obj是否相等,类型相同,内容相同
}
@Test
public void test3(){
Map map = new HashMap();
// 一般情况下,key-value类型都是确定的
//添加
map.put("AA", 123);
map.put(45, 123);
map.put("BB", 56);
// 修改,替换原有的
map.put("AA", 87);
System.out.println(map);
// putAll()
Map map1 = new HashMap();
map1.put("CC", 123);
map1.put("DD", 123);
map.putAll(map1);
System.out.println(map);
// remove(Object key): 移除指定的key的key-value对,并返回value
Object value = map.remove("CC");//存在返回对应value,不存在返回null
System.out.println(value);
System.out.println(map);
// clear(): 将map中所有元素清空
map.clear();// 与map = null 操作不同,Collection集合clear之后调isEmpty不会空指针异常,
System.out.println(map.size());// 元素个数 0
System.out.println(map);// {}
}
@Test
public void test2(){
// 无序性: 数组放的元素不是一个一个紧挨着的
Map map = new HashMap();
map = new LinkedHashMap();// 按照添加顺序来能够记录谁先加谁后加
map.put(123,"AA");
map.put(345,"BB");
map.put(12,"CC");
System.out.println(map);
}
@Test
public void test1(){
Map map = new HashMap();
// map = new Hashtable();// 报错
map.put(null, null);
}
}
- TreeMap两种添加方式的使用
向TreeMap中添加key-value,要求key必须是由同一个类创建的对象
因为要按照key进行排序: 自然排序,定制排序,不能按照value排序
// 自然排序
@Test
public void test1(){
TreeMap map = new TreeMap();// 自然排序调空参构造器
User u1 = new User("Tom", 23);
User u2 = new User("Jerry", 32);
User u3 = new User("Jack", 20);
User u4 = new User("Rose", 18);
map.put(u1,98);
map.put(u2,89);
map.put(u3,76);
map.put(u4,100);
// 遍历集合
Set entrySet = map.entrySet();
Iterator iterator = entrySet.iterator();
while (iterator.hasNext()) {
Object obj = iterator.next();
Map.Entry entry = (Map.Entry) obj;
System.out.println(entry.getKey() + "-->" + entry.getValue());
}
}
// TreeMap的定制排序,按年龄从小到大排
@Test
public void test2(){
// 创建TreeMap中的比较器的匿名实现类的匿名对象
TreeMap map = new TreeMap(new Comparator() {
@Override
public int compare(Object o1, Object o2) {
// 判断比较的对象是否属于User类
if (o1 instanceof User && o2 instanceof User) {
// 向下强转
User u1 = (User) o1;
User u2 = (User) o2;
// 通过年龄,从小到大排序
return Integer.compare(u1.getAge(), u2.getAge());
}else{
// 如果比较类型不是User类型
throw new RuntimeException("输入类型不匹配");
}
}
});
User u1 = new User("Tom", 23);
User u2 = new User("Jerry", 32);
User u3 = new User("Jack", 20);
User u4 = new User("Rose", 18);
map.put(u1,98);
map.put(u2,89);
map.put(u3,76);
map.put(u4,100);
// 遍历集合
// 创建遍历key-value集合的对象
Set entrySet = map.entrySet();
// 创建遍历集合对象的迭代器
Iterator iterator = entrySet.iterator();
// 循环遍历,判断是否有下一个元素
while (iterator.hasNext()) {
// 得到遍历的每个元素,并向下强转
Object obj = iterator.next();
Map.Entry entry = (Map.Entry) obj;
// 输出每个元素所以在entry对象
System.out.println(entry.getKey() + "-->" + entry.getValue());
}
}
- Properties处理属性配置文件
public class PropertiesTest {
// Properties: 常用来处理配置文件.key和value都是String类型
public static void main(String[] args) {
FileInputStream fis = null;
try {
// 造一个对象,代码中把配置信息读进来
Properties pros = new Properties();
// 创建文件流对象
fis = new FileInputStream("/jdbc.properties");
// 加载流对应的文件
pros.load(fis);
// 读取文件中的数据
String name = pros.getProperty("name");
String password = pros.getProperty("password");
System.out.println("name = " + name + " password = " + password);
} catch (IOException e) {
e.printStackTrace();
}finally {
if (fis != null)
try {
fis.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
}
- Collections工具类常用方法的测试
面试题: Collection 和 Collections的区别?
Collection是一个存储单列集合的接口, Collections是一个Collection,Map的工具类
public class CollectionsTest {
@Test
public void test1(){
// reverse(List): 反转List中的元素的顺序
List list = new ArrayList();
list.add(132);
list.add(46);
list.add(654);
list.add(-34);
list.add(0);
System.out.println(list);
Collections.reverse(list);// 把原list修改了
System.out.println(list);
// shffle(List): 对List集合的元素随机排序
Collections.shuffle(list);
System.out.println(list);
// sort(List): 根据元素的自然排序,对指定的list集合元素从小到大排序
Collections.sort(list);// 调用集合元素所在类的compareTo方法
System.out.println(list);
// swap(List int, int): 交换指定list中指定索引位置上的两个元素
Collections.swap(list,1,2);
// Object max(Collection): 根据元素的自然排序对指定list集合按从小到大排序并返回最大值
// Object max(Collection,Comparator): 根据元素的定制排序对指定list集合按从大到小排序,并返回最大值
// int frequency(Collection, Object): 返回指定集合中指定元素的出现次数
int frequency = Collections.frequency(list, 132);
System.out.println(frequency);// 1
}
@Test
public void test2(){
List list = new ArrayList();
list.add(132);
list.add(46);
list.add(654);
list.add(-34);
list.add(0);
// void copy(List dest, List src): 将src中的内容复制到dest中
// 报错,IndexOutOfBoundsException: Source does not fit in dest
/*List dest = new ArrayList();
Collections.copy(dest, list);
System.out.println(dest);*/
// 正确的: 通过asList把dest集合撑开,造了一个Object数组,长度是list.size(),里面相当于有size个元素,只不过每个位置都是null
List dest = Arrays.asList(new Object[list.size()]);
System.out.println(dest.size());// 等于list.size()
System.out.println(dest);
Collections.copy(dest, list);
System.out.println(dest);
// boolean replaceAll(List list, Object oldVal, Object newVal): 用新值替换
/*
Collections类中提供了多个synchronizedXxx()方法,
该方法可使将指定集合包装秤线程同步的集合,
从而可以解决多线程并发访问集合时的线程安全问题
*/
// 把ArrayList的对象list作为参数传入方法中,返回一个线程安全的list1对象
// 即为线程安全的list,就可以在多个线程中操作list了
List list1 = Collections.synchronizedList(list);
}
}
网友评论