2018-08-17 工作日志

Java Map 泛型 集合

今天内容：

• Set接口
  此类实现Set接口，由哈希表（实际上是HashMap实例）支持
  
  • HashSet
  • HashSet的常用方法
  • HashSet遍历
• Map接口
  基于哈希表的Map接口实现
  
  • HashMap
  • HashMap的常用方法
  • HashMap遍历
• Arrays类和Collections类
  
  • 集合操作工具类
• Java泛型

Set接口

Set集合，无序不重复，元素可为null

HashSet

附：

package com.nl.sx816.CollectionFramework.SetDemo;
import java.util.Date;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Objects;
/**
 * Created with IntelliJ IDEA 2018.
 * Description: Set集合，无序不重复，元素可为null
 *      不同步
 * @author: 黄昭鸿
 * @date: 2018-08-17
 * Time: 9:23
 */
public class SetDemo {
    public static void main(String[] args) {
        HashSet hashSet = new HashSet();
        hashSet.add("A");
        hashSet.add("B");
        hashSet.add("C");
        hashSet.add("D");
        hashSet.add(new S("huang", 12, new Date()));
        hashSet.add(new S("huang", 12, new Date()));
        hashSet.add(new S("sun", 13, new Date()));
        hashSet.add(new S("wang", 14, new Date()));
        hashSet.add(new S());
        hashSet.add(new S());
        hashSet.add(null);
        //迭代器
        Iterator iterator = hashSet.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
        //普通迭代器
        System.out.println("普通迭代器:");
        hashSet.iterator().forEachRemaining(System.out::print);
        System.out.println(hashSet.size());
        hashSet.remove(null);
        System.out.println(hashSet.size());
        //forEach()
        hashSet.forEach(System.out::print);
    }
}
class S {
    String str;
    int i;
    Date date;
    public S() {
    }
    public S(String str, int i, Date date) {
        this.str = str;
        this.i = i;
        this.date = date;
    }
    @Override
    public String toString() {
        if (this.str == null && this.date == null) {
            return "名字null" + ",年龄" + i + ",日期null";
        } else if (this.str == null) {
            return "名字null" + ",年龄" + i + ",日期" + date.toString();
        } else if (this.date == null) {
            return "名字" + str + ",年龄" + i + ",日期null";
        } else {
            return "名字" + str + ",年龄" + i + ",日期" + date.toString();
        }
    }
    @Override
    public int hashCode() {
/*        if (str == null) {
            return "".hashCode() + i;
        } else {
            return str.hashCode() + i;
        }*/
        return Objects.requireNonNullElse(str, "").hashCode() + i;
    }
    @Override
    public boolean equals(Object obj) {
        if (obj instanceof S) {
            S s = (S) obj;
            return (this.str == null || this.str.equals(s.str)) && this.i == (s.i);
        } else {
            return false;
        }
    }
}

Map和泛型

Map接口

HashMap

基于哈希表的Map接口实现。
请注意，此实现不同步。
HashMap 的查找效率贼高
键、值允许为null，键不允许重复，后者覆盖前者

HashMap 的特点

• 底层实现是 链表数组（transient Node<K,V>[] table;,当发生 哈希冲突（碰撞）的时候，HashMap 采用 拉链法 进行解决），JDK 8 后又加了 红黑树
• 实现了 Map 全部的方法
• key 用 Set 存放，所以想做到 key 不允许重复，key 对应的类需要重写 hashCode 和 equals 方法
• 允许空键和空值（但空键只有一个，且放在第一位，下面会介绍）
• 元素是无序的，而且顺序会不定时改变
• 插入、获取的时间复杂度基本是 O(1)（前提是有适当的哈希函数，让元素分布在均匀的位置）
• 遍历整个 Map 需要的时间与 桶(数组) 的长度成正比（因此初始化时 HashMap 的容量不宜太大）
• 两个关键因子：初始容量、加载因子

HashMap 的 13 个成员变量

1.默认初始容量：16，必须是 2 的整数次方
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

哈希表容量取 2 的整数次幂，有以下 2 点好处：
1.使用减法替代取模，提升计算效率；
2.为了使不同 hash 值发生碰撞的概率更小，尽可能促使元素在哈希表中均匀地散列

2.默认加载因子的大小：0.75，可不是随便的，结合时间和空间效率考虑得到的

static final float DEFAULT_LOAD_FACTOR = 0.75f;

3.最大容量： 2^ 30 次方

static final int MAXIMUM_CAPACITY = 1 << 30;

4.当前 HashMap 修改的次数，这个变量用来保证 fail-fast 机制

transient int modCount;

5.阈值，下次需要扩容时的值，等于 容量*加载因子

int threshold;

