总结
实现set接口的集合
set集合：无序不重复
不重复（去重）：元素放入集合之前或做判断
无序：存取不一致
1、讲解set的实现类
HashSet:底层使用哈希表来实现（底层是一个数组，数组里面保存一个单向链表）的集合
不允许元素重复，元素是无序的
-
HashSet的去重机制（怎么去除重复）
第一步：将要添加到HashSet集合元素的hashCode值拿到
第二步：在集合去查找是否存在这个hashCode值
不存在，说明这个元素在集合中不存在，可以执行添加
存在，就来让这个元素.equals(hashCode值相同元素)， 不相等false，说明这个元素在集合中不存在，执行添加，
相等true，说明元素在集合中已经存在了，那就不添加
注意：如果是自己创建的类，要重写hashCode方法和equals()方法。
@Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Dog dog = (Dog) o; return Objects.equals(name, dog.name); } @Override public int hashCode() { return Objects.hash(name); } -
HashSet的作用就是用来去重
-
LinkedHashSet:底层哈希表+单向链表（记录顺序）：有序的HashSet
public static void main(String[] args) {
// 创建一个HashSet集合
HashSet set = new HashSet(); // 哈希表（散列表）
// 常用方法
set.add("abc");
set.add(true);
set.add(123);
set.add("波多野辰辰");
set.add("波多野辰辰");
set.add("波多野辰辰");
System.out.println(set);
// 遍历
// for (Object o : set) {
// System.out.println(o);
// }
Iterator it = set.iterator();
while (it.hasNext()) {
System.out.println(it.next());
}
}
public static void main(String[] args) {
// 产生10个不重复的随机数
// HashSet set = new HashSet();
// while (set.size() < 10) {
// set.add((int)(Math.random() * 100 + 1));
// }
// System.out.println(set);
HashSet set = new HashSet();
// Cat d1 = new Cat("来福");
// Cat d2 = new Cat("来福");
// System.out.println(d1.hashCode());
// System.out.println(d2.hashCode());
// set.add(d1);
// set.add(d2);
System.out.println(set);
}
TreeSet集合：底层使用树结构来实现的集合
TreeSet:无序不可重复
树型结构是提高查询效率，将树上的元素按大小排序
在使用TreeSet,该集合中只能放同一种类型的元素，第一个添加的元素类型，就是这个集合中能放的类型
为什么TreeSet只能放同一种类型的元素？
因为对元素进行排序，类型必须一致。
public static void main(String[] args) {
// 创建一个TreeSet集合
TreeSet set = new TreeSet(); // 底层是TreeMap，基于树结构
// set.add("abc");
// set.add("bbc");
// set.add(123);
// System.out.println(set);
set.add(20);
set.add(20);
set.add(2);
set.add(27);
set.add(12);
set.add(200);
System.out.println(set);
}
-
怎样去重（去除重复的机制）
通过两个接口来完成
添加元素到集合，这个元素会和集合里面所有的元素依次调用compareTo()进行比较，返回 0，就说明该元素在集合已经存在了，就不添加了 -
排序方法
自然排序：元素会根据类里面写compareTo()的代码来进行排序
注意：返回正数说明p1对象大于p2对象 2、返回负数说明p1小于p2 3、返回0说明p1等于p2
System.out.println(p1.compareTo(p2)); // 1、返回正数说明p1对象大于p2对象 2、返回负数说明p1小于p2 3、返回0说明p1等于p2@Override public int compareTo(Object o) { // 对象进行大小比较其实就是对象的属性值进行比较 Pig p = (Pig)o; if(!this.name.equals(p.name)) { // 两个对象的名字不同，就比较name return p.name.hashCode() - this.name.hashCode(); // 0 整数 负数 // return this.name.length() - p.name.length(); }else if(this.age != p.age) { // name相同，age不同，就比较age return p.age - this.age; } return 0; // 属性值都相等返回0 // return this.hashCode() - p.hashCode(); }定制排序：实现Comparator接口，在一个单独的类里面写compareTo()的代码来进行排序
import java.util.Comparator; public class MyCompartor implements Comparator { @Override public int compare(Object o1, Object o2) { Cat c1 = (Cat)o1; Cat c2 = (Cat)o2; if(!c1.getName().equals(c2.getName())) { return c2.getName().hashCode() - c1.getName().hashCode(); }else if(!c1.getGender().equals(c2.getGender())) { return c2.getGender().hashCode() - c1.getGender().hashCode(); }else if(c1.getAge() != c2.getAge()){ return c2.getAge() - c1.getAge(); } return 0; } }// 测试类 import java.util.TreeSet; public class CatTest { public static void main(String[] args) { Cat c1 = new Cat("咪咪", "公", 2); Cat c2 = new Cat("哆哆", "母", 5); Cat c3 = new Cat("啦啦", "公", 1); // TreeSet set = new TreeSet(); // Comparable TreeSet set = new TreeSet(new MyCompartor());// Comparator:定制排序 set.add(c1); set.add(c2); set.add(c3); System.out.println(set); } } -
作用就是对元素进行排序，放入TreeSet的元素必须是同一类型，必须要实现Comparable接口
注意：Comparable:比较对象大小的接口
ublic class Pig implements Comparable { private String name; private int age; public String getName() { return name; } public int getAge() { return age; } public void setAge(int age) { this.age = age; } public void setName(String name) { this.name = name; } @Override public String toString() { return "Pig{" + "name='" + name + '\'' + ", age=" + age + '}'; } @Override public int compareTo(Object o) { // 对象进行大小比较其实就是对象的属性值进行比较 Pig p = (Pig)o; if(!this.name.equals(p.name)) { // 两个对象的名字不同，就比较name return p.name.hashCode() - this.name.hashCode(); // 0 整数 负数 // return this.name.length() - p.name.length(); }else if(this.age != p.age) { // name相同，age不同，就比较age return p.age - this.age; } return 0; // 属性值都相等返回0 // return this.hashCode() - p.hashCode(); } }
集合小结
1、体系结构
Collection
-List:有序可重复
实现类：
-ArrayList:底层是一个数组，查改快，增删插慢
-LinkedList:底层是一个双向链表，双向队列，栈
增删插快，查改慢
对首尾操作快
栈：push(),pop()
-Vector:线程安全的动态数组
-Set：无序不可重复
-HashSet:底层是一个哈希表，去重的原理：hashCode + equals,作用：用来去重的
-LinkedHashSet:哈希表+单向链表，可以维护顺序
-TreeSet：底层是树结构，作用：用来排序
要求：同一种类型，要使用Comparable或Comparator,排序
2、使用场景：
集合用：ArrayList,需要大频率的增删插，将ArrayList转换为LinkedList
需要去重，将ArrayList转换HashSet,如果需要保证顺序，转换为LinkedHashSet
需要排序，将ArrayList转换为TreeSet
集合：保存一个值
Map集合
Map集合： 保存一对值
Map：映射（键值对，由一个键指向一个值）
Map中键不能重复，值可以重复，一个键只能指向一个值
Map是映射的顶级父类，是一个接口
Map的实现类
HashMap：就是一个哈希表（散列表）
底层是一个：数组，数组中保存了一个单向链表，链表在满足条件下回转为树结构（红黑树）
在数组保存那些信息：键的hashCode、键、值、下一个对象
创建HashMap集合对象
创建长度为16的数组，数组的每一个元素有一个空链表，map保存的是一对值
HashMap map = new HashMap();
put(K key, V value) : 向map集合添加一对值
map.put("3838438", "蘋蘋");
存放值的过程
key:"3838438"
1. 获取键的hashCode,假设hashCode是19
2. 计算这对值放入数组的下标位置：用键的hash值 % 当前数组的长度，19 % 16，计算的结 果是3，那么这对值应该放入下标为3的位置
3. 判断下标为3的位置上有没有值：
没有：直接将这对值放入这个位置
有：将这个值接在这个位置上存在值的后面
map中键不允许重复
去重的机制：键的hashCode + equals
- key："3838438"，将键的哈希值获得
- 去这个map集合中查看有没有相同哈希值的键
- 没有：说明键不重复
计算放入的位置
...... - 有：将这个键.equals(哈希值相同的键),结果是true，说明键已经存在，然后覆盖值，结果false
- 没有：说明键不重复
哈希碰撞（哈希冲突）
概念：计算存在的位置，这个位置上已经有值，这就是哈希碰撞
（HashSet的值就是存在HashMap的键上，所以HashSet的值不可重复）
链表转为红黑树的过程
当一个链表上的元素个数（链表的节点数）大于等于8个，看这个集合中元素个是否大于等于64
- 没有：底层数组做一次扩容：当前长度的2倍
- 有：这个链表就会形成红黑树
当我们做删除的时候
原来是红黑树的，如果元素个数小于等于6个，那么这个红黑树又会转为链表