81.第 1 组百度面试题
2.一个文件，内含一千万行字符串，每个字符串在 1K 以内，要求找出所有相反的串对，如
abc 和 cba。
3.STL 的 set 用什么实现的？为什么不用 hash？
/*
2.一个文件，内含一千万行字符串，每个字符串在 1K 以内，要求找出所有相反的串对，如
abc和 cba。
所以我们有10G数据。这是不可能把它们都到主存储器。
首先第一轮计算每一行的哈希，第二轮计算每一行反向的散列，
只需要存储两个方向的哈希碰撞情况的组数。
最后一轮测试这些存储的
摘别人的：
文件的大小上限是10G，不能在内存操作。思考如何用hash使得如果两个字符串维相反串能得出相同的hash值，
然后用该hash将文件中的字符串散列到不同的文件中，再在各文件中进行匹配。
比如：对字符串上所有字符的ascii求和，因为长度在1K以内，因此范围在int之内。
更进一步，可以在上面那个hash后面再加一个字符串长度，可以得到更好的散列效果。
（例如，a2b1c5,统计按照每个字母出现的次数进行一步的hash）
在各个单独文件中匹配时，如果采用的是第二种hash函数，
那么该文件中的所有字符串都有相同的长度。
如果hash效果好，那么这个文件应该小到可以在内存中进行操作了。
将文件拷贝为两份，分别按照不同规则hash：
第一份按前k位哈希，第二份将字符串的头尾进行颠倒后按前k位哈希（只是对于排序算法颠倒，不必实际颠倒）。
这里的按前k位哈希只需要前k位相同能得到相同结果就好，
比如第i位的ascii乘以2^i。两份拷贝中hash值相同的就很可能是要求的相反串对了，
第二步，将第一份字符串放入hash_set中，然后将第二份的字符串以颠倒的字符串求hash_set，
查看是否在hash_set中，注意字符串中字母完全相同的情况
*/
/* 3.STL的 set用什么实现的？为什么不用hash？ 是用红黑树实现的，红黑树是一种平衡性很好的二分查找树。 要使用hash的话，就需要为不同的存储类型编写哈希函数，这样就照顾不到容器的模板性了， 而是用红黑树只需要为不同类型重载operator<就可以了。 hash_set是以Hash table（哈希表）作为底层数据结构的。 set可以在时间复杂度为O(logN)情况下插入、删除和查找数据。 hash_set操作的时间复杂度则比较复杂，这取决于哈希函数和哈希表的负载情况。 而散列的好处之一是，随着数据的增长，你不需要再散列数据了。 */