Java学习笔记（19）

双列集合

键值对 一一对应

键值对对象 entry

Map

Put第一次给不存在的key，会把键值对添加到map中，返回null

Put给同一个key是会覆盖value的，返回被覆盖的值value

Remove根据key删除键值对，返回被删除的值value

Map遍历

键找值

把所有键放到单列集合中map.keyset()方法，获取每一个键，再调用map.get(key)获取每一个值

键值对

Map.entryset()获得每一键值对，放到一个set集合中

Map.Entry<string,string>：因为Entry是Map里的一个接口，所以在用Entry接口的时候，要用Map调用

Entry.getkey()  Entry.getvalue() 分别获取key和value

Lambda遍历

Foreach

写一个匿名内部类实现biconsumer接口，创建这个匿名内部类的对象

Hashmap

但是计算哈希值的时候，只会利用键计算哈希值，和值无关

键是自定义对象，要重写hashcode和equals方法，值的话就不用

package exercise;
 
import java.util.*;
 
public class exercise3 {
    public static void main(String[] args) {
        String[] arr = {"A", "B", "C", "D"};
        ArrayList<String> list = new ArrayList<>();
        Random r = new Random();
        for (int i = 0; i < 80; i++) {
            list.add(arr[r.nextInt(arr.length)]);
        }
 
        HashMap<String,Integer> hm = new HashMap<>();
        for (String s : list) {
            if (hm.containsKey(s)) {
                Integer i = hm.get(s);
                i++;
                hm.put(s, i);
            } else {
                hm.put(s, 1);
            }
        }
 
        System.out.println(hm);
 
        //求最大值
        int max = 0;
        Set<Map.Entry<String, Integer>> entries = hm.entrySet();
        for (Map.Entry<String, Integer> entry : entries) {
            if (entry.getValue() > max) {
                max = entry.getValue();
            }
        }
        
        //把和最大值相同的景点打印
        for (Map.Entry<String, Integer> entry : entries) {
            if (entry.getValue() == max) {
                System.out.println(entry.getKey());
            }
        }
 
    }
}

Linkedhashmap

Treemap

按照键进行排序

package exercise;
 
import java.util.TreeMap;
 
public class exercise4 {
    public static void main(String[] args) {
        String str = "aababcabcdabcde";
        TreeMap<Character, Integer> ts = new TreeMap<>();
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (ts.containsKey(c)) {
                Integer j = ts.get(c);
                j++;
                ts.put(c, j);
            } else {
                ts.put(c, 1);
            }
        }
 
        StringBuilder sb = new StringBuilder();
        ts.forEach((character, integer) -> sb.append(character).append(" (").append(integer).append(") "));
        System.out.print(sb);
    }
}

Hashmap的底层源码

→：是继承自Map的方法

↑：重写Map里的方法

m：是方法（同名就是构造方法，不同名就是成员方法）

f：是成员属性，可能是变量或常量

i:接口

c：内部类

Hashmap中每一个元素都是Node对象，实现entry接口

Hash：记录哈希值

Key：键

Value：值

Next：记录下一个node的地址值

Hashmap中的红黑树

Parent：父节点

Left：左子结点

Right：右子节点

Red：ture就是红色，false就是黑

Table：记录数组的地址值，装的就是每一个node对象

默认数组初始容量16

默认加载因子0.75

Hashmap最大容量2^30

Hashmap在调用空参构造的时候，底层的数组还没有创建，默认null

只是指定了加载因子为0.75

直到put的时候才真正建立数组

Hash(key)：根据键计算出哈希值

onlyifAbsent：当前的数据是否保留，false就是不保留（当新的元素添加，键相同时，值就会覆盖掉原来的）

Hashmap添加元素源码分析

Hashmap添加第一个元素

数组位置为null

Putval

Resize（）：第一次添加元素，就会在这个方法里创建新的数组

第二种情况

数组位置不为null，键不重复，挂在下面形成链表或者红黑树

第三种情况

数组位置不为null，键重复，元素覆盖

这里会直接break

走这里

把新元素的值赋值给老元素的键值对的值

Treemap源码

添加第一个元素

//表示两个元素的键比较之后的结果

    int cmp;

//表示当前要添加节点的父节点

    Entry<K,V> parent;

//表示当前的比较规则

//如果我们是采取默认的自然排序，那么此时comparator记录的是null，cpr记录的也是null

//如果我们是采取比较去排序方式，那么此时comparator记录的是就是比较器

    Comparator<? super K> cpr = comparator;

//表示判断当前是否有比较器对象

//如果传递了比较器对象，就执行if里面的代码，此时以比较器的规则为准

