哈希表的一种简单表示

谈谈bitmap的使用

前言

在解某些算法中, 时间与空间往往二者不可得兼

这个时候, 我们需要根据实际需求来进行取舍, 到底是选择空间, 还是时间

什么是bitmap

所谓的Bit-map就是用一个bit位来标记某个元素对应的Value， 而Key即是该元素 —摘自：https://wizardforcel.gitbooks.io/the-art-of-programming-by-july/content/06.07.html

我们举个栗子：

假设现在有一个数组, 数组中的元素范围为1-127,　我们想要用O(1)的时间复杂度来查找某个元素是否存在于这个数组内.

第一个想到的解法就是使用哈希表(Java 内置的 HashMap) , 但相较于这个问题而言,　哈希表不够轻量.

于是bitmap就闪亮登场,　它可以理解为一个更为简单轻量的哈希表：

int[] map = new int[128]; // 这就是一个bitmap

那好,　如何用这个map 快速判断元素是否存在?

1. 映射

首先必须把原始数组中的数据表示到我们的bitmap上：

for (int i = 0; i < arr.length; i++){
  map[arr[i]] = 1;
}

上面的循环是将原始数组的元素作为map 的 index,　通过标记的方式来表示这个元素存在.

比如map[1] = 1 就表示1这个元素存在

2.查找

映射完毕,　接下来就可以实现在O(1)的时间复杂度内查找元素是否存在了

boolean contains(int key){
  return map[key] == 1;
}

搞定!

实例

leetcode 242 ：有效字母的异位词

https://leetcode-cn.com/problems/valid-anagram/

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

输入: s = “anagram”, t = “nagaram” 输出: true

这道题使用bitmap再合适不过了, 只需要建立两个bitmap 分别对两个字符串映射,　后一一比较各位是否相同即可

class Solution {
    public boolean isAnagram(String s, String t) {
        int[] map1 = new int[128];
        int[] map2 = new int[128];
        for(int i=0;i<s.length();i++){
            char c = s.charAt(i);
            map1[c] = map1[c] + 1;
        }
        for(int i=0;i<t.length();i++){
            char c = t.charAt(i);
            map2[c] = map2[c] + 1;
        }
        for(int i=0;i<map1.length;i++){
            if (map1[i] != map2[i]) {
                return false;
            }
        }
        return true;
    }
}

当然这段代码还有优化空间, 比如可以只使用一个bitmap 就能解决

Redis 中 bitmap 的使用

范围扩的更广一点, Redis 的　String 类型也支持bitmap操作:

比如可以用一个长度为365的bitmap 代表某个用户一年内登录的天数　那么就有以下操作:

setbit cxk 1 1 # 第一天登录
setbit cxk 364 1 # 第364天登录
bitcount cxk 0 10 # 0 - 10天这个时间窗口登录了几天

更复杂一点,　我们来统计某段时间内有多少用户登录过, 每一天一个bitmap 使用用户的ID　作为索引　就有以下操作

setbit 200618 1 1 # 18号1号用户登录
setbit 200619 1 1 # 19号1号用户登录
setbit 200619 7 1 # 19号7号用户登录
bitop or ret 200618 200619 # 使用或运算合并bit
bitcount ret 0 0 # 统计有多少位1 有多少位１就有多少用户登录过