标签： 算法 (2)

• 布隆去重的Java实现

  1  评论    81  浏览

  直观的说，bloom算法类似一个hash set，用来判断某个元素（key）是否在某个集合中。

  和一般的hash set不同的是，这个算法无需存储key的值，对于每个key，只需要k个比特位，每个存储一个标志，用来判断key是否在集合中。

  算法

  1. 首先需要k个hash函数，每个函数可以把key散列成为1个整数
  2. 初始化时，需要一个长度为n比特的数组，每个比特位初始化为0
  3. 某个key加入集合时，用k个hash函数计算出k个散列值，并把数组中对应的比特位置为1
  4. 判断某个key是否在集合时，用k个hash函数计算出k个散列值，并查询数组中对应的比特位，如果所有的比特位都是1，认为在集合中。

  优点

  不需要存储key，节省空间

  缺点

  1. 算法判断key在集合中时，有一定的概率key其实不在集合中
  2. 无法删除
  19-01-18 11:18 lethe
  标签： 技术, Java, 算法, 源码

• 笛卡儿积计算的两种非递归实现

  0  评论    231  浏览

  笛卡尔积：笛卡尔乘积是指在数学中，两个集合X和Y的笛卡尓积（Cartesian product），又称直积，表示为X × Y，第一个对象是X的成员而第二个对象是Y的所有可能有序对的其中一个成员 [1] 。
  18-06-13 23:59 lethe
  标签： Java, 技术, 算法