6.树形阈值：JDK 1.8 新增的，当使用 树 而不是列表来作为桶时使用。必须必 2 大

static final int TREEIFY_THRESHOLD = 8;

7.非树形阈值：也是 1.8 新增的，扩容时分裂一个树形桶的阈值（？不是很懂 - -），要比 TREEIFY_THRESHOLD 小

static final int UNTREEIFY_THRESHOLD = 6;

8.树形最小容量：桶可能是树的哈希表的最小容量。至少是 TREEIFY_THRESHOLD 的 4 倍，这样能避免扩容时的冲突

static final int MIN_TREEIFY_CAPACITY = 64;

9.缓存的 键值对集合（另外两个视图：keySet 和 values 是在 AbstractMap 中声明的）

transient Set<Map.Entry<K,V>> entrySet;

10.哈希表中的链表数组

transient Node<K,V>[] table;
当发生 哈希冲突（碰撞）的时候，HashMap 采用 拉链法 进行解决

11.键值对的数量

transient int size;

12.哈希表的加载因子

final float loadFactor;

HashMap 的初始容量和加载因子

由于 HashMap 扩容开销很大（需要创建新数组、重新哈希、分配等等,最好在初始化的时候就指定好 HashMap 的容量），因此与扩容相关的两个因素：

• 容量：数组的数量
• 加载因子：决定了 HashMap 中的元素占有多少比例时扩容

成为了 HashMap 最重要的部分之一，它们决定了 HashMap 什么时候扩容。

HashMap 的默认加载因子为 0.75，这是在时间、空间两方面均衡考虑下的结果：

• 加载因子太大的话发生冲突的可能就会大，查找的效率反而变低
• 太小的话频繁 rehash，导致性能降低

当设置初始容量时，需要提前考虑Map中可能有多少对键值对，设计合理的加载因子，尽可能避免进行扩容。
如果存储的键值对很多，干脆设置个大点的容量，这样可以少扩容几次。

HashMap构造函数和描述

HashMap()
使用默认初始容量（16）和默认加载因子（0.75）构造一个空的HashMap。
HashMap(int initialCapacity)
使用指定的初始容量和默认加载因子（0.75）构造一个空的HashMap，容量必须是 2 的整数次方，假如你传入的是 5，返回的初始容量为 8 。
HashMap(int initialCapacity, float loadFactor)
使用指定的初始容量和加载因子构造一个空的HashMap。
HashMap(Map<? extends K,? extends V> m)
使用与指定Map相同的映射构造一个新的HashMap。

插入逻辑:

• 先调用 hash() 方法计算哈希值
• 然后调用 putVal() 方法中根据哈希值进行相关操作
• 如果当前 哈希表内容为空，新建一个哈希表
• 如果要插入的桶中没有元素，新建个节点并放进去
• 否则从桶中第一个元素开始查找哈希值对应位置
  
  • 如果桶中第一个元素的哈希值和要添加的一样，替换，结束查找
  • 如果第一个元素不一样，而且当前采用的还是 JDK 8 以后的树形节点，调用putTreeVal()进行插入
  • 否则还是从传统的链表数组中查找、替换，结束查找
  • 当这个桶内链表个数大于等于 8，就要调用 treeifyBin() 方法进行树形化
• 最后检查是否需要扩容

hash():计算对应的位置
resize():扩容
putTreeVal():树形节点的插入
treeifyBin():树形化容器

查找逻辑:

• 先计算哈希值;
• 然后再用 (n - 1) & hash 计算出桶的位置;
• 在桶里的链表进行遍历查找（时间复杂度一般跟链表长度有关）。

HashMap中的hash()

HashMap 中通过将传入键的 hashCode 进行无符号右移 16 位，然后进行按位异或，得到这个键的哈希值。

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

forEach(BiConsumer action)

//Java8特有的map遍历方式
map.forEach((k, v) -> Console.log("key:value = " + k + ":" + v));

相关博文：Java 集合框架
相关教程：Java泛型

附：

package com.nl.sx816.CollectionFramework.MapDemo;
import cn.hutool.core.lang.Console;
import java.util.*;
/**
 * Created with IntelliJ IDEA 2018.
 * Description: HashMap。键、值允许为null，键不允许重复，后者覆盖前者
 *      不同步
 *
 * @author: 黄昭鸿
 * @date: 2018-08-17
 * Time: 09:00
 */
