Java高级编程day22

Tree 自然排序与定制排序练习题

1.定义一个Employee类。
该类包含：private成员变量name,age,birthday,其中birthday为
MyDate类的对象；
并为每一个属性定义getter,setter方法南
并重写toString方法输出name,age,brthday.
MyDate类包含：
private成员变量year,month,day;并为每一个属性定义getter,setter
方法；
创建该类的5个对象，并把这些对象放入TreeSet集合中（下一章：
TreeSet需使用泛型来定义)
分别按以下两种方式对集合中的元素进行排序，并遍历输出：
1).使Employee实现Comparable接口，并按name排序，
2).创建TreeSet时传入Comparator对象，按生日日期的先后排序。

Employee类

public class Employee implements Comparable {
    private String name;
    private int age;
    private MyDate birthday;

    public Employee(String name, int age, MyDate birthday) {
        this.name = name;
        this.age = age;
        this.birthday = birthday;
    }

    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 getBirthday() {
        return birthday;
    }

    public void setBirthday(MyDate birthday) {
        this.birthday = birthday;
    }

    @Override
    public String toString() {
        return "Employee{" +
                "name='" + name + '\'' +
                ", age=" + age +
                ", birthday=" + birthday +
                '}';
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Employee)) return false;
        Employee employee = (Employee) o;
        return age == employee.age && Objects.equals(name, employee.name) && Objects.equals(birthday, employee.birthday);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age, birthday);
    }

    @Override
    public int compareTo(Object o) {
        //使Employee实现Comparable接口，并按name排序
        if(o instanceof Employee){
            return ((Employee) o).getName().compareTo(this.name);
        }
        throw new RuntimeException("类型不匹配");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

MyData类

public class MyDate implements Comparable{
    private Integer year;
    private Integer month;
    private Integer day;

    public MyDate(int year, int month, int day) {
        this.year = year;
        this.month = month;
        this.day = 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;
    }

    @Override
    public String toString() {
        return "MyDate{" +
                "year=" + year +
                ", month=" + month +
                ", day=" + day +
                '}';
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof MyDate)) return false;
        MyDate myDate = (MyDate) o;
        return year == myDate.year && month == myDate.month && day == myDate.day;
    }

    @Override
    public int hashCode() {
        return Objects.hash(year, month, day);
    }

    @Override
    public int compareTo(Object o) {
        if(o instanceof MyDate){
            if(((MyDate) o).year>=((MyDate) o).year){
            return  ((MyDate) o).year.compareTo(this.year);
            }else if(((MyDate) o).month>=this.month){
                return ((MyDate) o).month.compareTo(this.month);
            }else if(((MyDate) o).day>=this.day){
                return ((MyDate) o).day.compareTo(this.day);
            }else{
                return -1;
            }

        }
        throw new RuntimeException("二者类型不匹配");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

Test类

public class Test {
    public static void main(String[] args) {
        Employee employee = new Employee("有道", 18, new MyDate(2001, 10, 4));
        Employee employee1 = new Employee("有道1", 18, new MyDate(2011, 10, 4));
        Employee employee2 = new Employee("有道2", 18, new MyDate(2051, 10, 4));
        Employee employee3 = new Employee("有道3", 18, new MyDate(2101, 10, 4));

        TreeSet treeSet = new TreeSet(new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                if(o1 instanceof Employee && o2 instanceof Employee) {
                    return ((Employee) o1).getBirthday().compareTo(((Employee) o2).getBirthday());
                }
                throw new RuntimeException("类型不匹配");
            }
        });
        treeSet.add(employee);
        treeSet.add(employee1);
        treeSet.add(employee2);
        treeSet.add(employee3);
        System.out.println(treeSet);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

Map接口

|—Map:双列数据，存储key-value对的数据，----- 类似于高中的函数：y=f(x);

​ |—HashMap:Map接口的主要实现类，线程不安全，效率高，可以存储null的key与value

​ |—LinkedHashMap：可以按照存储顺序进行遍历，对于频繁的遍历，效率高于HashMap，在原有的HashMap的基础上添加了一对指针，一个指向前一个， 一个指向后一个

​ |—TreeMap：保证按照添加的key-Value对进行排序，实现排序遍历。此时考虑key的自然排序与定制排序

​ 底层使用红黑树

​ |—HashTable：Map接口的古老实现类，线程安全，效率低 ，不能存储null的key与value

​ |—properties：主要用于配置文件，key和value必须为String类型

HashMap的底层：数组+链表（jdk7之前）

​ 数组+链表+红黑树（jdk8）

面试题
1.HashMap的底层实现原理？
2.HashMap和Hashtable的异，同？
3.CurrentHashMap与Hashtable的异同？（暂时不讲）

HashMap的底层实现原理

以jdk7为例说明：
HashMap map= new HashMap():
在实例化以后，底层创建了长度是16的一维数组Entry[]table。
可能已经执行过多次put.·
map.put(key1,value1):
首先，调用key1所在类的hashCode()计算key1哈希值，此哈希值经过某种算法计算以后，得到在Entry数组中的存放位置。
如果此位置上的数据为空，此时key1-value1添加成功。—情况1
如果此位置上的数据不为空，（意味着此位置上存在一个或多个数据（以链表形式存在）)，比较key1和已经存在的一个或多个数据
的哈希值：
如果key1的哈希值与己经存在的数据的哈希值都不相同，此时key1-value1添加成功。—情况2
如果key1的哈希值和已经存在的某一个数据(key2-value2)的哈希值相同，继续比较：调用key1所在类的equals(key2)
如果equals()返回false:此时key1-value:1添加成功。—情况3
如果equals()返回true:使用value1替换value2。
补充：关于情况2和情况3：此时key1-value1和原来的数据以链表的方式存储。
在不断的添加过程中，会涉及到扩容问题，当超出临界值（且要存放的位置非空）时，扩容，默认的扩容方式：扩容为原来容量的2倍，并将原有的数据复制过来。

