第 12 章 集合
12.1 集合的理解和好处
前面我们保存多个数据使用的是数组，那么数组有不足的地方，我们分析一下
12.1.1 数组
- 长度开始时必须指定，而且一旦指定，不能更改
- 保存的必须为同一类型的元素
- 使用数组进行增加/删除元素的示意代码 – 比较麻烦
写出Person数组扩容示意代码。
Person[] pers = new Person[1]; //大小是1
pers[0]=new Person(); //增加新的Person对象?
Person[] pers2 = new Person[pers.length+1]; //新创建数组
for(int i = 0; i < pers.length; i++){ //拷贝pers数组的元素到pers2 pers2[i] = pers[i];
}
pers2[pers2.length-1] = new Person();//添加新的对象
12.1.2 集合
- 可以动态保存任意多个对象，使用比较方便！
- 提供了一系列方便的操作对象的方法：add、remove、set、get等
- 使用集合添加,删除新元素的示意代码- 简洁了
12.2 集合的框架体系
Java 的集合类很多，主要分为两大类，如图：
public class Collection_ {@SuppressWarnings({"all"})public static void main(String[] args) {//解读//1. 集合主要是两组(单列集合 , 双列集合)//2. Collection 接口有两个重要的子接口 List Set , 他们的实现子类都是单列集合//3. Map 接口的实现子类 是双列集合，存放的 K-V//4. 把老师梳理的两张图记住//Collection//MapArrayList arrayList = new ArrayList();arrayList.add("jack");arrayList.add("tom");HashMap hashMap = new HashMap();hashMap.put("NO1", "北京");hashMap.put("NO2", "上海");}
}
12.3 Collection 接口和常用方法
12.3.1 Collection 接口实现类的特点
public interface Collection<E> extends Iterable<E>
- collection实现子类可以存放多个元素，每个元素可以是Object
- 有些Collection的实现类，可以存放重复的元素，有些不可以
- 有些Collection的实现类，有些是有序的(List)，有些不是有序(Set)
- Collection接口没有直接的实现子类，是通过它的子接口Set 和 List 来实现的
Collection 接口常用方法,以实现子类 ArrayList 来演示. CollectionMethod.java
public class CollectionMethod {@SuppressWarnings({"all"})public static void main(String[] args) {List list = new ArrayList();
// add:添加单个元素list.add("jack");list.add(10);//list.add(new Integer(10))list.add(true);System.out.println("list=" + list);
// remove:删除指定元素//list.remove(0);//删除第一个元素list.remove(true);//指定删除某个元素System.out.println("list=" + list);
// contains:查找元素是否存在System.out.println(list.contains("jack"));//T
// size:获取元素个数System.out.println(list.size());//2
// isEmpty:判断是否为空System.out.println(list.isEmpty());//F
// clear:清空list.clear();System.out.println("list=" + list);
// addAll:添加多个元素ArrayList list2 = new ArrayList();list2.add("红楼梦");list2.add("三国演义");list.addAll(list2);System.out.println("list=" + list);
// containsAll:查找多个元素是否都存在System.out.println(list.containsAll(list2));//T
// removeAll：删除多个元素list.add("聊斋");list.removeAll(list2);System.out.println("list=" + list);//[聊斋]
// 说明：以ArrayList实现类来演示.}
}
12.3.2 Collection 接口遍历元素方式 1-使用 Iterator(迭代器)
基本介绍
java.util
接口 Iterator<E>
所有已知子接口: ListIterator<E>, XMLStreamReader
所有已知实现类: BeanContextSupport.BCSIterator, EventReaderDelegate, Scanner
- Iterator对象称为迭代器，主要用于遍历 Collection 集合中的元素。
- 所有实现了Collection接口的集合类都有一个iterator()方法，用以返回一个实现了Iterator接口的对象，即可以返回一个迭代器。
- Iterator 的结构.[看一张图]
- Iterator 仅用于遍历集合，Iterator 本身并不存放对象。
在调用 iterator.next() 方法之前必须要调用 iterator.hasNext() 进行检测。若不调用，且下一条记录无效，直接调用 it.next() 会抛出 NoSuchElementException 异常。 迭代器的使用案例
看案例演示 CollectionIterator.java
public class CollectionIterator {@SuppressWarnings({"all"})public static void main(String[] args) {Collection col = new ArrayList();col.add(new Book("三国演义", "罗贯中", 10.1));col.add(new Book("小李飞刀", "古龙", 5.1));col.add(new Book("红楼梦", "曹雪芹", 34.6));//System.out.println("col=" + col);//现在希望能够遍历 col集合//1. 先得到 col 对应的 迭代器Iterator iterator = col.iterator();//2. 使用while循环遍历
// while (iterator.hasNext()) {//判断是否还有数据
// //返回下一个元素，类型是Object
// Object obj = iterator.next();
// System.out.println("obj=" + obj);
// }//一个快捷键，快速生成 while => itit//显示所有的快捷键的的快捷键 ctrl + jwhile (iterator.hasNext()) {Object obj = iterator.next();System.out.println("obj=" + obj);}//3. 当退出while循环后 , 这时iterator迭代器，指向最后的元素// iterator.next();//NoSuchElementException//4. 如果希望再次遍历，需要重置我们的迭代器iterator = col.iterator();System.out.println("===第二次遍历===");while (iterator.hasNext()) {Object obj = iterator.next();System.out.println("obj=" + obj);}}
}class Book {private String name;private String author;private double price;public Book(String name, String author, double price) {this.name = name;this.author = author;this.price = price;}public String getName() {return name;}public void setName(String name) {this.name = name;}public String getAuthor() {return author;}public void setAuthor(String author) {this.author = author;}public double getPrice() {return price;}public void setPrice(double price) {this.price = price;}@Overridepublic String toString() {return "Book{" +"name='" + name + '\'' +", author='" + author + '\'' +", price=" + price +'}';}
}
12.3.3 Collection 接口遍历对象方式 2 - for 循环增强
增强 for 循环，可以代替 iterator 迭代器，特点：增强 for 就是简化版的 iterator，本质一样。只能用于遍历集合或数组。
基本语法
for(元素类型 元素名 : 集合名或数组名) { 访问元素
}
案例演示
CollectionFor.java
for (Object object : col) { System.out.println(object);
}
public class CollectionFor {@SuppressWarnings({"all"})public static void main(String[] args) {Collection col = new ArrayList();col.add(new Book("三国演义", "罗贯中", 10.1));col.add(new Book("小李飞刀", "古龙", 5.1));col.add(new Book("红楼梦", "曹雪芹", 34.6));//解读//1. 使用增强for, 在Collection集合//2. 增强for， 底层仍然是迭代器//3. 增强for可以理解成就是简化版本的 迭代器遍历//4. 快捷键方式 I
// for (Object book : col) {
// System.out.println("book=" + book);
// }for (Object o : col) {System.out.println("book=" + o);}//增强for，也可以直接在数组使用
// int[] nums = {1, 8, 10, 90};
// for (int i : nums) {
// System.out.println("i=" + i);
// }}
}
12.4 List 接口和常用方法
12.4.1 List 接口基本介绍
List 接口是 Collection 接口的子接口 List.java
List集合类中元素有序（即添加顺序和取出顺序一致）、且可重复 [案例]List集合中的每个元素都有其对应的顺序索引，即支持索引。 [案例]List容器中的元素都对应一个整数型的序号记载其在容器中的位置，可以根据序号存取容器中的元素。- JDK API 中
List接口的实现类有：
常用的有：List list = new ArrayList(); list.add("tom"); list.add("jack"); list.add("mary"); list.add("smith"); list.add("smith2"); list.add("kristina"); System.out.println(list); // 3的案例 System.out.println(list.get(4));//smith2ArrayList、LinkedList和Vector。
public class List_ {@SuppressWarnings({"all"})public static void main(String[] args) {//1. List集合类中元素有序(即添加顺序和取出顺序一致)、且可重复 [案例]List list = new ArrayList();list.add("jack");list.add("tom");list.add("mary");list.add("hsp");list.add("tom");System.out.println("list=" + list);//2. List集合中的每个元素都有其对应的顺序索引，即支持索引// 索引是从0开始的System.out.println(list.get(3));//hsp//3.}
}
12.4.2 List接口的常用方法
public class ListMethod {@SuppressWarnings({"all"})public static void main(String[] args) {List list = new ArrayList();list.add("张三丰");list.add("贾宝玉");
// void add(int index, Object ele):在index位置插入ele元素//在index = 1的位置插入一个对象list.add(1, "拉里");System.out.println("list=" + list);
// boolean addAll(int index, Collection eles):从index位置开始将eles中的所有元素添加进来List list2 = new ArrayList();list2.add("jack");list2.add("tom");list.addAll(1, list2);System.out.println("list=" + list);
// Object get(int index):获取指定index位置的元素//说过
// int indexOf(Object obj):返回obj在集合中首次出现的位置System.out.println(list.indexOf("tom"));//2
// int lastIndexOf(Object obj):返回obj在当前集合中末次出现的位置list.add("拉里");System.out.println("list=" + list);System.out.println(list.lastIndexOf("拉里"));
// Object remove(int index):移除指定index位置的元素，并返回此元素list.remove(0);System.out.println("list=" + list);
// Object set(int index, Object ele):设置指定index位置的元素为ele , 相当于是替换.list.set(1, "玛丽");System.out.println("list=" + list);
// List subList(int fromIndex, int toIndex):返回从fromIndex到toIndex位置的子集合// 注意返回的子集合 fromIndex <= subList < toIndexList returnlist = list.subList(0, 2);System.out.println("returnlist=" + returnlist);}
}
12 .4.3 List接口课堂练习
public class ListExercise {@SuppressWarnings({"all"})public static void main(String[] args) {/*添加10个以上的元素(比如String "hello" )，在2号位插入一个元素"教育"，获得第5个元素，删除第6个元素，修改第7个元素，在使用迭代器遍历集合，要求:使用List的实现类ArrayList完成。*/List list = new ArrayList();for (int i = 0; i < 12; i++) {list.add("hello" + i);}System.out.println("list=" + list);//在2号位插入一个元素"教育"list.add(1, "教育");System.out.println("list=" + list);//获得第5个元素System.out.println("第五个元素=" + list.get(4));//删除第6个元素list.remove(5);System.out.println("list=" + list);//修改第7个元素list.set(6, "三国演义");System.out.println("list=" + list);//在使用迭代器遍历集合Iterator iterator = list.iterator();while (iterator.hasNext()) {Object obj = iterator.next();System.out.println("obj=" + obj);}}
}
12.4.4 List的三种遍历方式[ArrayList,LinkedList,Vector]
public class ListFor {@SuppressWarnings({"all"})public static void main(String[] args) {//List 接口的实现子类 Vector LinkedList//List list = new ArrayList();//List list = new Vector();List list = new LinkedList();list.add("jack");list.add("tom");list.add("鱼香肉丝");list.add("北京烤鸭子");//遍历//1. 迭代器Iterator iterator = list.iterator();while (iterator.hasNext()) {Object obj = iterator.next();System.out.println(obj);}System.out.println("=====增强for=====");//2. 增强forfor (Object o : list) {System.out.println("o=" + o);}System.out.println("=====普通for====");//3. 使用普通forfor (int i = 0; i < list.size(); i++) {System.out.println("对象=" + list.get(i));}}
}
12.5 ArrayList 底层结构和源码分析
12.5.1 ArrayList 的注意事项
ArrayListDetail.java
- permits all elements, including null，ArrayList 可以加入 null，并且多个
- ArrayList 是由数组来实现数据存储的 [后面老师解读源码]
- ArrayList 基本等同于 Vector，除了 ArrayList 是线程不安全（执行效率高）看源码。在多线程情况下，不建议使用 ArrayList
12.5.2 ArrayList 的底层操作机制源码分析(重点，难点.)
ArrayListSource.java ，先说结论，在分析源码(示意图)
- ArrayList 中维护了一个 Object 类型的数组
elementData。[debug 看源码]transient Object[] elementData; // transient 表示瞬间,短暂的,表示该属性不会被序列号 - 当创建 ArrayList 对象时，如果使用的是无参构造器，则初始
elementData容量为 0，第 1 次添加，则扩容elementData为 10，如需要再次扩容，则扩容elementData为 1.5 倍。 - 如果使用的是指定大小的构造器，则初始
elementData容量为指定大小，如果需要扩容，则直接扩容elementData为 1.5 倍。
12.6 Vector 底层结构和源码剖析
12.6.1 Vector 的基本介绍
-
Vector 类的定义说明
public class Vector<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, Serializable -
Vector 底层也是一个对象数组
protected Object[] elementData; -
Vector 是线程同步的（即线程安全），Vector 类的操作方法带有
synchronizedpublic synchronized E get(int index) { if (index >= elementCount) throw new ArrayIndexOutOfBoundsException(index); return elementData(index); } -
在开发中，需要线程同步安全时，考虑使用 Vector
-
public class Vector_ {public static void main(String[] args) {//无参构造器//有参数的构造Vector vector = new Vector(8);for (int i = 0; i < 10; i++) {vector.add(i);}vector.add(100);System.out.println("vector=" + vector);//解读源码//1. new Vector() 底层/*public Vector() {this(10);}补充：如果是 Vector vector = new Vector(8);走的方法:public Vector(int initialCapacity) {this(initialCapacity, 0);}2. vector.add(i)2.1 //下面这个方法就添加数据到vector集合public synchronized boolean add(E e) {modCount++;ensureCapacityHelper(elementCount + 1);elementData[elementCount++] = e;return true;}2.2 //确定是否需要扩容 条件 ： minCapacity - elementData.length>0private void ensureCapacityHelper(int minCapacity) {// overflow-conscious codeif (minCapacity - elementData.length > 0)grow(minCapacity);}2.3 //如果 需要的数组大小 不够用，就扩容 , 扩容的算法//newCapacity = oldCapacity + ((capacityIncrement > 0) ?// capacityIncrement : oldCapacity);//就是扩容两倍.private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;int newCapacity = oldCapacity + ((capacityIncrement > 0) ?capacityIncrement : oldCapacity);if (newCapacity - minCapacity < 0)newCapacity = minCapacity;if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);elementData = Arrays.copyOf(elementData, newCapacity);}*/} }
12.6.2 Vector 和 ArrayList 的比较
| 底层结构 | 版本 | 线程安全（同步）效率 | 扩容倍数 | |
|---|---|---|---|---|
| ArrayList | 可变数组 | jdk1.2 | 不安全，效率高 | 如果有参构造1.5倍 如果是无参 1.第一次10 2.从第二次开始1.5扩 |
| Vector | 可变数组 Object[] | jdk1.0 | 安全，效率不高 | 如果是无参，默认10 ，满后，就按2倍扩容 如果指定大小，则每次直接按2倍扩容。 |
12.7 LinkedList 底层结构
12.7.1 LinkedList 的全面说明
- LinkedList 底层实现了双向链表和双端队列特点
- 可以添加任意元素（元素可以重复），包括
null - 线程不安全，没有实现同步
12.7.2 LinkedList 的底层操作机制
public class LinkedList01 {public static void main(String[] args) {//模拟一个简单的双向链表Node jack = new Node("jack");Node tom = new Node("tom");Node lili = new Node("lili");//连接三个结点，形成双向链表//jack -> tom -> lilijack.next = tom;tom.next = lili;//lili -> tom -> jacklili.pre = tom;tom.pre = jack;Node first = jack;//让first引用指向jack,就是双向链表的头结点Node last = lili; //lili,就是双向链表的尾结点//演示，从头到尾进行遍历System.out.println("===从头到尾进行遍历===");while (true) {if(first == null) {break;}//输出first 信息System.out.println(first);first = first.next;}//演示，从尾到头的遍历System.out.println("====从尾到头的遍历====");while (true) {if(last == null) {break;}//输出last 信息System.out.println(last);last = last.pre;}//演示链表的添加对象/数据，是多么的方便//要求，是在 tom --------- lili直接，插入一个对象 smith//1. 先创建一个 Node 结点，name 就是 smithNode smith = new Node("smith");//下面就把 smith 加入到双向链表了smith.next = lili;smith.pre = tom;lili.pre = smith;tom.next = smith;//让first 再次指向jackfirst = jack;//让first引用指向jack,就是双向链表的头结点System.out.println("===从头到尾进行遍历===");while (true) {if(first == null) {break;}//输出first 信息System.out.println(first);first = first.next;}last = lili; //让last 重新指向最后一个结点//演示，从尾到头的遍历System.out.println("====从尾到头的遍历====");while (true) {if(last == null) {break;}//输出last 信息System.out.println(last);last = last.pre;}}
}//定义一个Node 类，Node 对象 表示双向链表的一个结点
class Node {public Object item; //真正存放数据public Node next; //指向后一个结点public Node pre; //指向前一个结点public Node(Object name) {this.item = name;}public String toString() {return "Node name=" + item;}
}
12.7.3 LinkedList的增删改查案例
public class LinkedListCRUD {public static void main(String[] args) {LinkedList linkedList = new LinkedList();linkedList.add(1);linkedList.add(2);linkedList.add(3);System.out.println("linkedList=" + linkedList);//演示一个删除结点的linkedList.remove(); // 这里默认删除的是第一个结点//linkedList.remove(2);System.out.println("linkedList=" + linkedList);//修改某个结点对象linkedList.set(1, 999);System.out.println("linkedList=" + linkedList);//得到某个结点对象//get(1) 是得到双向链表的第二个对象Object o = linkedList.get(1);System.out.println(o);//999//因为LinkedList 是 实现了List接口, 遍历方式System.out.println("===LinkeList遍历迭代器====");Iterator iterator = linkedList.iterator();while (iterator.hasNext()) {Object next = iterator.next();System.out.println("next=" + next);}System.out.println("===LinkeList遍历增强for====");for (Object o1 : linkedList) {System.out.println("o1=" + o1);}System.out.println("===LinkeList遍历普通for====");for (int i = 0; i < linkedList.size(); i++) {System.out.println(linkedList.get(i));}//源码阅读./* 1. LinkedList linkedList = new LinkedList();public LinkedList() {}2. 这时 linkeList 的属性 first = null last = null3. 执行 添加public boolean add(E e) {linkLast(e);return true;}4.将新的结点，加入到双向链表的最后void linkLast(E e) {final Node<E> l = last;final Node<E> newNode = new Node<>(l, e, null);last = newNode;if (l == null)first = newNode;elsel.next = newNode;size++;modCount++;}*//*读源码 linkedList.remove(); // 这里默认删除的是第一个结点1. 执行 removeFirstpublic E remove() {return removeFirst();}2. 执行public E removeFirst() {final Node<E> f = first;if (f == null)throw new NoSuchElementException();return unlinkFirst(f);}3. 执行 unlinkFirst, 将 f 指向的双向链表的第一个结点拿掉private E unlinkFirst(Node<E> f) {// assert f == first && f != null;final E element = f.item;final Node<E> next = f.next;f.item = null;f.next = null; // help GCfirst = next;if (next == null)last = null;elsenext.prev = null;size--;modCount++;return element;}*/}
}
12.8 ArrayList 和 LinkedList 比较
12.8.1 ArrayList 和 LinkedList 的比较
| 底层结构 | 增删的效率 | 改查的效率 | |
|---|---|---|---|
| ArrayList | 可变数组 | 较低 数组扩容 |
较高 |
| LinkedList | 双向链表 | 较高，通过链表追加 | 较低 |
| 如何选择 ArrayList 和 LinkedList： |
- 如果改查操作多，选择 ArrayList
- 如果增删操作多，选择 LinkedList
- 一般程序中 80%-90% 是查询，因此大部分情况选 ArrayList
- 项目中灵活根据业务选，可能一个模块用 ArrayList，另一个用 LinkedList
12.9 Set 接口和常用方法
12.9.1 Set 接口基本介绍
- 无序（添加和取出顺序不一致），没有索引 [后面演示]
- 不允许重复元素，最多包含一个
null - JDK API 中 Set 接口的实现类有：
java.util 接口 Set<E> 类型参数: E - 此 set 所维护元素的类型 所有超级接口: Collection<E>, Iterable<E> 所有已知子接口: NavigableSet<E>, SortedSet<E> 所有已知实现类: AbstractSet, ConcurrentSkipListSet, CopyOnWriteArraySet, EnumSet, HashSet, JobStateReasons, LinkedHashSet, TreeSet
12.9.2 Set 接口的常用方法
和 List 接口一样，Set 接口也是 Collection 的子接口，因此，常用方法和 Collection 接口一样
12.9.3 Set 接口的遍历方式
同 Collection 的遍历方式一样，因为 Set 接口是 Collection 接口的子接口。
- 可以使用迭代器
- 增强 for
- 不能使用索引的方式来获取
12.9.4 Set 接口的常用方法举例
public class SetMethod {public static void main(String[] args) {//解读//1. 以Set 接口的实现类 HashSet 来讲解Set 接口的方法//2. set 接口的实现类的对象(Set接口对象), 不能存放重复的元素, 可以添加一个null//3. set 接口对象存放数据是无序(即添加的顺序和取出的顺序不一致)//4. 注意：取出的顺序的顺序虽然不是添加的顺序，但是他的固定.Set set = new HashSet();set.add("john");set.add("lucy");set.add("john");//重复set.add("jack");set.add("hsp");set.add("mary");set.add(null);//set.add(null);//再次添加nullfor(int i = 0; i <10;i ++) {System.out.println("set=" + set);}//遍历//方式1： 使用迭代器System.out.println("=====使用迭代器====");Iterator iterator = set.iterator();while (iterator.hasNext()) {Object obj = iterator.next();System.out.println("obj=" + obj);}set.remove(null);//方式2: 增强forSystem.out.println("=====增强for====");for (Object o : set) {System.out.println("o=" + o);}//set 接口对象，不能通过索引来获取}
}
12.10 Set 接口实现类 - HashSet
12.10.1 HashSet 的全面说明
HashSet.java
- HashSet 实现了 Set 接口
- HashSet 实际上是 HashMap，看源码（图）
public HashSet() { map = new HashMap<>(); } - 可以存放
null值，但是只能有一个null - HashSet 不保证元素是有序的，取决于 hash 后，再确定索引的结果（即，不保证存放元素的顺序和取出顺序一致）
- 不能有重复元素/对象，在前面 Set 接口使用已经讲过
public class HashSet_ {public static void main(String[] args) {//解读//1. 构造器走的源码/*public HashSet() {map = new HashMap<>();}2. HashSet 可以存放null ,但是只能有一个null,即元素不能重复*/Set hashSet = new HashSet();hashSet.add(null);hashSet.add(null);System.out.println("hashSet=" + hashSet);}
}
12.10.2HashSet案例说明
public class HashSet01 {public static void main(String[] args) {HashSet set = new HashSet();//说明//1. 在执行add方法后，会返回一个boolean值//2. 如果添加成功，返回 true, 否则返回false//3. 可以通过 remove 指定删除哪个对象System.out.println(set.add("john"));//TSystem.out.println(set.add("lucy"));//TSystem.out.println(set.add("john"));//FSystem.out.println(set.add("jack"));//TSystem.out.println(set.add("Rose"));//Tset.remove("john");System.out.println("set=" + set);//3个//set = new HashSet();System.out.println("set=" + set);//0//4 Hashset 不能添加相同的元素/数据?set.add("lucy");//添加成功set.add("lucy");//加入不了set.add(new Dog("tom"));//OKset.add(new Dog("tom"));//OkSystem.out.println("set=" + set);//在加深一下. 非常经典的面试题.//看源码，做分析， 先给小伙伴留一个坑，以后讲完源码，你就了然//去看他的源码，即 add 到底发生了什么?=> 底层机制.set.add(new String("ming"));//okset.add(new String("ming"));//加入不了.System.out.println("set=" + set);}
}
class Dog { //定义了Dog类private String name;public Dog(String name) {this.name = name;}@Overridepublic String toString() {return "Dog{" +"name='" + name + '\'' +'}';}
}
12.10.3 HashSet 底层机制说明
分析HashSet底层是HashMap, HashMap底层是(数组+链表+红黑树)
public class HashSetSource {public static void main(String[] args) {HashSet hashSet = new HashSet();hashSet.add("java");//到此位置，第1次add分析完毕.hashSet.add("php");//到此位置，第2次add分析完毕hashSet.add("java");System.out.println("set=" + hashSet);/*对HashSet 的源码解读1. 执行 HashSet()public HashSet() {map = new HashMap<>();}2. 执行 add()public boolean add(E e) {//e = "java"return map.put(e, PRESENT)==null;//(static) PRESENT = new Object();}3.执行 put() , 该方法会执行 hash(key) 得到key对应的hash值 算法h = key.hashCode()) ^ (h >>> 16)public V put(K key, V value) {//key = "java" value = PRESENT 共享return putVal(hash(key), key, value, false, true);}4.执行 putValfinal V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i; //定义了辅助变量//table 就是 HashMap 的一个数组，类型是 Node[]//if 语句表示如果当前table 是null, 或者 大小=0//就是第一次扩容，到16个空间.if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;//(1)根据key，得到hash 去计算该key应该存放到table表的哪个索引位置//并把这个位置的对象，赋给 p//(2)判断p 是否为null//(2.1) 如果p 为null, 表示还没有存放元素, 就创建一个Node (key="java",value=PRESENT)//(2.2) 就放在该位置 tab[i] = newNode(hash, key, value, null)if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {//一个开发技巧提示： 在需要局部变量(辅助变量)时候，在创建Node<K,V> e; K k; ////如果当前索引位置对应的链表的第一个元素和准备添加的key的hash值一样//并且满足 下面两个条件之一://(1) 准备加入的key 和 p 指向的Node 结点的 key 是同一个对象//(2) p 指向的Node 结点的 key 的equals() 和准备加入的key比较后相同//就不能加入if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;//再判断 p 是不是一颗红黑树,//如果是一颗红黑树，就调用 putTreeVal , 来进行添加else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {//如果table对应索引位置，已经是一个链表, 就使用for循环比较//(1) 依次和该链表的每一个元素比较后，都不相同, 则加入到该链表的最后// 注意在把元素添加到链表后，立即判断 该链表是否已经达到8个结点// , 就调用 treeifyBin() 对当前这个链表进行树化(转成红黑树)// 注意，在转成红黑树时，要进行判断, 判断条件// if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY(64))// resize();// 如果上面条件成立，先table扩容.// 只有上面条件不成立时，才进行转成红黑树//(2) 依次和该链表的每一个元素比较过程中，如果有相同情况,就直接breakfor (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);if (binCount >= TREEIFY_THRESHOLD(8) - 1) // -1 for 1sttreeifyBin(tab, hash);break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;//size 就是我们每加入一个结点Node(k,v,h,next), size++if (++size > threshold)resize();//扩容afterNodeInsertion(evict);return null;}*/}
}
public class HashSetIncrement {public static void main(String[] args) {/*HashSet底层是HashMap, 第一次添加时，table 数组扩容到 16，临界值(threshold)是 16*加载因子(loadFactor)是0.75 = 12如果table 数组使用到了临界值 12,就会扩容到 16 * 2 = 32,新的临界值就是 32*0.75 = 24, 依次类推*/HashSet hashSet = new HashSet();
// for(int i = 1; i <= 100; i++) {
// hashSet.add(i);//1,2,3,4,5...100
// }/*在Java8中, 如果一条链表的元素个数到达 TREEIFY_THRESHOLD(默认是 8 )，并且table的大小 >= MIN_TREEIFY_CAPACITY(默认64),就会进行树化(红黑树),否则仍然采用数组扩容机制*/// for(int i = 1; i <= 12; i++) {
// hashSet.add(new A(i));//
// }/*当我们向hashset增加一个元素，-> Node -> 加入table , 就算是增加了一个size++*/for(int i = 1; i <= 7; i++) {//在table的某一条链表上添加了 7个A对象hashSet.add(new A(i));//}for(int i = 1; i <= 7; i++) {//在table的另外一条链表上添加了 7个B对象hashSet.add(new B(i));//}}
}class B {private int n;public B(int n) {this.n = n;}@Overridepublic int hashCode() {return 200;}
}class A {private int n;public A(int n) {this.n = n;}@Overridepublic int hashCode() {return 100;}
}
12.10.4 HashSet 课堂练习 1
HashSetExercise.java 5min
定义一个 Employee 类，该类包含：private 成员属性 name, age 要求:
- 创建 3 个
Employee对象放入HashSet中 - 当
name和age的值相同时，认为是相同员工，不能添加到HashSet集合中
实现说明
equals()：若name和age值相同，返回true（判定为相同对象）hashCode()：若name和age值相同，返回相同哈希码（保证相同对象进同一哈希桶，配合equals去重 ）
操作示意：
在 IDE 中生成 equals() 和 hashCode() 时，勾选 name、age 字段，让这两个属性共同决定对象是否“相同”。
public class HashSetExercise {public static void main(String[] args) {/**定义一个Employee类，该类包含：private成员属性name,age 要求:创建3个Employee 对象放入 HashSet中当 name和age的值相同时，认为是相同员工, 不能添加到HashSet集合中*/HashSet hashSet = new HashSet();hashSet.add(new Employee("milan", 18));//okhashSet.add(new Employee("smith", 28));//okhashSet.add(new Employee("milan", 18));//加入不成功.//回答,加入了几个? 3个System.out.println("hashSet=" + hashSet);}
}//创建Employee
class Employee {private String name;private int age;public Employee(String name, int age) {this.name = name;this.age = age;}public String getName() {return name;}public void setName(String name) {this.name = name;}public int getAge() {return age;}@Overridepublic String toString() {return "Employee{" +"name='" + name + '\'' +", age=" + age +'}';}public void setAge(int age) {this.age = age;}//如果name 和 age 值相同，则返回相同的hash值@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;Employee employee = (Employee) o;return age == employee.age &&Objects.equals(name, employee.name);}@Overridepublic int hashCode() {return Objects.hash(name, age);}
}
12.11 Set 接口实现类 - LinkedHashSet
12.11.1 LinkedHashSet 的全面说明
- LinkedHashSet 是 HashSet 的子类
- LinkedHashSet 底层是一个 LinkedHashMap，底层维护了一个数组 + 双向链表
- LinkedHashSet 根据元素的 hashCode 值来决定元素的存储位置，同时使用链表维护元素的次序（图），这使得元素看起来是以插入顺序保存的。
- LinkedHashSet 不允许添加重复元素
public class LinkedHashSetSource {public static void main(String[] args) {//分析一下LinkedHashSet的底层机制Set set = new LinkedHashSet();set.add(new String("AA"));set.add(456);set.add(456);set.add(new Customer("刘", 1001));set.add(123);set.add("HSP");System.out.println("set=" + set);//解读//1. LinkedHashSet 加入顺序和取出元素/数据的顺序一致//2. LinkedHashSet 底层维护的是一个LinkedHashMap(是HashMap的子类)//3. LinkedHashSet 底层结构 (数组table+双向链表)//4. 添加第一次时，直接将 数组table 扩容到 16 ,存放的结点类型是 LinkedHashMap$Entry//5. 数组是 HashMap$Node[] 存放的元素/数据是 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);}}*/}
}
class Customer {private String name;private int no;public Customer(String name, int no) {this.name = name;this.no = no;}
}
12.11.2LinkedHashSet课后练习题LinkedHashSetExercise.java
public class LinkedHashSetExercise {public static void main(String[] args) {LinkedHashSet linkedHashSet = new LinkedHashSet();linkedHashSet.add(new Car("奥拓", 1000));//OKlinkedHashSet.add(new Car("奥迪", 300000));//OKlinkedHashSet.add(new Car("法拉利", 10000000));//OKlinkedHashSet.add(new Car("奥迪", 300000));//加入不了linkedHashSet.add(new Car("保时捷", 70000000));//OKlinkedHashSet.add(new Car("奥迪", 300000));//加入不了System.out.println("linkedHashSet=" + linkedHashSet);}
}/*** Car 类(属性:name,price)， 如果 name 和 price 一样，* 则认为是相同元素，就不能添加。 5min*/class Car {private String name;private double price;public Car(String name, double price) {this.name = name;this.price = price;}public String getName() {return name;}public void setName(String name) {this.name = name;}public double getPrice() {return price;}public void setPrice(double price) {this.price = price;}@Overridepublic String toString() {return "\nCar{" +"name='" + name + '\'' +", price=" + price +'}';}//重写equals 方法 和 hashCode//当 name 和 price 相同时， 就返回相同的 hashCode 值, equals返回t@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;Car car = (Car) o;return Double.compare(car.price, price) == 0 &&Objects.equals(name, car.name);}@Overridepublic int hashCode() {return Objects.hash(name, price);}
}