2020.8.2 泛型

发布于 2020-08-02  15 次阅读


1.学习内容

  • Collections

    • Collections.sort( 集合 , 比较器)
    • 比较器Comparator接口
      • 实现方法compare()方法,可以排序对象
  • for循环增强版

    • 特点:
      • 实现了Iterable就可以使用
      • 通常是用来遍历,不在遍历中修改增加等操作
      • 增强for循环就是javac编译时改成传统形式
    • 优点缺点:
      • 方便书写代码,
      • 不方便修改元素,效率低
  • Java 泛型

    • 泛型特点:

      • JDK出现的新特性
      • 泛型:让程序更安全的运行(没有泛型,集合可以随意存放任意类型)
      • 编译时候有效,class没有泛型
    • 通配符

      • ?任何类型
      • 上限限定 List
        • 限定为子类,子孙类

      • 下线限定 List
        • 限定为父类,以及父类以上

    • 泛型种类

      • 泛型类
        • 定义:类名\<泛型>
        • 静态类中,不能访问类的泛型
      • 泛型方法
        • 定义:public static \ void shot(T t)
      • 泛型接口
        • 接口定义 和方法定义 都差不多
          • 实现泛型类:不明确泛型 AND 明确泛型
          • 不明确泛型:就是泛型还是调用者指定\
        • 明确泛型: 实现类就指定\ 灵活性弱
    • E,T,K,V

      • 原理
        • 其实就是变量
        • 可以赋值引用类型(数据类型)
      • E 代表element 元素
      • T 代表type 类型
      • K key V value
  • Set集合

    • 特点:
      • 元素不能重复
      • 没有索引值(只能使用迭代器和加强for循环)
      • 底层实现:HashMap
    • Set接口的实现类
      • HashSet,LinkedHashSet
    • 常用方法
      • add、isEmpty,size,toArray等等,基本和List相同
      • hashCode() 哈希地址
        • 对象@转换成十六进制
        • String重写了hashCode建立了自己的哈希值
  • 哈希表(集合存储使用)

    • 根据哈希值访问元素
      • 数组长度
    • 哈希表实现
      • 哈希表存储采用数组+链表+红黑树实现(JDK8)
      • 当元素够8个,就改变为红黑树
    • 使用hash值,准确定位到元素位置
    • 哈希表存储字符对象过程图
    • 哈希表如何判定元素重复
      • hashCode()和equals()方法
      • 如果需要指定方式,就需要重写equals方法指定规则
    • 哈希表初始容量
      • 数组长度为16个
      • 数组容量不够,扩充原数组两倍
    • 加载因子为0.75
      • 加载因子,用来扩充数组
      • 数组容量达到75%就扩充数组
    • 桶:()
      • 数组上挂的链表节点
      • 数量越多,查找越慢
  • LinkedHashSet集合

    • 和HashSet使用上没有区别
    • 是一个双链表,有存取顺序

2.扩展延伸知识

3.灵感代办

