【读书笔记】数据结构与算法之美 第4章 哈希表、位图和哈希算法

《数据结构与算法之美》，王争 著

标签：数据结构、算法

第4章 哈希表、位图和哈希算法

一、哈希

作者在哈希（又称散列表）这个小节，介绍下面的内容：

• 哈希思想：什么是哈希

• 哈希函数：什么是哈希函数和哈希冲突

• 哈希冲突：解决哈希冲突的两种常用方法：开放寻址法和链表法

• 哈希表：如何打造一个工业级的哈希表： 设计哈希函数、解决装载因子过大的问题、避免低效的扩容、选择合适的冲突解决策略、工业级的哈希表（Java HashMap）举例分析

• 哈希表：如何利用哈希表优化LRU缓存淘汰算法

 二、位图

通过如何实现网页爬虫中的网址链接去重功能的三种解决方案

哈希表、位图和布鲁姆过滤器的简述比较，给读者引出了位图和布鲁姆过滤器两个强大的东西（有实际工业背景的东西）。这是一般数据结构教材不会出现的。

 三、哈希算法

本节从实战的角度，如何应用哈希算法来解决问题（安全加密、唯一标识、数据校验、哈希函数、负载均衡、数据分片、分布式存储）。虽然文字篇幅不多，但是感谢作者的收集和汇总。

这一节，最大的特色是给读者列出了很多哈希（哈希表和哈希算法两个分别是数据结构和算法中很有代表性的东西，常规教材讲的不多，考试一般考的也不难，课程实现一般没有）可以解决的实际问题，是对常规教材和课程中哈希内容的补充，同时对读者了解哈希的实际应用以及面试也是很有帮助的。

简单说，很多开发语言和平台，都有哈希表可以使用；哈希表和哈希函数的应用范围和可解决的问题是非常多的。