img

image-20200621235419362

image-20200621235438971

1. HashMap


2.《Java核心技术卷一》P372,chap9.3:映射

  • 映射 MAP 数据结构= 「HashMap」&&「TreeMap」
  • 存放 {键KEY:值VALUE}对
  • 都只对 键(KEY)进行处理( 散列&& 搜索树排序

3.相关方法函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//哈希map初始化,自己定义Key和Value的类型
Map<String, Employee> staff = new HashMap<>();

//创建一个employee对象,用作Value
Employee harry = new Employee("Harry Hacker");

//1.:map.put(key,value)方法:将 键值对 放进HashMap
staff.put("123456",harry)//
//同一个key存两次,会覆盖,并且返回的是上一次存储的 Value值;

//2.:map.get(key) 方法:按照 Key 的值,来从HashMap中获取Value
String id = "123456";
Employee e = staff.get(id);

//get()方法还可以人为设置默认值:
Map<String, Integer> score = new HashMap<>();
int score = score.get(id,0);
//放这个Key对应的Value不存在时,返回 0;
    1. import java.util.HashMap;//导入
    2. HashMap<K, V> map = new HashMap<K, V>();//定义map,K和V是类,不允许是基本类型?
    3. put(K, V)
    4. V get(K)
    5. V remove(K)//移除K键的值,返回的是V,可以不接收
    6. size()//返回映射Map中的元素数目
    7. replace()//替换
  •  map.replace( Key,Value );
    <!--1-->
  • 9. computeIfAbsent()//

  • //如果key键为java的,就添加,并且value为key键的长度
    //这个算子就是一个和put功能差不多的算子,都是往map里面添加数据。
    
    map.computeIfAbsent("java", (key)->((String)key).length());
    <!--2-->

4.关于遍历方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//返回所有 Key-Value 对:
for(Map.Entry n: map.entrySet()){
System.out.println(n);
}

//返回所有 Key:
for(String n : map.keySet()){
System.out.println(n);
}

//返回所有Value:
for(Integer n: map.values()){
System.out.println(n);
}

5.其他:

image-20200622181415228


6.整理下HashMap里面的常见面试考点:

  1. HashMap 默认容量:

    • 默认容量是:16 = 1 << 4(位移动 = $1000_2$ = $16_{10}$);
    • 默认负载因子是:0.75(根据)(服从泊松分布):红黑树部分也是这个原理:
    • 桶中的节点个数服从泊松分布;
    • 取 $\lambda = 0.5$ ,此时 ,每个捅中元素个数为 【0,8】个的概率分别如图所示,大于八个,基本已经到达百万分之一的级别,所以 Java8 中选择以 8 作为一个临界数字,来决定是否将链表转化为 红黑树
    • 其中,在 最大桶元素个数 = 7 时,不变,作为缓冲,以防止过于频繁的转换消耗;

    image-20200622234017327

  2. 如何扩容?

    • $2^n$ 的形式,每次翻两倍;(这和 Hash 的工作机制有关:(n - 1)& hash)
    • 这样子的好处是,($2^n$-1)= 一个全为1 的二进制树,计算更快;
  3. 为什么HashMap的数组大小一定要是 2 的幂?

    • 和 Hash 的工作机制有关;HashMap求索引时用&运算,index=(n-1)&hash

    • n = length : 表长度 = $2^n$

    • (HashTable求索引用模运算,index = (hash & 0x7FFFFFFF) % n)

    • :只有这样才能保证 经过 ( $2^n $ ) 操作后得到全是1 的值;

    • 然后这样才能经过非常快速的位运算,快速拿到数组下标,并且能保证分布均匀

    • 若不是 $2^n$, 则运算过后,会有0存在,那么就会导致,不管 和他进行按位与 运算的数字是多少,都会出现某些位永远是 0,那么就会导致,某些 里的元素永远都是 0个,不均匀且不合理;

  4. HashMap 为什么是线程不安全的?

    • 在接近临界点时,若此时两个或者多个线程进行put操作,都会进行resize(扩容)和reHash(为key重新计算所在位置),而reHash在并发的情况下可能会形成链表环
    • 总结来说就是在多线程环境下,使用HashMap进行put操作会引起死循环,导致CPU利用率接近100%,所以在并发情况下不能使用HashMap。
    • 为什么在并发执行put操作会引起死循环?是因为多线程会导致HashMap的Entry链表形成环形数据结构,一旦形成环形数据结构,Entry的next节点永远不为空,就会产生死循环获取Entry。
    • jdk1.7的情况下,并发扩容时容易形成链表环,此情况在1.8时就好太多太多了。
    • 因为在1.8中当链表长度达到阈值(默认长度为8)时,链表会被改成树形(红黑树)结构。如果删剩节点变成7个并不会退回链表,而是保持不变,删剩6个时就会变回链表,7不变是缓冲,防止频繁变换。
    • 在JDK1.7中,当并发执行扩容操作时会造成环形链和数据丢失的情况。
    • 在JDK1.8中,在并发执行put操作时会发生数据覆盖的情况。
  5. Java 7 到 8 做了哪些改进?为什么?

    • 如上题所述:

7.拓展

  1. 你能想到的做 HashMap 匹配的方法?

      1. 直接取模:($-2^{31}$ ~ $2^{31} -1$ )% n = (0 , $n-1$)
    • 缺点:两个:
      • 负数对 n求余,答案是负数;(所以需要额外把 负数 变为 正数 )
      • 速度较慢(相比于位运算):因为硬件中“求余”的本质是“除法”
  2. 常考的“坑”:扩容:resize()

    1. 扩容 resize( )包括 rehash ( )
    2. 机制是,当原来的容器中,容量达到了 0.75 * capacity, 再创建一个 2 * capacity 的新的桶;
    3. 然后会把旧的桶中的数据 迁移 过去,迁移的时候,伴随着重新地对原始数据进行 rehash 计算;
    4. resize()里面的 transfer()是一切问题的根源!!
    • 死锁问题::本身是线程不安全的;完全是用户的问题;
    • 哈希表最致命的缺陷:哈希碰撞——>最差情况下,会变成单链表;链表性能退化
    • 所以在java7时代的 Tomcat(2011) 中引起了问题——>可以通过一组精心设计的 恶意请求,造成 DoS(Deny of serveice)
  3. "Aa","BB","C#" 的哈希值是相同的!
    
    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
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118

    7. ![image-20200622231322114](https://blog-1301959139.cos.ap-beijing.myqcloud.com/picGo/20200626183234.png)



    ## 8. Java8的改进点 && 新API

    1. 从 **数组 + 链表**——>**数组 + 链表 / 红黑树**

    2. 扩容时,插入顺序的改进:(原来是,从旧的头先取,然后按照“头插法”插入新的桶,导致顺序不稳定)

    3. 函数方法:(java 8 引入了 Lamda 表达式)

    1. forEach
    2. compute 系列

    4. Map 的新 API

    1. Merge
    2. replace



    ***



    # 9.补充

    1. **抑或运算**:可以更简单地理解为 **不进位的 加法 !**
    2. 红黑树转换,并不是要把整张表都从链表改成红黑树,而是只要 超过 8 个元素的 那个桶,改一下形式,就行了:
    3. ![image-20200623000116947](https://blog-1301959139.cos.ap-beijing.myqcloud.com/picGo/20200626183235.png)
    4. 二叉平衡树,平均查找时间:O($log N$)
    5. 单纯的二叉树,有个极端情况:插入顺序是有序的,那么就会造成演化成 **单链表**
    6. 而红黑树,经过一定的旋转,保证了查找的效率(具体再仔细看看书)
    7. **新的 Java8 中的 resize()函数**:改进成了 **扩容时** 能保持原来的顺序,但是仍然不能保证 **线程安全**,只能说是大搭建撒后了线程冲突的概率。
    8. 所以未来可能不会再多线程情况下遇到问题,但是还是不能放心地在多线程环境下使用它!(**Linux中的任务调度 是多线程的,有用到 HashMap**)
    9. **HashCode** : 默认使用 **32位** 的 **Int** 的**HashCode**;



    ***

    # 10.面试题常见:

    1. 为什么用 数组 +链表:经典的学院派操作
    2. Hash 冲突你还知道哪些解决办法:可以在冲突的桶里面,再套一层 Hash 表;即,冲突的进行二次分流;(表中再有个表)
    3. 用Lin课的Li身体代替数组结构可以吗?:不可以,数组的随机访问是 O(1)的,不受数组长度的影响,二链表的顺序访问速度是 O(n),不能起到随机访问的效果;
    4. get()的操作?:如果第一个元素就是要求的话,那么就直接返回它;不是的话,那么,先判断该桶是什么结构,如果是红黑树,那么就用树的查找方法 查找;否则若是链表结构,就采用链表的顺序访问形式访问
    5. 为什么 String 、Integer 这样的 wrapper 类 适合作为键?:因为String是final,具有不变性,而且已经重写了 equals()和hashcode()方法了。不变性是必要的!因为 为了要计算 hashcode(),就要防止键改变,如果键再嵌入时和获取时返回不同的 hashcode 的话,就不能从 HashMap 中找到你想要的对象。
    6. 如果HashMap的大小超过了负载因子(load factor)定义的容量怎么办?:扩容:resize() & rehash()「注意,resize()的效率非常低!!!」所以如果预先知道有一个很大的表要创建,那么可以预先再创建时,就指定一个较大的空间,相当于时 **空间换时间**;避免未来的频繁resize()花费很多时间。

    ##

    ***



    # 11.红黑树:自己补充

    ![截屏2020-06-23上午12.50.42](/Users/huangshengjie/Desktop/截屏2020-06-23上午12.50.42.png)

    * [B站课程](https://www.bilibili.com/video/BV1tE411f7tP?from=search&seid=2421763921920035607):
    * [一份链接文章](https://blog.csdn.net/Mr_Helloworld_/article/details/106694724)
    * ![image-20200624005349275](https://blog-1301959139.cos.ap-beijing.myqcloud.com/picGo/20200626183236.png)
    * ![image-20200624005402070](https://blog-1301959139.cos.ap-beijing.myqcloud.com/picGo/20200626183237.png)
    * ![image-20200624005251467](https://blog-1301959139.cos.ap-beijing.myqcloud.com/picGo/20200626183238.png)



    ***

    # 12.正题:001:两数之和:Java版

    ```java
    import java.util.*;

    public class twoSum_001 {
    public static void main(String[] args) {
    }
    //暴力法
    public int[] twoSum_force(int[] nums, int target){
    for(int i=0;i< nums.length;i++){
    for(int j=i+1;j< nums.length;j++){
    if(nums[j] == target - nums[i]){
    return new int[] {i, j};
    }
    }
    }
    throw new IllegalArgumentException("No two sum soluition");
    }
    //两遍 Hash,一遍存,一遍查取;
    public int[] twoSum_HashTwice(int[] nums, int target){
    Map<Integer, Integer> map = new HashMap<>();
    for(int i=0;i< nums.length;i++){
    map.put(nums[i],i);
    }
    for(int i=0; i<nums.length;i++){
    int complement = target - nums[i];
    if(map.containsKey(complement) && map.get(complement) != i){
    return new int[]{i,map.get(complement)};
    }
    }
    throw new IllegalArgumentException("No two sum solution");
    }
    //一遍 Hash,先查,查不到就接着存;
    public int[] twoSum_HashOnce(int[] nums, int target){
    Map<Integer, Integer> map = new HashMap<>();
    for(int i=0;i<nums.length;i++){
    int complemenmt = target - nums[i];
    if(map.containsKey(complemenmt)){
    return new int[]{i,map.get(complemenmt)};
    }
    map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution.");
    }
    }

1.问题:

在Mac & Clion 中尝试使用

1
while(cin >> varient){}

来作为输入结束判断时,由于判断的是“流”结束与否(具体不钻牛角尖),即在win环境下,一般是使用 CTRL+C结束,而在Clion中这个方法不行。

2.解决:

  • 有很多博客说使用 CTRL+D /Command + D,均失败

  • 有效方法:以 Debug模式 运行程序,正确输入数据之后—>回车—> command +D


以上,谨此纪念C++修习结束。

很多人说Python 比Cpp好学,我觉得不然。这句话可能只能仅限于 使用单纯语言自身特性上;若是要再加上语言的各种外载功能包,还指不定孰优孰劣呢。

在学习TF、Torch的路上,被各种乱七八糟的工具包整的落花流水。

实习实习找的不顺,想来也是自己基础实在没有打扎实,虽说自己是反抗成为上班族的,但是在发觉自己在想衡量自己的市场价值的时候竟然这么不值钱,就心里不爽万分。

再把合成相关的东西学学吧,没啥学不会的。


06_21_2020 Sunday

@PT

1.需求:在本地查看Tensorboard

  • ssh -L 16006:127.0.0.1:6006 hsj@student.is99kdf.xyz -p 15203
    
    1
    2
    3
    4

    * 作用:将远程的服务器**6006**端口转发到本地的 **16006**端口

    *
    cd /home/sdb3/home/hsj/taco1_tf/tacotron
    1
    2
    3
    4

    * 作用:进入所要运行的 logs 文件夹所在路径

    *
    source activate py36 tensorboard --logdir ./logs-tacotron
    1
    2
    3
    4
    5

    * 开启有 Tensorboard 的环境
    * 运行 ,打开logs文件

    *
    本地浏览器打开 127.0.0.1:16006
    • 成功实现本地查看 Tensorboard
    • 再也不用像之前那样傻傻滴每次要手动下载 log 文件到本地之后才执行

2.待解决:

  • 再进一步了解一下 Tensorboard 上方的各种功能:
    • Distributions
    • Histograms
    • Projector :这个很有意思啊,貌似是吧训练过程中数据点的变化,以动图的形式表现出来;

备注:

tensorflow 和 Numpy 对应关系:

image-20200626175304169


        

不知怎么的,每次听这首歌都会泪目

阅读全文 »

1. 创建文章

  • 在hexo下创建一个新的文章

1
hexo new "文章名称"

2. 创建标签

  • 创建分类页面
1
hexo new page categories
  • 基本设置
1
2
3
title: tags
date:
type: "tags"

3.创建分类

  • 创建分类页面
1
hexo new page categories
  • 基本设置
1
2
3
title: categories
date:
type: "categories"