Table of Contents

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.扩展延伸知识

|= 和 &= 运算
- 按位与，按位或
8421编码
- https://baike.baidu.com/item/8421%E7%A0%81/4405565?fromtitle=8421%E7%BC%96%E7%A0%81&fromid=857812&fr=aladdin
Java 中字符串的hashCode
- 重写了hashCode
- 31*上一次计算的哈希值+字符ASCII编码
- 31是指数，降低哈希碰撞率
- 尽量避免哈希值相同，实际情况中不能完全避免
Java中String是什么类型；
- char类型的数组
红黑树
- 自平衡二叉查找树
- 查找数据很快，10亿数据不到30次找到
- https://www.jianshu.com/p/e136ec79235c
java中比较技巧（返回整数）
- 两个整数之间做减法运算
Iterator和Iterable

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.学习成果&问题

来自为知笔记(Wiz)

2020.8.2 泛型

1.学习内容

Collections

for循环增强版

Java 泛型

泛型特点：

通配符

泛型种类

E，T，K，V

Set集合

哈希表（集合存储使用）

LinkedHashSet集合

2.扩展延伸知识

|= 和 &= 运算

8421编码

Java 中字符串的hashCode

Java中String是什么类型；

红黑树

java中比较技巧（返回整数）

Iterator和Iterable

3.灵感代办

4.复习内容

哈希表源代码分析

HashMap无参数构造方法的分析

HashMap有参数构造方法分析

tableSizeFor方法分析

Node 内部类分析

存储元素的put方法源码

putVal方法源码

resize方法的扩容计算

确定元素存储的索引

遇到重复哈希值的对象

5.学习成果&问题

2020.8.1 集合基础知识

2020.8.4 复习python