网站建设 支持多种语言,给我免费的观看,江苏扬州工程建设信息网站,室内设计学校在哪里一、什么是哈希算法#xff1f;
1.定义 将任意长度的二进制值串映射成固定长度的二进制值串#xff0c;这个映射的规则就是哈希算法#xff0c;而通过原始数据映射之后得到的二进制值串就是哈希值。 2.如何设计一个优秀的哈希算法#xff1f; ①单向哈希#xff1a; 从哈…一、什么是哈希算法
1.定义 将任意长度的二进制值串映射成固定长度的二进制值串这个映射的规则就是哈希算法而通过原始数据映射之后得到的二进制值串就是哈希值。 2.如何设计一个优秀的哈希算法 ①单向哈希 从哈希值不能反向推导出哈希值所以哈希算法也叫单向哈希算法。 ②篡改无效 对输入敏感哪怕原始数据只修改一个Bit最后得到的哈希值也大不相同。 ③散列冲突 散列冲突的概率要很小对于不同的原始数据哈希值相同的概率非常小。 ④执行效率 哈希算法的执行效率要尽量高效针对较长的文本也能快速计算哈希值。
二、哈希算法的常见应用有哪些
7个常见应用安全加密、唯一标识、数据校验、散列函数、负载均衡、数据分片、分布式存储。 1.安全加密 ①常用于加密的哈希算法 MD5MD5 Message-Digest AlgorithmMD5消息摘要算法 SHASecure Hash Algorithm安全散列算法 DESData Encryption Standard数据加密标准 AESAdvanced Encryption Standard高级加密标准 ②对用于加密的哈希算法有两点格外重要第一点是很难根据哈希值反向推导出原始数据第二点是散列冲突的概率要小。 ③在实际开发中要权衡破解难度和计算时间来决定究竟使用哪种加密算法。 2.唯一标识 通过哈希算法计算出数据的唯一标识从而用于高效检索数据。图片搜索 3.数据校验 利用哈希算法对输入数据敏感的特点可以对数据取哈希值从而高效校验数据是否被篡改过。P2P传输分块 下载块后校验 4.散列函数 散列函数中用到的哈希算法更加关注散列后的值能不能平均分布以及散列函数的执行快慢。
5.负载均衡 5.1.需求 如何实现一个会话粘滞session sticky的负载均衡算法也就是说在一次会话中的所有请求都路由到同一个服务器上。 5.2.解决方案 通过哈希算法对客户端IP或会话ID计算哈希值将取得的哈希值与服务器列表的大小进行取模运算最终得到的值就是应该被路由到的服务器编号。这样就可以把同一个IP过来的请求都路由到同一个后端服务器上。 6.数据分片 5.1.如何统计“搜索关键词”出现的次数 ①需求描述 假如我们有1T的日志文件这里面记录了用户的搜索关键词我们想要快速统计出每个关键词被搜索的次数该怎么做呢 ②问题分析 这个问题有两个难点第一个是搜索的日子很大没办法放到一台机器的内存中。第二个是只用一台机器来处理这么巨大的数据处理时间会很长。 ③解决方案 先对数据进行分片然后采用多台比如n台机器进行处理。具体做法从搜索记录的日志文件中依次读取每个关键词并通过哈希函数计算该关键词的哈希值然后跟机器的台数n取模最终得到值就是该关键词应该被分到的机器编号这样相同的关键词一定会被分配到同一台机器上数据分配完成后由多台机器并行进行统计最后合并起来就是最终结果。 实际上这里的处理过程也是 MapReduce 的基本设计思想。 5.2.如何快速判断图片是否存在图库中 ①需求描述 假设现在我们的图库中有1亿张图片如何快速判断图片是否在图库中基本方式是给每个图片去唯一表示或者信息摘要然后构建散列表。 ②问题分析 很显然在单台机器上构建散列表示行不通的因为单台机器的内存有限而1亿张图片构建散列表远远超过了单台机器的内存上限。 ②解决方案 准备n台机器让每台机器只维护一部分图片对应的散列表。我们每次从图库中读取一个图片计算唯一标识然后与机器个数n求余取模得到的值就对应要分配的机器编号然后将这个图片的唯一表示和图片路径发往对应的机器构建散列表。 当我们要判断一个图片是否在图库中时我们通过同样的哈希算法计算这个图片的唯一表示然后与机器个数n求余取模。假设得到的值是k那就去编号为k的机器构建的散列表中查找。 如何估算给1亿张图片构建散列表大约需要多少台机器 散列表中每个数据单元包含两个信息哈希值和图片文件的路径。假设我们通过 MD5 来计算哈希值那长度就是 128 比特也就是 16 字节。文件路径长度的上限是 256 字节我们可以假设平均长度是 128 字节。如果我们用链表法来解决冲突那还需要存储指针指针只占用 8 字节。所以散列表中每个数据单元就占用 152 字节这里只是估算并不准确。 假设一台机器的内存大小为 2GB散列表的装载因子为 0.75那一台机器可以给大约 1000 万2GB*0.75/152张图片构建散列表。所以如果要对 1 亿张图片构建索引需要大约十几台机器。在工程中这种估算还是很重要的能让我们事先对需要投入的资源、资金有个大概的了解能更好地评估解决方案的可行性。 实际上针对这种海量数据的处理问题我们都可以采用多机分布式处理。借助这种分片的思路可以突破单机内存、CPU 等资源的限制。 7.分布式存储 7.1.什么是分布式存储 分布式存储就是将数据存储在多台机器上并提供高效的读取、写入支持。那如何决定将哪个数据放到哪个机器上呢可以利用数据分片的思想即通过哈希算法对数据取哈希值然后对机器个数取模这个最终值就是应该存储的缓存机器编号。 7.2.遇到的问题是什么 如果数据持续增多原来的机器数量已经不能满足需求就需要增加机器这时就麻烦了因为所有的数据都需要重新哈希值进行再次分配。这就相当于缓存中的数据一下子都失效了所有的数据请求都会穿透缓存直接去请求数据库。这样就可能发生雪崩效应压垮数据库。 7.3.解决方案是什么 ①这时需要一种方法使得新加入一个机器后并不需要做大量的数据搬移。那就是在分布式系统中应用非常广泛的一致性哈希算法。 ②一致性哈希算法的基本思想是什么呢为了说清楚这个问题我们假设有k个机器数据的哈希值范围是[0-MAX]我们将整个范围划分成m个小区间m远大于k每个机器复杂m/k个小区间。当有新机器加入的时候我们就将某几个小区间的数据从原来的机器中搬移到新的机器中。这样既不用全部重新哈希、搬移数据也保持了各个机器上数据量的均衡。
三、思考
1.如何防止数据库中的用户信息被脱库你会如何存储用户密码这么重要的数据吗 ①使用MD5进行加密 ②字典攻击如果用户信息被“脱库”黑客虽然拿到的是加密之后的密文但可以通过“猜”的方式来破解密码这是因为有些用户的密码太简单。 ③针对字典攻击我们可以引入一个盐salt跟用户密码组合在一起增加密码的复杂度。 2.现在区块链是一个很火的领域它被很多人神秘化不过其底层的实现原理并不复杂。其中哈希算法就是它的一个非常重要的理论基础。你能讲一讲区块链使用的是哪种哈希算法吗是为了解决什么问题而使用的呢 区块链是一块块区块组成的每个区块分为两部分区块头和区块体。
区块头保存着 自己区块体 和 上一个区块头 的哈希值。
因为这种链式关系和哈希值的唯一性只要区块链上任意一个区块被修改过后面所有区块保存的哈希值就不对了。
区块链使用的是 SHA256 哈希算法计算哈希值非常耗时如果要篡改一个区块就必须重新计算该区块后面所有的区块的哈希值短时间内几乎不可能做到。
笔记整理来源 王争 数据结构与算法之美