jdk8相较于jdk7在底层实现方面的不同：
1.new HashMap():底层没有创建一个长度为16的数组
2.jdk8底层的数组是：Node[],而非Entry[]
3.首次调用put()方法时，底层创建长度为16的数组
4.jdk7底层结构只有：数组+链表。jdk8中底层结构：数组+链表+红黑树。
当数组的某一个索引位置上的元素以链表形式存在的数据个数>8且当前数组的长度>64时，
此时此素引位置上的所有数据政为使用红黑树存储。

DEFAULT INITIAL CAPACITY:HashMap的默认容量，16
DEFAULT_LOAD_FACTOR:HashMap的默认加载因子：0.75
threshold:扩容的临界值，=容量*填充因子：16*0.75=>12
TREEIFY THRESHOLD:Bucket中链表长度大于该默认值，转化为红黑树：8
MIN_TREEIFY_CAPACITY:桶中Node被树化时最小hash表容量：64

Map常用方法

Object get(Object key):获取指定key对应value
booLean containsKey(Object key):是否包含指定的key
boolean containsValue(Object value):是否包含指定value
int size():返回map中key-value.对的个数
boolean isEmpty():判断当前map是否为空
boolean equals(Object obj):判断当前map和参数对象obj是否相等

元视图操作的方法：
Set keySet():返回所有key构成set集合
Collection values():返回所有value构成的Collection.集合
Set entrySet():返回所有key-value.对构成set集合

添加、删除、修改操作：
Object put(Object key,Object value):将指定key-value.添加到（或修改）当前map对象中
void putAll(Mapm):将m中的所有key-value.对存放到当前map中
Object remove(Object key):移除指定key欹ey-value.对，并返回jalue
void clear():清空当前map中的所有数据

总结：常用方法：

