记一件生活与查找的趣事

一、背景

最近去逛街遇到了一家饰品店，其中有卖百家姓的格子，如图所示：

非常见的姓本来就少，都不确定在不在里面，更不知道在哪个地方，找半天最终还是放弃了。

二、思考

该选取何种结构更好的知道还有没有呢？找快速到对应的值呢？

判断是否存在

2.1.1 Map

可以进货时，

将钥匙串的百家姓的名称和数量采用Map name2CountMap 这种结构存储起来，

比如卖了一个“田”，则其值减一。

判断某个姓是否卖完，则查找对应的值是否为0就好了。

2.1.2 布隆过滤器

如果不是百家姓，而是更大的海量数据判断是否存在，则可使用布隆过滤器。

原理：https://zh.wikipedia.org/wiki/%E5%B8%83%E9%9A%86%E8%BF%87%E6%BB%A4%E5%99%A8

布隆过滤器的原理是，当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们置为1。

检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：

如果这些点有任何一个0，则被检元素一定不在；如果都是1，则被检元素很可能在。这就是布隆过滤器的基本思想。

检索

2.2.1 字典树

字典树的定义：https://zh.wikipedia.org/wiki/Trie

可能不太标准，随时画了一个，比如可以在格子上串两行绳子，第一行是首字母，第二行是拼音，钥匙扣用夹子夹在第二行对应拼音的位置，有点像小时候查的《汉语大词典》。

2.2.2 类似二分查找

将每个百家姓贴上标签，并按照百家姓书中出现的先后从小到大的顺序依次摆放，

假如店主熟悉百家姓，可以使用二分查找方式比较，查找顾客所需的姓氏。

利用排序

记住百家姓的顺序可能难度大一些，可以按照笔画排序，这样算出自己的姓氏多少笔画，从对应对应笔画的数字下查找即可，减少了重复查找的情况。

频率优先排序

还可以按照优先级排序，销量多的姓氏排在左侧，销量低的放在右侧。

这样非常见姓氏的直接从右侧找就可以了。

2.2.3 hash

可以使用Map

map不仅可以判断是否还有，还可以找到其位置。

比如可以借鉴上述的方式贴上标签，按照序号排列号，将数量和序号构成一个实体作为值录入到Map中，

就可以快速告知是否有这个要是扣以及还有几个，

以及编号是多少，

由于按照编号排序好的很容易找到。

比如给出Key="刘"，

可以通过map.get("刘") 得到其值为  (数量5，编号192号)对象

卖出去后，可以自动数量-1

利用数据库

可以存如MySQL数据库，对姓氏建索引（可选择hash索引，因为没必要范围查找），记录如下：

select * from xxx where name="刘"  可以快速查找其对应的库存和编号等。

三、延伸

由此可见多种数据结构可以解决查找的问题，如果范围查找可能就需要借助二叉搜索树，B+树等结构。

另外生活上的很多事情，可以从技术角度考虑是否可以改良，是否有更优化的方案。

拓展阅读：《MySQL为啥用B+树作为数据的存储结构的连环炮》https://cloud.tencent.com/developer/article/1870337

当然可能还有其他方式，欢迎补充。

如果觉得本文对你有帮助，欢迎点赞，欢迎关注我，如果有补充欢迎评论交流，我将努力创作更多更好的文章。