public class HashMapDemo {
    public static void main(String[] args){
        HashMap hashMap=newHashMap();
        //线程安全的 Map
        Map m = Collections.synchronizedMap(newHashMap());
        //containsKey(Object key)
        System.out.print(hashMap.containsKey(2));
        //get(Object key)返回指定键映射到的值
        System.out.println(hashMap.get(2));
        //Set<K>    keySet()返回Set此映射中包含的键的视图。
        //Set<String> set=hashMap.keySet();
        //Collection<V>     values()返回Collection此映射中包含的值的视图。
        //Collection<String> list=hashMap.values();
        //Set<Map.Entry<K,V>>   entrySet()
        dddd(hashMap);
    }
    public static void dddd(HashMap map){
        //迭代器
        System.out.println("迭代器");
        map.entrySet().iterator().forEachRemaining(
                System.out::print
        );
        System.out.println("Java8特有的map遍历方式");
        map.forEach((k, v) -> System.out.println("key:value = " + k + ":" + v));
        //Java8特有的map遍历方式
        //map.forEach((k, v) -> Console.log("key:value = " + k + ":" + v));
        //Java8,通过Map.entrySet遍历key和value，在大容量时推荐使用
        //map.entrySet().forEach(entry -> Console.log("key:value = " + entry.getKey() + ":" + entry.getValue()));
        //Java8,通过Map.entrySet使用Iterator遍历key和value
        //map.entrySet().iterator().forEachRemaining(item -> System.out.println("key=value:" + item));
        //Java8，通过Map.keySet遍历key和value
        //map.keySet().forEach(key -> System.out.println("map.get(" + key + ") = " + map.get(key)));
        //Java8,遍历所有的value
        //map.values().forEach(System.out::println);
    }
    public static HashMap newHashMap(){
        HashMap hashMap=new HashMap();
        hashMap.put(1,"荆州");
        hashMap.put(2,"杭州");
        hashMap.put(3,"苏州");
        hashMap.put(4,"庐州");
        hashMap.put(null,"北京");
        hashMap.put(5,null);
        return hashMap;
    }
}

Java泛型

泛型提供了编译时类型安全检测机制，该机制允许程序员在编译时检测到非法的类型。
泛型的本质是参数化类型，也就是说所操作的数据类型被指定为一个参数
每一个类型参数声明部分包含一个或多个类型参数，参数间用逗号隔开。
注意类型参数只能代表引用型类型，不能是原始类型

package com.nl.sx817.generics;
/**
 * Created with IntelliJ IDEA 2018.
 * Description: Java泛型
 * 泛型提供了编译时类型安全检测机制，该机制允许程序员在编译时检测到非法的类型。
 * 注意类型参数只能代表引用型类型，不能是原始类型
 *
 * @author: 黄昭鸿
 * @date: 2018-08-17
 * Time: 14:01
 */
public class GenericMethodTest {
    /**
     * Description: 泛型方法 printArray
     *
     * @param [inputArray]
     * @return void
     * @author 黄昭鸿
     * @date 2018/8/17 14:02
     */
    public static void main(String args[]) {
        // 创建不同类型数组： Integer, Double 和 Character
        Integer[] intArray = {1, 2, 3, 4, 5};
        Double[] doubleArray = {1.1, 2.2, 3.3, 4.4};
        Character[] charArray = {'H', 'E', 'L', 'L', 'O'};
        System.out.println("整型数组元素为:");
        // 传递一个整型数组
        printArray(intArray);
        System.out.println("\n双精度型数组元素为:");
        // 传递一个双精度型数组
        printArray(doubleArray);
        System.out.println("\n字符型数组元素为:");
        // 传递一个字符型数组
        printArray(charArray);
    }
    public static <E> void printArray(E[] inputArray) {
        // 输出数组元素
        for (E element : inputArray) {
            System.out.printf("%s ", element);
        }
        System.out.println();
    }
}

有界的类型参数

package com.nl.sx817.generics;
import cn.hutool.core.util.RandomUtil;
import java.math.RoundingMode;
import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;
/**
 * Created with IntelliJ IDEA 2018.
 * Description:Java泛型——有界的类型参数
 *
 * @author: 黄昭鸿
 * @date: 2018-08-17
 * Time: 14:14
 */
