Jason Zhao's List: Algorithm

• 这样当hashtable中出现重复key的时候说明此链表上有环. 这个方法的时间复杂度为O(n), 空间同样为O(n).
• 当有环的时候反转next指针会最终走到链表头部; 当没有环的时候反转next指针会破坏链表结构(使链表反向), 所以需要最后把链表再反向一次. 这种方法的空间复杂度是O(1), 实事上我们使用了3个额外指针;而时间复杂度是O(n), 我们最多2次遍历整个链表(当链表中没有环的时候)
• 多线程情况下不安全
• 快指针和慢指针

2 more annotations...

• 如果允许有一定的错误率，可以使用Bloom filter
• 采用2-Bitmap

  • 零错误率的情况用bitmap
• 用位图/Bitmap的方法，申请512M的内存，一个bit位代表一个unsigned int值。

  • 这种题不允许有错误率，故不能用Bloom Filter.

1 more annotation...

• 并能判断一个元素是否属于这个集合
• 在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false  positive）
• 为了表达S={x₁, x₂,…,x_n}这样一个n个元素的集合，Bloom Filter使用k个相互独立的哈希函数（Hash  Function），它们分别将集合中的每个元素映射到{1,…,m}的范围中。对任意一个元素x，第i个哈希函数映射的位置h_i(x)就会被置为1（1≤i≤k）
• 数据字典，进行数据的判重，或者集合求交集
• 一个简单的改进就是 counting Bloom filter，用一个counter数组代替位数组，就可以支持删除了
• 当hash函数个数k=(ln2)*(m/n)时错误率最小
• Counting bloom filter（CBF）将位数组中的每一位扩展为一个counter，从而支持了元素的删除操作。Spectral Bloom Filter（SBF）将其与集合元素的出现次数关联。SBF采用counter中的最小值来近似表示元素的出现频率。

5 more annotations...

• 在CBF中加入一个元素时，k个哈希位置的counter都要加1。也就是说，如果不考虑碰撞（collision），出现次数为n的元素对应的k个counter的值都为n。即使考虑到碰撞的因素，只要k个位置不全出现碰撞，k个counter中的最小值仍是n。令元素x对应的k个counter的最小值为m_x，x的出现频率为f_x，从上面的分析我们不难看出，f_x ≠ m_x的概率和标准bloom filter的false positive概率相同，因为二者出现的充要条件都是k个哈希位置同时出现碰撞。
• CBF的counter在只支持membership query的时候，4位就够了，如果想要支持元素的出现频率查询，4位就远远不够。由于元素有可能成百上千次重复出现，而且完全没法预测，所以SBF的counter必须能够动态伸缩

• 如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面
• 算法的实现

  • 代码有问题，while循环要判断 j >= 0