//如果没有传递比较器对象，就执行else里面的代码，此时以自然排序的规则为准

    if (cpr != null) {

        do {

            parent = t;

            cmp = cpr.compare(key, t.key);

            if (cmp < 0)

                t = t.left;

            else if (cmp > 0)

                t = t.right;

            else {

                V oldValue = t.value;

                if (replaceOld || oldValue == null) {

                    t.value = value;

                }

                return oldValue;

            }

        } while (t != null);

    } else {

//把键进行强转，强转成Comparable类型的

//要求：键必须要实现Comparable接口，如果没有实现这个接口

//此时在强转的时候，就会报错。

        Comparable<? super K> k = (Comparable<? super K>) key;

        do {

//把根节点当做当前节点的父节点

            parent = t;

//调用compareTo方法，比较根节点和当前要添加节点的大小关系

            cmp = k.compareTo(t.key);

            if (cmp < 0)

//如果比较的结果为负数

//那么继续到根节点的左边去找

                t = t.left;

            else if (cmp > 0)

//如果比较的结果为正数

//那么继续到根节点的右边去找

                t = t.right;

            else {

//如果比较的结果为0，会覆盖

                V oldValue = t.value;

                if (replaceOld || oldValue == null) {

                    t.value = value;

                }

                return oldValue;

            }

        } while (t != null);

    }

//就会把当前节点按照指定的规则进行添加

    addEntry(key, value, parent, cmp < 0);

return null;

 private void addEntry(K key, V value, Entry<K, V> parent, boolean addToLeft) {

    Entry<K,V> e = new Entry<>(key, value, parent);

    if (addToLeft)

        parent.left = e;

    else

        parent.right = e;

//添加完毕之后，需要按照红黑树的规则进行调整

    fixAfterInsertion(e);

    size++;

    modCount++;

}

private void fixAfterInsertion(Entry<K,V> x) {

//因为红黑树的节点默认就是红色的

    x.color = RED;

//按照红黑规则进行调整

//parentOf:获取x的父节点

//parentOf(parentOf(x)):获取x的爷爷节点

//leftOf:获取左子节点

    while (x != null && x != root && x.parent.color == RED) {

//判断当前节点的父节点是爷爷节点的左子节点还是右子节点

//目的：为了获取当前节点的叔叔节点

        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {

//表示当前节点的父节点是爷爷节点的左子节点

//那么下面就可以用rightOf获取到当前节点的叔叔节点

            Entry<K,V> y = rightOf(parentOf(parentOf(x)));

            if (colorOf(y) == RED) {

//叔叔节点为红色的处理方案

//把父节点设置为黑色

                setColor(parentOf(x), BLACK);

//把叔叔节点设置为黑色

                setColor(y, BLACK);

//把爷爷节点设置为红色

                setColor(parentOf(parentOf(x)), RED);

//把爷爷节点设置为当前节点

                x = parentOf(parentOf(x));

            } else {

//叔叔节点为黑色的处理方案

//表示判断当前节点是否为父节点的右子节点

                if (x == rightOf(parentOf(x))) {

//表示当前节点是父节点的右子节点

                    x = parentOf(x);

//左旋

                    rotateLeft(x);

                }

                setColor(parentOf(x), BLACK);

                setColor(parentOf(parentOf(x)), RED);

                rotateRight(parentOf(parentOf(x)));

            }

        } else {

//表示当前节点的父节点是爷爷节点的右子节点

//那么下面就可以用leftOf获取到当前节点的叔叔节点

            Entry<K,V> y = leftOf(parentOf(parentOf(x)));

            if (colorOf(y) == RED) {

                setColor(parentOf(x), BLACK);

                setColor(y, BLACK);

                setColor(parentOf(parentOf(x)), RED);

                x = parentOf(parentOf(x));

            } else {

                if (x == leftOf(parentOf(x))) {

                    x = parentOf(x);

                    rotateRight(x);

                }

                setColor(parentOf(x), BLACK);

                setColor(parentOf(parentOf(x)), RED);

                rotateLeft(parentOf(parentOf(x)));

            }

        }

    }

//把根节点设置为黑色

    root.color = BLACK;

}

**************************

6.课堂思考问题：

6.1TreeMap添加元素的时候，键是否需要重写hashCode和equals方法？

此时是不需要重写的。

6.2HashMap是哈希表结构的，JDK8开始由数组，链表，红黑树组成的。

既然有红黑树，HashMap的键是否需要实现Compareable接口或者传递比较器对象呢？

不需要的。

因为在HashMap的底层，默认是利用哈希值的大小关系来创建红黑树的

6.3TreeMap和HashMap谁的效率更高？

如果是最坏情况，添加了8个元素，这8个元素形成了链表，此时TreeMap的效率要更高

但是这种情况出现的几率非常的少。

一般而言，还是HashMap的效率要更高。

6.4你觉得在Map集合中，java会提供一个如果键重复了，不会覆盖的put方法呢？

此时putIfAbsent本身不重要。

传递一个思想：

代码中的逻辑都有两面性，如果我们只知道了其中的A面，而且代码中还发现了有变量可以控制两面性的发生。

那么该逻辑一定会有B面。

习惯：

boolean类型的变量控制，一般只有AB两面，因为boolean只有两个值

int类型的变量控制，一般至少有三面，因为int可以取多个值。

6.5三种双列集合，以后如何选择？

HashMap LinkedHashMap TreeMap

默认：HashMap（效率最高）

如果要保证存取有序：LinkedHashMap

如果要进行排序：TreeMap