4.复习内容

  • 哈希表源代码分析

    HashSet集合本身并不提供功能,底层依赖HashMap集合,HashSet构造方法中创建了HashMap对象:

    map = new HashMap<>();

    因此源代码分析是分析HashMap集合的源代码,HashSet集合中的add方法调研的是HashMap集合中的put方法。

    HashMap无参数构造方法的分析

    //HashMap中的静态成员变量
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    public HashMap() {
      this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

    解析:使用无参数构造方法创建HashMap对象,将加载因子设置为默认的加载因子,loadFactor=0.75F。

    HashMap有参数构造方法分析

    public HashMap(int initialCapacity, float loadFactor) {
      if (initialCapacity < 0)
          throw new IllegalArgumentException("Illegal initial capacity: " +
      initialCapacity);
      if (initialCapacity > MAXIMUM_CAPACITY)
          initialCapacity = MAXIMUM_CAPACITY;
      if (loadFactor <= 0 || Float.isNaN(loadFactor))
          throw new IllegalArgumentException("Illegal load factor: " +
      loadFactor);
      this.loadFactor = loadFactor;
      this.threshold = tableSizeFor(initialCapacity);
    }

    解析:带有参数构造方法,传递哈希表的初始化容量和加载因子

    • 如果initialCapacity(初始化容量)小于0,直接抛出异常。
    • 如果initialCapacity大于最大容器,initialCapacity直接等于最大容器
    • MAXIMUM_CAPACITY = 1 << 30 是最大容量 (1073741824)
    • 如果loadFactor(加载因子)小于等于0,直接抛出异常
    • tableSizeFor(initialCapacity)方法计算哈希表的初始化容量。
    • 注意:哈希表是进行计算得出的容量,而初始化容量不直接等于我们传递的参数。

    tableSizeFor方法分析

    static final int tableSizeFor(int cap) {
      int n = cap - 1;
      n |= n >>> 1;
      n |= n >>> 2;
      n |= n >>> 4;
      n |= n >>> 8;
      n |= n >>> 16;
      return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

    解析:该方法对我们传递的初始化容量进行位移运算,位移的结果是 8 4 2 1 码

    • 例如传递2,结果还是2,传递的是4,结果还是4。
    • 例如传递3,结果是4,传递5,结果是8,传递20,结果是32。

    Node 内部类分析

    哈希表是采用数组+链表的实现方法,HashMap中的内部类Node非常重要

    static class Node<K,V> implements Map.Entry<K,V> {
       final int hash;
       final K key;
       V value;
       Node<K,V> next;
    Node(int hash, K key, V value, Node<K,V> next) {
       this.hash = hash;
       this.key = key;
       this.value = value;
       this.next = next;
    }

    解析:内部类Node中具有4个成员变量

    • hash,对象的哈希值
    • key,作为键的对象
    • value,作为值得对象(讲解Set集合,不牵扯值得问题)
    • next,下一个节点对象

    存储元素的put方法源码

    public V put(K key, V value) {
      return putVal(hash(key), key, value, false, true);
    }

    解析:put方法中调研putVal方法,putVal方法中调用hash方法。

    • hash(key)方法:传递要存储的元素,获取对象的哈希值
    • putVal方法,传递对象哈希值和要存储的对象key

    putVal方法源码

    Node<K,V>[] tab; Node<K,V> p; int n, i;
      if ((tab = table) == null || (n = tab.length) == 0)
          n = (tab = resize()).length;

    解析:方法中进行Node对象数组的判断,如果数组是null或者长度等于0,那么就会调研resize()方法进行数组的扩容。

    resize方法的扩容计算

    if (oldCap > 0) {
       if (oldCap >= MAXIMUM_CAPACITY) {
           threshold = Integer.MAX_VALUE;
           return oldTab;
       }
       else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                oldCap >= DEFAULT_INITIAL_CAPACITY)
           newThr = oldThr << 1; // double threshold
    }

    解析:计算结果,新的数组容量=原始数组容量<<1,也就是乘以2。

    确定元素存储的索引

    if ((p = tab[i = (n - 1) & hash]) == null)
       tab[i] = newNode(hash, key, value, null);

    解析:i = (数组长度 - 1) & 对象的哈希值,会得到一个索引,然后在此索引下tab[i],创建链表对象。

    不同哈希值的对象,也是有可能存储在同一个数组索引下。

    遇到重复哈希值的对象

    Node<K,V> e; K k;
    if (p.hash == hash &&
       ((k = p.key) == key || (key != null && key.equals(k))))
           e = p;

    解析:如果对象的哈希值相同,对象的equals方法返回true,判断为一个对象,进行覆盖操作。

    else {
       for (int binCount = 0; ; ++binCount) {
           if ((e = p.next) == null) {
               p.next = newNode(hash, key, value, null);
           if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
               treeifyBin(tab, hash);
           break;
    }

    解析:如果对象哈希值相同,但是对象的equals方法返回false,将对此链表进行遍历,当链表没有下一个节点的时候,创建下一个节点存储对象。

5.学习成果&问题


Ares个人进阶之路