TreeSet课后练习
public class MyDate {
//三个成员变量year,month,day
private int year;
private int month;
private int day;
public int getYear() {
return year;
}
public void setYear(int year) {
this.year = year;
}
public int getMonth() {
return month;
}
public void setMonth(int month) {
this.month = month;
}
public int getDay() {
return day;
}
public void setDay(int day) {
this.day = day;
}
public MyDate(int year, int month, int day) {
this.year = year;
this.month = month;
this.day = day;
}
public MyDate() {
}
@Override
public String toString() {
return "MyDate{" +
"year=" + year +
", month=" + month +
", day=" + day +
'}';
}
}
public class Employee implements Comparable{
//该类包含三个成员变量name，age，brithday,，其中brithday为MyDate类的对象
private String name;
private int age;
private MyDate brithday;
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 MyDate getBrithday() {
return brithday;
}
public void setBrithday(MyDate brithday) {
this.brithday = brithday;
}
@Override
public String toString() {
return "Employee{" +
"name='" + name + '\'' +
", age=" + age +
", brithday=" + brithday +
'}';
}
public Employee() {
}
public Employee(String name, int age, MyDate brithday) {
this.name = name;
this.age = age;
this.brithday = brithday;
}
//按照名称从小到大排序
@Override
public int compareTo(Object o) {
if(o instanceof Employee){
Employee employee = (Employee) o;
return this.name.compareTo(employee.name);
}
// return 0;
throw new RuntimeException("传入的数据异常！");
}
}
public class test {
public static void main(String[] args) {
//测试：使用自然排序
TreeSet set = new TreeSet();
set.add(new Employee("liangchaowei",56,new MyDate(1986,8,7)));
set.add(new Employee("liudehua",55,new MyDate(1987,5,4)));
set.add(new Employee("zhangxueyou",54,new MyDate(1988,9,13)));
set.add(new Employee("guofucheng",45,new MyDate(1990,4,28)));
set.add(new Employee("liming",48,new MyDate(1994,10,24)));
Iterator iterator = set.iterator();
while (iterator.hasNext()){
System.out.println(iterator.next());
}
//按照生日排序（定制排序）
Comparator com = new Comparator() {
@Override
public int compare(Object o1, Object o2) {
if(o1 instanceof Employee && o2 instanceof Employee){
Employee employee1 = (Employee) o1;
Employee employee2 = (Employee) o2;
if(employee1.getBrithday().getYear()==employee2.getBrithday().getYear()){
if(employee1.getBrithday().getMonth()==employee2.getBrithday().getMonth()){
return Integer.compare(employee1.getBrithday().getDay(),employee2.getBrithday().getDay());
}else {
return Integer.compare(employee1.getBrithday().getMonth(),employee2.getBrithday().getMonth());
}
}else {
return Integer.compare(employee1.getBrithday().getYear(),employee2.getBrithday().getYear());
}
}
throw new RuntimeException("数据输入异常！");
}
};
TreeSet set0 = new TreeSet(com);
set0.add(new Employee("liangchaowei",56,new MyDate(1986,8,7)));
set0.add(new Employee("liudehua",55,new MyDate(1987,5,4)));
set0.add(new Employee("zhangxueyou",54,new MyDate(1988,9,13)));
set0.add(new Employee("guofucheng",45,new MyDate(1988,9,28)));
set0.add(new Employee("liming",48,new MyDate(1988,10,24)));
Iterator iterator1 = set0.iterator();
System.out.println("======");
while (iterator1.hasNext()){
System.out.println(iterator1.next());
}
}
}
Set接口练习
练习一
- 在List内去除重复数字值，要求尽量简单
- 思路：将List转化为HashSet（通过addAll()方法转化），通过HashSet的特性不能有重复的值。来处理。
public class Demo02 {
public static void main(String[] args) {
List list = new ArrayList();
list.add(new Integer(1));
list.add(new Integer(1));
list.add(new Integer(2));
list.add(new Integer(3));
list.add(new Integer(3));
list.add(new Integer(4));
List list1 = duplicateList(list);
Iterator iterator = list1.iterator();
while (iterator.hasNext()){
System.out.print(iterator.next()+"\t");//1 2 3 4 (去掉了重复的)
}
}
public static List duplicateList(List list){
HashSet hashSet = new HashSet();
hashSet.addAll(list);
return new ArrayList(hashSet);
}
}
练习二
public class Person {
String name;
int age;
public Person() {
}
public Person(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public String toString() {
return "Person{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Person person = (Person) o;
if (age != person.age) return false;
return name != null ? name.equals(person.name) : person.name == null;
}
@Override
public int hashCode() {
int result = name != null ? name.hashCode() : 0;
result = 31 * result + age;
return result;
}
}
//Person类已经重写hashCode()方法和equals()方法了
//测试类
public class text {
public static void main(String[] args) {
HashSet hashSet = new HashSet();
Person p1 = new Person("AA",1001);
Person p2 = new Person("BB",1002);
hashSet.add(p1);
hashSet.add(p2);
System.out.println(hashSet);//[Person{name='AA', age=1001}, Person{name='BB', age=1002}]
p1.name = "CC";
hashSet.remove(p1);
System.out.println(hashSet);//[Person{name='CC', age=1001}, Person{name='BB', age=1002}]
hashSet.add(new Person("CC",1001));
System.out.println(hashSet);//[Person{name='CC', age=1001}, Person{name='CC', age=1001}, Person{name='BB', age=1002}]
hashSet.add(new Person("AA",1001));
System.out.println(hashSet);//[Person{name='CC', age=1001}, Person{name='CC', age=1001}, Person{name='AA', age=1001}, Person{name='BB', age=1002}]
}
}
Map接口
Map接口继承树
-
Map：双列数据，存储key - value对的数据
-
HashMap：作为Map的主要实现类；线程不安全的，效率高；可以存储null的key和value。
-
Map map = new HashMap(); map.put(null,123); map.put(null,null); System.out.println(map);//{null=null} Map map1 = new Hashtable(); map1.put(null,123);//NullPointerException异常 map1.put(123,null);//NullPointerException异常 map1.put(null,null);//NullPointerException异常 System.out.println(map1);- LinkedHashMap：保证在遍历map元素时，可以按照添加的顺序实现遍历。原因：在原有的HashMap底层结构基础上，添加了一对指针，指向前一个和后一个元素。好处：对于频繁的遍历操作，此类执行效率高于HashMap。
-
TreeMap：按照添加的key - value对进行排序，实现排序遍历。 此时考虑key的自然排序或定制排序。底层使用红黑树。
-
Hashtable：作为古老的实现类；线程安全，效率低；不能存储null的key和value。
- Properties：常用来处理配置文件，key和value都是String类型
-
HashMap的底层：数组 + 链表 （jdk 7 之前）
? 数组 + 链表 + 红黑树 （jdk 8 ）
-
面试题：
- HashMap的底层实现原理？
- HashMap和Hashtable的异同？
- CurrentHashMap 与 Hashtable异同？
Map结构的理解
- Map中的key：是无序的，不可重复的，使用Set存储所有的key。 这就要求：key所在的类要重写equals()方法和hashCode()（以HashMap为例）
- Map中的value：无序的可重复的，使用Collection存储所有的value。 这就要求value所在的类要重写equals()
- 一个键值对：key - value构成了一个Entry对象，
- Map中的entry：无序的，不可重复的，使用Set存储所有的entry
HashMap的底层实现原理（重点）
- 以 jdk 7 为例说明：
HashMap map = new HashMap();
//在实例化之后，底层创建了长度是16的一维数组Entry[] table。
// ...可能已经已经执行过多次put...
map.put(key1,value);
//首先，调用key1所在类的hashCode()计算key1哈希值经过某种算法以后，得到在Entry数组中的存放位置，
//如果此位置上的数据为空，此时的key1 - value1添加成功。 --情况1
//如果此位置上的数据不为空，（意味着此位置上存在一个或多个数据(以链表形式存在)），比较key1和已经存在的一个或多个数据的哈希值：
// 如果key1的哈希值与已经存在的数据的哈希值都不同，此时key1 - valueltion添加成功。 --情况2
// 如果key1的哈希值和已经存在的某一个数据(key2 - value2)的哈希值相同，继续比较：调用key1所在类的equals()方法，比较：
// 如果equals()返回false:此时key1 - value1添加成功。--情况3
// 如果equals()返回true:使用value1替换value2.
// 补充：关于情况2和情况3：此时key1 - value1和原来的数据以链表的方式存储。
// 在不断的添加过程中，会涉及到扩容问题，当超出临界值（且要存放的位置非空）时，默认的扩容方式；扩容为原来
//容量的2 倍,并将原有的数据复制过来。
- jdk 8 相较于jdk 7在底层实现方面 的不同；
- new HashMap()：底层没有创建一个长度为16 的数组
- jdk 8 底层的数组是：Node[]，而非Entry[]
- 首次调用put()方法时，底层创建长度为16的数组
- jdk 7 底层结构只有：数组 + 链表，jdk 8 中底层结构：数组 + 链表 + 红黑树。当数组某一个索引位置上的元素以链表形式存在的数据个数 > 8 且当前数组的长度 > 64时，此时此索引位置上的所有数据改为使用红黑树存储。
HashMap源码中的重要常量
- DEFAULT_INITIAL_CAPACITY : HashMap的默认容量，16
- DEFAULT_LOAD_FACTOP : HashMap的默认加载因子：0.75
- threshold：扩容的临界值，=容量*填充因子：16 * 0.75 = 12
- TREEIFY_THRESHOLD: Bucket中链表长度大于该默认值（8），转化为红黑树
- MIN_TREEIFY_CAPACITY: 桶中的Node被树化时最小的hash表容量：64
LinkedHashMap的底层实现原理（了解）
public class Demo02 {
public static void main(String[] args) {
Map map =new HashMap();
map.put(123,"AA");
map.put(345,"BB");
map.put(12,"CC");
System.out.println(map);//{345=BB, 123=AA, 12=CC}
Map map1 = new LinkedHashMap();
map1.put(123,"AA");
map1.put(345,"BB");
map1.put(12,"CC");
//LinkedHashMap输出时会记录你添加的顺序
System.out.println(map1);//{123=AA, 345=BB, 12=CC}
}
}
源码中：
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中定义的方法
-
添加，删除，修改操作：
- Object put(Object key,Object value)：将指定key - value添加到（或修改）当前map对象中
- void putAll(Map m)：将m中的所有Key - value对存放到当前map中
- Object remove(Object key)：移除指定key的key - value对，并返回value
- void clear()：清空当前map中的所有数据
-
元素查询的操作：
- Object get(Object key)：获取指定key对应的value
- boolean contiansKey(Object key)：是否包含指定的key
- boolean contiansValue(Object value)：是否包含指定的key
- int size()：返回map中key - value对的个数
- boolean isEmpty()：判断当前map是否为空
- boolean equas(Object obj)：判断当前map和参数对象obj是否相等
-
元视图操作的方法：
- Set keySet():返回所有key构成的Set集合
- Collection values()：返回所有value构成的Collection集合
- Set entrySet()：返回所有key - value对构成的Set集合
-
总结：常用方法：
- 添加 ：put(Object key,Object value)
- 删除： remove(Object key)
- 修改： put(Object key,Object value)
- 查询：get(Object key)
- 长度： size()
- 遍历：KeySet() 、values() 、entrySet()
/*- 添加，删除，修改操作：
- Object put(Object key,Object value)：将指定key - value添加到（或修改）当前map对象中
- void putAll(Map m)：将m中的所有Key - value对存放到当前map中
- Object remove(Object key)：移除指定key的key - value对，并返回value
- void clear()：清空当前map中的所有数据
*/
Map map =new HashMap();
//添加
map.put("AA",123);
map.put(45,123);
map.put("BB",56);
//体现修改
map.put("AA",87);
System.out.println(map);//{AA=87, BB=56, 45=123}
HashMap map1 = new HashMap();
map1.put("CC",123);
map1.put("DD",123);
map .putAll(map1);
System.out.println(map);//{AA=87, BB=56, CC=123, DD=123, 45=123}
//remove(Object key)
Object value = map.remove("CC");
System.out.println(value);//123
System.out.println(map);//{AA=87, BB=56, DD=123, 45=123}
//clear():清空里面的数据
map.clear();//map = null
System.out.println(map.size());//0
System.out.println(map);//{}
public class Demo04 {
public static void main(String[] args) {
/*
- 元素查询的操作：
- Object get(Object key)：获取指定key对应的value
- boolean contiansKey(Object key)：是否包含指定的key
- boolean contiansValue(Object value)：是否包含指定的key
- int size()：返回map中key - value对的个数
- boolean isEmpty()：判断当前map是否为空
- boolean equas(Object obj)：判断当前map和参数对象obj是否相等
*/
Map map =new HashMap();
map.put("AA",123);
map.put(45,123);
map.put("BB",56);
//Object get(Object key)
System.out.println(map.get(45));//123
//contiansKey(Object key)
boolean bb = map.containsKey("BB");
System.out.println(bb);//true
//contiansValue(Object value)
boolean b = map.containsValue(123);//有两个值，他找到一个了，就不会接着往下找
System.out.println(b);//true
//isEmpty()
map.clear();
System.out.println(map.isEmpty());//true
}
}
public class Demo05 {
public static void main(String[] args) {
/*
- 元视图操作的方法：
- Set keySet():返回所有key构成的Set集合
- Collection values()：返回所有value构成的Collection集合
- Set entrySet()：返回所有key - value对构成的Set集合
*/
Map map =new HashMap();
map.put("AA",123);
map.put(45,123);
map.put("BB",56);
//遍历所有的key集，KeySet()
Set set = map.keySet();
Iterator iterator = set.iterator();
while (iterator.hasNext()){
System.out.println(iterator.next());
}
//遍历所有的value集：values()
Collection values = map.values();
for (Object value : values) {
System.out.println(value);
}
//遍历所有的Key - value
//方式一： entrySet()
Set set1 = map.entrySet();
Iterator iterator1 = set1.iterator();
while (iterator1.hasNext()){
Object obj = iterator1.next();
Map.Entry entry = (Map.Entry)obj;
System.out.println(obj);
System.out.println(entry.getKey()+"--->"+entry.getValue());
/*
AA=123
AA--->123
BB=56
BB--->56
45=123
45--->123
*/
}
//方式二：
Set set2 = map.keySet();
Iterator iterator2 = set1.iterator();
System.out.println("======");
while (iterator2.hasNext()){
Object Key = iterator2.next();
Object value = map.get(Key);
System.out.println(Key+"====="+value);
}
}
}