有段时间没写这种文章了。根据姜文电影的名场面，我决定将博客的这个栏目命名为——「正经人谁写日记呀」，哈哈。
2019年像之前的每一年一样，过得很快。对它的印象只剩加班加班、辞职家里蹲、旅行，然后，就是现在：手机在放歌，我坐在床上，敲打老旧的 MacBook，现在是 12.31 02:02。
又是不太长进的一年。原本没有值得写的东西。但今年有两个瞬间让我想写点什么：
一是 ruohan 在微信上再次联络我之后，我觉得人和人也许是可以相互原谅的，心里稍微好受一点，当时感激地有写东西的冲动。
二是前几天，见了一些老朋友。看到大家都过得很好，也许说不上很好但也是「稳步前行」。似乎让我对自己也稍稍有了一点信心。
毕业后我在两个公司工作过，其中一家是台湾的电子制造公司LiteOn，第二家是华为。
这是一篇LiteOn领导拜托我写给他们介绍华为工程师生活的文章。我把它贴出来，作为对前东家讨论系列的第一篇，之后可能还会有别的分析文章。
表妹在大一的C语言课上写了个bug程序，发到群里让大家帮忙debug。我一眼看出其中存在一处“语法”错误：
if (0 < a < 10) {
…
}
一个很有意思的事是，我把它当成了“语法错误”，认为这样写根本编译不过。
但事实是，从之后的讨论中看到，这个程序没有编译失败。只是逻辑上有错而已——这个if后面的表达式永远为true。
我用gcc编译了一遍试试，报了这个warning：
warning: comparisons like ‘X<=Y<=Z’ do not have their mathematical meaning [-Wparentheses]
if (0 < a < 10) {
意味着我们一开始的判断是对的，0 < a < 10 确实不是正确的C语言写法，应该写作(0 < a) && (a < 10)。但编译器还是允许它通过了。程序运行时真正发生的是什么呢？：
（0 < a） < 10
相当于先执行了括号内的运算，返回 true 或 false。在C语言中 true == 1， false == 0。这两个值再去与10做比较。——当然是恒 <10 的，所以 (0 < a < 10) 这个表达式恒为 true，相关 if 语句永远不会走进 else 分支。
这方面的语法差异还挺有趣的，这篇文章里说，如果你没学过C，你可能会以为a < b < c就是a < b < c，如果你学过C，你会以为这里无法编译通过。
a < b < c 的意思就是 a < b < ccomparisons like ‘X<=Y<=Z’ do not have their mathematical meaning< 符号没有关联性（non-associative (meaning operations cannot be chained, often because the output type is incompatible with the input types)）。在编译时开启所有编译告警，并尽可能地将它们清零，是一个好的习惯。
当然，也不是一概而论的。取决于你的项目性质，某些告警（未使用的函数、未使用的变量）还是可以选择关闭的。最好是开启所有告警，然后明确声明关闭特定的某几个告警；而不是直接关闭所有告警。
最近在思考关于哈希表二次探测再散列后如何查找的问题。暂时没找到解释。先转一篇有趣的科普文，以供后续研究。
原文来自： http://www.ruanyifeng.com/blog/2018/09/hash-collision-and-birthday-attack.html
所谓哈希（hash），就是将不同的输入映射成独一无二的、固定长度的值（又称”哈希值”）。它是最常见的软件运算之一。
如果不同的输入得到了同一个哈希值，就发生了”哈希碰撞”（collision）。
举例来说，很多网络服务会使用哈希函数，产生一个 token，标识用户的身份和权限。
AFGG2piXh0ht6dmXUxqv4nA1PU120r0yMAQhuc13i8
上面这个字符串就是一个哈希值。如果两个不同的用户，得到了同样的 token，就发生了哈希碰撞。服务器将把这两个用户视为同一个人，这意味着，用户 B 可以读取和更改用户 A 的信息，这无疑带来了很大的安全隐患。
黑客攻击的一种方法，就是设法制造”哈希碰撞”，然后入侵系统，窃取信息。
防止哈希碰撞的最有效方法，就是扩大哈希值的取值空间。
16个二进制位的哈希值，产生碰撞的可能性是 65536 分之一。也就是说，如果有65537个用户，就一定会产生碰撞。哈希值的长度扩大到32个二进制位，碰撞的可能性就会下降到 4,294,967,296 分之一。
更长的哈希值意味着更大的存储空间、更多的计算，将影响性能和成本。开发者必须做出抉择，在安全与成本之间找到平衡。
下面就介绍，如何在满足安全要求的前提下，找出哈希值的最短长度。
哈希碰撞的概率取决于两个因素（假设哈希函数是可靠的，每个值的生成概率都相同）。
这个问题在数学上早有原型，叫做”生日问题“（birthday problem）：一个班级需要有多少人，才能保证每个同学的生日都不一样？
答案很出人意料。如果至少两个同学生日相同的概率不超过5%，那么这个班只能有7个人。事实上，一个23人的班级有50%的概率，至少两个同学生日相同；50人班级有97%的概率，70人的班级则是99.9%的概率（计算方法见后文）。
这意味着，如果哈希值的取值空间是365，只要计算23个哈希值，就有50%的可能产生碰撞。也就是说，哈希碰撞的可能性，远比想象的高。实际上，有一个近似的公式。
上面公式可以算出，50% 的哈希碰撞概率所需要的计算次数，N 表示哈希的取值空间。生日问题的 N 就是365，算出来是 23.9。这个公式告诉我们，哈希碰撞所需耗费的计算次数，跟取值空间的平方根是一个数量级。
这种利用哈希空间不足够大，而制造碰撞的攻击方法，就被称为生日攻击（birthday attack）。
这一节给出生日攻击的数学推导。
至少两个人生日相同的概率，可以先算出所有人生日互不相同的概率，再用 1 减去这个概率。
我们把这个问题设想成，每个人排队依次进入一个房间。第一个进入房间的人，与房间里已有的人（0人），生日都不相同的概率是365/365；第二个进入房间的人，生日独一无二的概率是364/365；第三个人是363/365，以此类推。
因此，所有人的生日都不相同的概率，就是下面的公式。
上面公式的 n 表示进入房间的人数。可以看出，进入房间的人越多，生日互不相同的概率就越小。
这个公式可以推导成下面的形式。
那么，至少有两个人生日相同的概率，就是 1 减去上面的公式。
上面的公式，可以进一步推导成一般性的、便于计算的形式。
根据泰勒公式，指数函数 ex 可以用多项式展开。
如果 x 是一个极小的值，那么上面的公式近似等于下面的形式。
现在把生日问题的1/365代入。
因此，生日问题的概率公式，变成下面这样。
假设 d 为取值空间（生日问题里是 365），就得到了一般化公式。
上面就是哈希碰撞概率的公式。
上面的公式写成函数。
const calculate = (d, n) => {
const exponent = (-n * (n - 1)) / (2 * d)
return 1 - Math.E ** exponent;
}
calculate(365, 23) // 0.5000017521827107
calculate(365, 50) // 0.9651312540863107
calculate(365, 70) // 0.9986618113807388
一般来说，哈希值由大小写字母和阿拉伯数字构成，一共62个字符（10 + 26 + 26）。如果哈希值只有三个字符的长度（比如abc），取值空间就是 62 ^ 3 = 238,328，那么10000次计算导致的哈希碰撞概率是100%。
calculate(62 ** 3, 10000) // 1
哈希值的长度增加到5个字符（比如abcde），碰撞的概率就下降到5.3%。
calculate(62 ** 5, 10000) // 0.05310946204730993
现在有一家公司，它的 API 每秒会收到100万个请求，每个请求都会生成一个哈希值，假定这个 API 会使用10年。那么，大约一共会计算300万亿次哈希。能够接受的哈希碰撞概率是1000亿分之一（即每天发生一次哈希碰撞），请问哈希字符串最少需要多少个字符？
根据上面的公式倒推，就会知道哈希值的最短长度是22个字符（比如BwQ1W6soXkA1PU120r0yMA），计算过程略。
22个字符的哈希值，就能保证300万亿次计算里面，只有1000亿分之一的概率发生碰撞。常用的 SHA256 哈希函数产生的是64个字符的哈希值，每个字符的取值范围是0~9和a~f，发生碰撞的概率还要低得多。
Powered by WordPress & Theme by Anders Norén