第一章视频3分40s开讲

哈希函数

特征

  1. 输入域是无穷的 输出域是有范围的
  • 常见的 比如MD5函数 和SHA1函数 输出范围见下图 （MD5是长度为16位的十六进制字符串，后者是32位的，一个十六进制位等于4个二进制位）

image.png

  1. 相同的输入有相同的输出
  2. 因为输入域是无穷的 输出域相对有限 会发生哈希碰撞
  3. 具有离散型 和 均匀性 假设输入的字符串有规律 比如”abc1” “abc2” “abc3” 输出的结果也会在输出域上离散开来 均匀性指 在输出域中 任取几段小范围 小范围上的值的个数差不多一样 如下图

image.png

  1. 人为对输出域中的值 %m 那么输出在0~m-1上均匀分布 见下图

image.png

练习题

40亿个数据，每个数的范围是0-42亿，给你1g内存 让你统计出现最多次数的那个数
image.png

  1. 用常规解法内存不够用 最大需要32GB
  2. 用hash函数 帮所有数分配到100个小文件里 相同的数一定在同文件 不同的数也会均匀分布在100个文件 再对100个小文件用常规HashMap解法 每个文件得到一个出现最多的数 最后在统计这100个数 只需要0.32G内存

image.png

哈希表的实现

  1. 首先元素经过哈希然后对初始数组大小取模，放入对应的下标位置 哈希碰撞用链表法解决

    扩容

  • 因为哈希表链表太长影响性能 所以要扩容

    扩容代价

  • 假设往hashmap里加入1000个字符串 链表长度超过2就要扩容 那么总共扩容logn次 每次扩容需要重新移动n个节点 总共扩容代价是O(nlogn)的 均摊一下，单个插入的扩容代价就是 logn

    优化技术

    增加链表长度

  • 增加链表长度 减少扩容次数 logn就会变得特别小 贴近O(1)

    jvm后台离线扩容

    设计RandomPool结构

    56分21秒

    岛问题

    第二章 3分19秒
    image.png

    普通解法

  • 思路：首先遍历这个矩阵里的所有元素，如果碰到为1的元素 就递归的对这个元素进行感染 infect 操作

  • 感染操作就是将附近的一片1都改成2 这样递归的结束条件就得出了
  • infect函数递归的将上下左右都进行infect操作 如果越界或者不为1就返回
  • 时间复杂度为 log n * m n代表遍历次数 m代表每个节点最多被访问四次

    并行解法

    第二章 1小时8分