articleList
2025/04/11
posted in
数据结构和算法
简介： 哈希表原理和冲突碰撞解决方案
什么是哈希表 hash table
别名 散列表，本质上是一个数组，提供了键(Key)和值(Value)的映射关系，通过 Key 可以高效查找到匹配的 Value
Key 多数是字符串形式，通过 hash 函数把 key 进行运算，得出数组下标；value 可以是一个 POJO 或者 json 对象
一般包括 key-value 也可以叫 Node 或者 Entry
hash 函数 ：CRC16、CRC32、、murmurHash 和自定义等
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
关键问题：hash 冲突碰撞
hash 碰撞的意思是不同 key 计算得到的 Hash 值相同，两个或多个键值映射到同一个桶（bucket）中
Entry 数据结构里面常见属性
Entry{
String key;
Object value;
Entry next;
int hash;
}
常见的冲突解决办法
开放地址法
链表法
存操作
读操作
注意
JDK1.8 之前的 Hashmap 就是用了这个方法
JDK1.8 改变
链表的长度小于 8，采用链表存储
链表的长度大于 8，链表会转换成红黑树存储 （treeifyBin 函数：把容器里的元素变成树结构）
再哈希法
建立公共溢出区
简介： 海量数据去重-BitMap 位图解决方案
需求（面试题）
一个 32 位 4G 内存的操作系统，在 20 亿个整数，找出某个数 X 是否存在其中
假如是 java 语言，int 占 4 字节，1 字节=8 位（1 byte = 8 bit）
方式一：每个数字是 int 类型存储，就是 20 亿个 int 需要的空间大小就是 7GB 多
方式二：不存储具体数据，而存储是否存在，如果存在则位上存储 1，采用 bit 位存储 20 亿个数就是 20 亿位，空间是 0.2GB 多
什么是 BitMap 位图
需求案例方式二解答
需要申请的数组大小
array[0]:可表示0~31
array[1]:可表示32~63
array[2]可表示64~95
…
总的数组长度为20亿/32 +1
比如元素存储 80，确定所在数组的bit位置
1、数组index索引 80/32 = 2.5，即第3个数组的位置 arr[2]
2、比特位index索引 80%32 = 16，索引下标为16的比特位，把比特位设置为1，即arr[2][16]
注意
缺点
bitmap会有碰撞问题，即可能映射到同个位置，即 hash 碰撞业务应用：日活/月活 UV 统计、签到统计、用户点赞，用户签到，访问计数，在线用户数等
简介： 阿里面试题-编码实现 1 亿个数据找不存在的随机数
题目需求
位图在 java 里面的实现 BitSet 类
是一个实现按需增长的位向量，位 Set 的每一个位置都有一个 boolean 值，默认初始值都是 false
底层实现是使用 long 数组作为内部存储结构的，所以 BitSet 的大小为 long 类型大小(64 位)的整数倍
如果指定了 bitset 的初始化大小，会规整到一个大于或者等于这个数字的 64 的整倍数（内存对齐）
主要 API
void and(BitSet set) 对此目标位 set 和参数位 set 执行逻辑与操作。
void or(BitSet set) 对此目标位集执行逻辑或操作
void clear() 将此 BitSet 中的所有位设置为 false
void clear(int bitIndex)：将指定索引处的位设置为 false
void set(int index) 将指定索引处的位设置为 true
boolean get(int index) 返回指定索引处的位值
int size()：返回此 BitSet 中的位数（按逻辑大小）【表示位值时实际使用空间的位数，值是64的整数倍】
int length() 返回此 BitSet 的"逻辑大小",BitSet 中最高设置位的索引加 1
int cardinality() 返回此 BitSet 中设置为 true 的位数
API 测试
public static void testBitSet(){
BitSet bitSet = new BitSet();
bitSet.set(0);
bitSet.set(66);
System.out.println(bitSet.size()); // 128
System.out.println(bitSet.length()); // 67
System.out.println(bitSet.cardinality()); // 2
System.out.println("=====");
System.out.println(bitSet.get(0)); // true
System.out.println(bitSet.get(1)); // false
}
解答思路
海量数据 里面查找是否存在，排序，交集，并集等，这类题目基本就是使用位图解决
这类题目一般有两个面试形式
public static void testBitMap2(){
//范围
int range = 100;
//个数
int totalNum = 10;
List<Integer> list=new ArrayList<>();
//1.声明一个BitSet
BitSet bitSet = new BitSet(range);
//2.生成1千万个随机数
for (int i = 0; i < totalNum; i++) {
int random = (int) (Math.random() * range);
bitSet.set(random);
list.add(random);
}
System.out.println("产生的随机数："+list);
System.out.println("bitmap是1的个数(存在重复随机送)："+bitSet.cardinality());
System.out.println("bitmap是size："+bitSet.size());
System.out.println("bitmap是length(bitmap里面占据的位数是1的位数+1)："+bitSet.length());
//3.遍历BitSet，将没有出现的数打印出来
for (int i = 0; i < range; i++) {
if (!bitSet.get(i)) {
System.out.print(i+",");
}
}
}
简介： 限定优惠劵业务解决方案-Redis 的 BitMap 应用
需求背景
题目条件
老王
老帆
docker部署redis7
#部署
docker run -itd --name xdclass-redis1 -p 6379:6379 -v /mydata/redis/data:/data redis:7.0.8 --requirepass 123456
#进入容器内部
docker exec -it 容器id /bin/bash
#客户端连接
./redis-cli
#授权
auth 123456
冰冰
存在高并发场景，频繁插入查询数据库不行，那可以结合 Redis，进行判断
但数据结构应该采用 bitmap 数据结构，每个用户 id 占用空间只占用 1 位
领过的用户把 user_id 加入 bitmap 中，下次如果再次领取的查询是否重复领取
Redis 的 bitmap
Redis中提供的BitMap命令：setbit,getbit,bitcount
领劵：setbit coupon-id user-uid 1
例子：setbit coupon-id:876 8888 1
已经领券判断：getbit coupon-id user-uid
例子：getbit coupon-id:876 8888
如果未领取状态是0，如果已领就是1
统计该优惠券有多少个用户领取
bitcount coupon-id:876
返回值为该key值中1的个数
分析
注意
但假如该网站每天的独立访问用户很少， 例如只有 10 万，那这时候使用 Bitmaps 就不太合适， 因为基本上大部分位都是 0
Set 存储使用的空间：64 位 * 100000 = 800KB
BitMap 存储使用的空间：1bit * 1 亿 = 1 亿 bit = 11.9MB
简介： 海量数据处理-进阶版哈希表 BloomFilter
背景需求
海量数据去重需求解决方案
海量数据下去重，如果是非数值类型的话如何判断
什么是布隆过滤器
1970 年由布隆提出的一种空间效率很高的概率型数据结构，它可以用于检索一个元素是否在一个集合中
由只存 0 或 1 的位数组和多个 hash 算法, 进行判断数据 【一定不存在或者可能存在的算法】
如果这些 bit 数组 有任何一个 0，则被判定的元素一定不在; 如果都是 1 则被检元素很可能在
对比 bitmap 位图，布隆过滤器适合更多类型元素，通过 hash 值转换
原理
将元素添加到一个 bitmap 数组中，每个散列函数将元素映射到 bitmap 数组中的一个位置
如果该位置已经被占用，则将该位置置为 1，否则置为 0
当要查询一个元素是否存在时，只需要计算该元素的散列值，并检查 bitmap 数组中对应的位置是否已经被置为 1
如果都是 1，则该元素可能存在，否则肯定不存在。
优点
缺点
案例效果测试
记住结论：不存在的一定不存在，存在的不一定存在
注意点
简介： BloomFilter 应用-垃圾邮件和缓存穿透解决方案
应用场景：解决海量数据下非精确过滤的业务场景
解决缓存穿透解决方案
简介： 爬虫 URL 去重和分库分表注册手机号唯一性解决方案
爬虫 URL 地址去重解决方案
大量的网页爬取，通过解析已经爬取页面中的网页链接，然后再爬取这些链接对应的网页
同一个网页链接有可能被包含在多个页面中，会导致爬虫在爬取的过程中，重复爬取相同的网页
分库分表下手机号重复注册解决方案
简介：爬虫 URL 去重实战-SpringBoot3.0+Guava 布隆过滤器《上》
前置环境准备
项目开发
依赖包引入
<dependencies>
<dependency>
<groupId>org.springframework.boot</groupId>
<artifactId>spring-boot-starter-web</artifactId>
</dependency>
<dependency>
<groupId>org.springframework.boot</groupId>
<artifactId>spring-boot-starter-test</artifactId>
<scope>test</scope>
</dependency>
<dependency>
<groupId>org.apache.commons</groupId>
<artifactId>commons-lang3</artifactId>
<version>3.12.0</version>
</dependency>
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>31.1-jre</version>
</dependency>
</dependencies>
数据准备 (随机生成 500 万 URL)
@Test
public void testGeneUrl() {
try{
File file = new File("/Users/xdclass/Desktop/dat.txt");
if (!file.exists()) {
file.createNewFile(); // 创建新文件,有同名的文件的话直接覆盖
}
FileOutputStream fos = new FileOutputStream(file, true);
OutputStreamWriter osw = new OutputStreamWriter(fos);
BufferedWriter bw = new BufferedWriter(osw);
StringBuilder builder = new StringBuilder();
for (int i = 0; i < 5000000; i++) {
String name = RandomStringUtils.randomAlphabetic(5);
String fileName = "https://www." + name + ".com" + i + "\n";
builder.append(fileName);
}
bw.write(String.valueOf(builder));
bw.newLine();
bw.flush();
bw.close();
osw.close();
fos.close();
} catch (FileNotFoundException e1) {
e1.printStackTrace();
} catch (IOException e2) {
e2.printStackTrace();
}
}
Guava 包布隆过滤器介绍
//参数一： 指定布隆过滤器中存的是什么类型的数据，有 IntegerFunnel，LongFunnel，StringCharsetFunnel
//参数二： 预期需要存储的数据量
//参数三： 误判率，默认是 0.03
BloomFilter.create(Funnels.stringFunnel(Charset.forName("UTF-8")), 5000000, 0.01);
简介：爬虫 URL 去重实战-SpringBoot3.0+Guava 布隆过滤器《下》
@Bean
public Set set() throws IOException {
Set<String> set = new LinkedHashSet<>();
FileInputStream inputStream = new FileInputStream(new File("/Users/xdclass/Desktop/dat.txt"));
InputStreamReader streamReader = new InputStreamReader(inputStream);
BufferedReader reader = new BufferedReader(streamReader);
String line = null;
while (true) {
line = reader.readLine();
if (line != null) {
set.add(line);
} else {
break;
}
}
inputStream.close();
return set;
}
@Bean
public BloomFilter bloomFilter() throws IOException {
BloomFilter bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.forName("UTF-8")), 5000000, 0.01);
FileInputStream inputStream = new FileInputStream(new File("/Users/xdclass/Desktop/dat.txt"));
InputStreamReader streamReader = new InputStreamReader(inputStream);
BufferedReader reader = new BufferedReader(streamReader);
String line = null;
while (true) {
line = reader.readLine();
if (line != null) {
bloomFilter.put(line);
} else {
break;
}
}
inputStream.close();
return bloomFilter;
}
@RestController
@RequestMapping("/api")
public class FilterController {
@Autowired
private BloomFilter<String> bloomFilter;
@Autowired
private Set set;
@GetMapping("/bloom")
public String list() throws IOException {
//判断是否包含这个内容
if (bloomFilter.mightContain("https://www.dhVrX.com5")) {
return "命中了";
} else {
return "没命中";
}
}
@GetMapping("/set")
public String set() {
if (set.contains("httssps://www.shncb.com999663")) {
return "命中了";
} else {
return "没命中";
}
}
}
案例测试 （调整 JVM 参数分配内存：-Xms100m -Xmx100m）
简介：哈希表-位图和布隆过滤器特点和业务选择说明
案例说明
哈希表、位图和布隆过滤器对比
共同点
差异
变种