添加：put(Object key,object value,)
删除：remove(object key)
修改：put(Object key,Object value)
查询：get(Object key)
长度：size(）
遍历：keySet()/values()/entrySet()

TreeMap

自然排序，定制排序

public class TreeMapTest {
    public static void main(String[] args) {
        TreeMap treeMap = new TreeMap();
        User u1 = new User("A", 20);
        User u2 = new User("B", 21);
        User u3 = new User("C", 22);
        User u4 = new User("D", 23);

        treeMap.put(u1, 98);
        treeMap.put(u2, 88);
        treeMap.put(u3, 78);
        treeMap.put(u4, 68);

        Iterator iterator = treeMap.entrySet().iterator();
        while (iterator.hasNext()) {
            Object next = iterator.next();
            //entrySet都是Set元素
            Map.Entry users = (Map.Entry) next;
            System.out.println(users.getKey() + "-------" + users.getValue());
        }
        System.out.println("***************************************************************");
        TreeMap treeMap1 = new TreeMap(new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                if(o1 instanceof User&& o2 instanceof User)
                return Integer.compare(((User) o1).getAge(),((User) o2).getAge());
                throw new RuntimeException("类型不匹配");
            }
        });
        treeMap1.put(u1, 98);
        treeMap1.put(u2, 88);
        treeMap1.put(u3, 78);
        treeMap1.put(u4, 68);
        //System.out.println(treeMap1);
        Set set = treeMap1.entrySet();
        Iterator iterator1 = set.iterator();
        while (iterator1.hasNext()){
            Object next = iterator1.next();
            Map.Entry user2= (Map.Entry) next;
            System.out.println(user2.getKey()+"----"+user2.getValue());
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

properties

作为配置文件使用

public class PropertiesTest {
    public static void main(String[] args) throws IOException {
        Properties properties = new Properties();
        //创建配置文件的文件流
        FileInputStream fileInputStream = new FileInputStream("JDBC.properties");
        //加载文件流
        properties.load(fileInputStream);
        System.out.println(properties.getProperty("name"));
        System.out.println(properties.getProperty("password"));
    }
}
1
2
3
4
5
6
7
8
9
10
11

备注：properties配置文件要在工程目录文件下创建

Collections工具类的使用

可以操作Set Map List

reverse(List):反转Lst中元素的顺序
shuffle(List):对List集合元素进行随机排序
sort(List):根据元素的自然顺序对指定List集合元素按升序排序
sort(List,Comparator):根据指定的Comparator产生的顺序对List集合元素进行排序
swap(List,int,int):将指定List集合中的i处元素和j处元素进行交换
Object max(Collection):根据元素的自然顺序，返回给定集合中的最大元素
object max(Collection,Comparator):根据Comparator指定的顺序，返回给定集合中的最大值
object min(Collection)
object min(Collection,Comparator)
int frequency(Collection,Object):返回指定集合中指定元素的出现次数
void copy(List dest,List src):将src中的内容复制到dest中
boolean replaceAll(List list,Object oldVal,Object newVal):使用新值替换List对象

synchronizedXxx()：将进程不安全的转为进程安全的

例如：ArrayList HashMap HashSet等等

public class CollectionsTest {
    public static void main(String[] args) {
        ArrayList list = new ArrayList();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(1);
        list.add(1);
        ArrayList list1 = new ArrayList();
        list1.add('A');
        list1.add('B');
        list1.add('C');
        list1.add('D');
        System.out.println(list);
        Collections.reverse(list);
        System.out.println(list);
        Collections.shuffle(list);
        System.out.println(list);
        Collections.shuffle(list);
        System.out.println(list);
        list.sort(new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                if(o1 instanceof Integer&&o2 instanceof Integer){
                   return -Integer.compare((int) o1,(int) o2);
                }
                throw new RuntimeException("类型不匹配");
            }
        });
        System.out.println(list);
        Collections.sort(list);
        System.out.println(list);
        Collections.swap(list,0,2);
        System.out.println(list);
        System.out.println(Collections.max(list));
        System.out.println(Collections.min(list));
        System.out.println(Collections.frequency(list, 1));
        Collections.copy(list,list1);
        System.out.println(list);
        Collections.replaceAll(list, 'D', "高有道");
        System.out.println(list);
        System.out.println("********************");
        Set set = new HashSet();
        set.add("A");
        set.add("b");
        set.add("c");
        set.add("d");
        System.out.println(Collections.max(set));
        Map map = new HashMap();
        map.put(1,123);
        map.put(2,123321);
        map.put(3,123111);
        map.put(4,123222);
        map.put(5,123333);

    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

cope

正确方法：

List<Object> objects = Arrays.asList(new Object[list.size()]);
Collections.copy(objects,list);
1
2

练习

1.请从键盘随机输入10个整数呆存到List中，并按倒序、从大到小的顺序显示出来

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    ArrayList list = new ArrayList();
    System.out.println("输入需要输入的数量：");
    int num = scanner.nextInt();
    for (int i = 0; i < num; i++) {
        System.out.println("请输入整数：");
        int number=scanner.nextInt();
        list.add(number);
    }
    Collections.sort(list, new Comparator() {
        @Override
        public int compare(Object o1, Object o2) {
            if(o1 instanceof Integer&&o2 instanceof Integer){
                return -Integer.compare((int)o1,(int)o2);
            }
            throw new RuntimeException("类型不匹配");
        }
    });
    System.out.println(list);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2.请把学生名与考试分数录入到集合中，并按分数显示前三名成绩学员的名字。
TreeSet(Student(name,score,id));

public class TreeSetTest {
    public static void main(String[] args) {
        TreeSet treeSet = new TreeSet();
        treeSet.add(new Student("有道",99,1));
        treeSet.add(new Student("高有道",98,2));
        treeSet.add(new Student("有道高",79,3));
        treeSet.add(new Student("有高道",88,4));
        Iterator iterator = treeSet.iterator();
        
        for (int i=0;i<3;i++) {
            System.out.println(iterator.next());
        }

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15