public class MaximumTest {
    /**
     * Description: 要声明一个有界的类型参数，首先列出类型参数的名称，后跟extends关键字，最后紧跟它的上界。
     * 比较三个值并返回最大值
     *
     * @param [x, y, z]
     * @return T
     * @author 黄昭鸿
     * @date 2018/8/17 14:15
     */
    public static <T extends Comparable<T>> T maximum(T x, T y, T z) {
        // 假设x是初始最大值
        T max = x;
        if (y.compareTo(max) > 0) {
            //y 更大
            max = y;
        }
        if (z.compareTo(max) > 0) {
            // 现在 z 更大
            max = z;
        }
        // 返回最大对象
        return max;
    }
    public static void main(String args[]) {
        System.out.printf("%d, %d 和 %d 中最大的数为 %d\n\n", 3, 4, 5, maximum(3, 4, 5));
        System.out.printf("%.1f, %.1f 和 %.1f 中最大的数为 %.1f\n\n", 6.6, 8.8, 7.7, maximum(6.6, 8.8, 7.7));
        System.out.printf("%s, %s 和 %s 中最大的数为 %s\n", "pear", "apple", "orange", maximum("pear", "apple", "orange"));
        //
        List<?> name = newList("String");
        List<?> age = newList("Integer");
        List<?> number = newList("Number");
        List<?> gender = newList("Character");
        List<?> height = newList("Double");
        List<?> ggList = newList("Gg");
        getData(name);
        getData(age);
        getData(number);
        getData(gender);
        getData(height);
        getData(ggList);
    }
    public static void getData(List<?> data) {
        ListIterator listIterator = data.listIterator();
        while (listIterator.hasNext()) {
            System.out.println(listIterator.next());
        }
    }
    //初始化数据
    public static List<?> newList(String type) {
        switch (type) {
            case "String":
                List names = new ArrayList<String>();
                names.add("及时雨");names.add("玉麒麟");
                names.add("智多星");names.add("入云龙");
                names.add("豹子头");names.add("小李广");
                names.add("花和尚");names.add("神行太保");
                names.add("黑旋风");names.add("浪里白条");
                names.add("拼命三郎");
                return names;
            case "Integer":
                List age = new ArrayList<String>();
                for (int i = 30; i < 41; i++) {
                    age.add(i);
                }
                return age;
            case "Number":
                List number = new ArrayList<String>();
                for (int i = 0; i < 11; i++) {
                    number.add(i);
                }
                return number;
            case "Character":
                List gender = new ArrayList<String>();
                gender.add('男');gender.add('女');gender.add('男');gender.add('女');
                gender.add('男');gender.add('女');gender.add('男');gender.add('女');
                gender.add('男');gender.add('女');gender.add('男');
                return gender;
            case "Double":
                List height = new ArrayList<String>();
                height.add(RandomUtil.randomDouble(1.5, 2.1, 2, RoundingMode.HALF_UP));
                height.add(RandomUtil.randomDouble(1.5, 2.1, 2, RoundingMode.HALF_UP));
                height.add(RandomUtil.randomDouble(1.5, 2.1, 2, RoundingMode.HALF_UP));
                height.add(RandomUtil.randomDouble(1.5, 2.1, 2, RoundingMode.HALF_UP));
                height.add(RandomUtil.randomDouble(1.5, 2.1, 2, RoundingMode.HALF_UP));
                height.add(RandomUtil.randomDouble(1.5, 2.1, 2, RoundingMode.HALF_UP));
                height.add(RandomUtil.randomDouble(1.5, 2.1, 2, RoundingMode.HALF_UP));
                height.add(RandomUtil.randomDouble(1.5, 2.1, 2, RoundingMode.HALF_UP));
                height.add(RandomUtil.randomDouble(1.5, 2.1, 2, RoundingMode.HALF_UP));
                height.add(RandomUtil.randomDouble(1.5, 2.1, 2, RoundingMode.HALF_UP));
                height.add(RandomUtil.randomDouble(1.5, 2.1, 2, RoundingMode.HALF_UP));
                return height;
            case "Gg":
                List gg = new ArrayList<Gg>();
                gg.add(new Gg("天魁星","呼保义","总兵都头领"));
                gg.add(new Gg("天罡星","玉麒麟","总兵都头领"));
                gg.add(new Gg("天机星","智多星","掌管机密军师"));
                gg.add(new Gg("天闲星","入云龙","掌管机密军师"));
                gg.add(new Gg("天雄星","豹子头","马军五虎将"));
                gg.add(new Gg("天英星","小李广","马军八骠骑"));
                gg.add(new Gg("天孤星","花和尚","步军头领"));
                gg.add(new Gg("天速星","神行太保","总探声息头领"));
                gg.add(new Gg("天杀星","黑旋风","步军头领"));
                gg.add(new Gg("天慧星","拼命三郎","歩军头领"));
                gg.add(new Gg("天损星","浪里白条","水军头领"));
                return gg;
            default:
                return new ArrayList();
        }
    }
}
class Gg {
    String constellation="星宿",nickname="诨名",post="职位";
    public Gg() {}
    public Gg(String constellation, String nickname, String post) {
        this.constellation = constellation;
        this.nickname = nickname;
        this.post = post;
    }
    @Override
    public String toString() {
        return "好汉{" +
                "星宿='" + constellation + '\'' +
                ", 诨名='" + nickname + '\'' +
                ", 职位='" + post + '\'' +
                '}';
    }
}

#