面试笔记--大数据算法

大数据的解法无非那么几种，常见的就是hash和bitmap

10亿个QQ号，让我找出一个QQ号是不是在其中，时间复杂度要求O(1)

用bitmap来做这个问题。首先对数据进行预处理。定义10亿bit位个int.在32位计算机下，一个int是32位，10亿位的话，就需要10亿除以32个int整数。大概有很多个。第一个int标记0-31这个数字范围的QQ号存不存在，比如说0000001这个QQ号，我就把第一个int的第1位置1。第二个int能够标记32-63这个范围的QQ存不存在，以此类推。把这10亿个QQ号预处理一遍。然后计算你给我的这个QQ号，它是在哪个int里面，然后找到相应的数据位，看是1还是0，就能在O(1)的时间里找到