哈希算法范文

哈希算法范文（精选8篇）

哈希算法 第1篇

随着网络带宽的不断增大, 网络速度的不断提高, 传统的基于单主机的入侵检测系统已经很难满足大规模网络高效检测的需求。分布式入侵检测系统是解决高速网络环境下入侵检测效率低下问题的解决方案之一。现今, 提升分布式入侵检测系统的性能面对许多难题。首先, 数据的完整性对入侵检测系统检测准确率的提升至关重要, 因此如何保持数据的完整性是对分布式系统中数据分割算法提出的重大挑战;其次, 分布式系统中可能会产生添加或删除结点的情况, 此时若采用传统求模运算的哈希函数, 则必须重新分配数据, 然而在入侵检测中有时需要与历史信息结合来准确判断出攻击行为, 此时将产生大量的数据迁移, 降低整个系统性能;最后, 均衡的保持每个结点的负载, 使各个结点发挥出最大性能, 也是提升分布式入侵检测系统的关键。因此, 实现分布式入侵检测的关键在于数据分割算法。

一个良好的面向分布式入侵检测的数据分割算法应当满足以下三个特征: (1) 有效性, 即每个数据分片应能准确检测出攻击行为; (2) 均衡性, 即每一个分片应使各分布式结点负载均衡; (3) 简单性, 即分割算法简单、高效。文献[1]提出动态最小负载优先算法, 将数据优先分配给负载最轻的结点。文献[2]中加入了数据预过滤和缓冲聚类, 将检测结点的一部分功能转移到分割模块中, 降低了后续模块的处理压力。文献[3]提出的随意分割集中学习的方法, 此种算法满足了分割算法的简单性和负载均衡性, 但后续的检测较为复杂, 不利于实时网络入侵检测的实施。文献[4]综合考虑了影响各结点负载均衡性的因素, 优先将数据分配给负载最轻的结点, 实现了负载均衡性, 然而并没有考虑到数据包之间的联系, 破坏了数据的完整性。文献[5]提出基于流粒度的负载均衡算法, 以会话流为单位分发数据包, 保持数据的完整性。

本文基于一致性哈希算法, 给出一种改进的算法, 并用于分布式入侵检测的数据分割, 该算法针对采集的数据包, 通过维护TCP连接记录并重组TCP数据链, 保持数据流的完整性;再通过改进的一致性哈希算法, 减小结点间数据的迁移量, 同时通过负载均衡策略维持结点间的负载均衡。

2 改进的一致性哈希数据分割方法

在分布式入侵检测中, 数据分割的优劣一直是制约分布式入侵检测系统性能的瓶颈。首先, 若以单一数据包为最小检测单元, 不关心数据包的状态信息, 将相互关联的数据包分配到结点, 会导致许多攻击行为无法检测出;其次, 为了准确检测出攻击行为, 有时还需获取历史告警记录。若采用传统哈希函数, 当分布式系统中有结点的添加和删除时, 将导致整个哈希函数重新分布, 为了保证历史记录的准确性, 需要迁移大量的历史告警信息, 为系统增加负担;最后, 若分割算法不能实现负载均衡, 则无法充分发挥各结点的计算性能, 导致系统整体陷入瓶颈。

针对以上问题, 本文首先采用TCP流重组技术, 以会话流为最小单元保持数据的完整性。TCP协议在网络中进行传输的时候, 由于经过不同的路由, 在到达的时间与顺序上会产生混乱, 因此要提取出数据流中的TCP包进行重组才能还原成一个完整的数据链。为保证将海量的网络数据分割成一个个完整的数据子集, 在数据重组时, 计算数据包的哈希值。一条TCP连接可以由四元组<源IP地址, 源端口, 目的IP地址, 目的端口>唯一确定, 因此, 可以通过哈希函数计算四元组的哈希值, 作为此连接的唯一标识, 结合报文中的连接序号就可以实现正确的TCP流重组。针对重组形成的一个个TCP流链, 进一步采用改进的一致性哈希算法, 将不同的TCP流链分配到不同的结点, 实现数据的分割。

2.1 改进的一致性哈希算法

一致性哈希算法是实际结点对应的虚拟结点映射到0~232的环上, 数据求取哈希值后同样映射到该环上, 并按顺时针方向查找与之最接近的虚拟结点, 通过虚拟结点与实际结点之间的映射关系将数据分布到真实结点。当有新结点加入或旧结点退出时, 仅影响顺时针方向的下一个结点的数据, 减少数据的迁移量。

然而传统一致性哈希算法主要针对同构主机, 当两个结点的性能相差过大时, 需要引入大量的虚拟结点, 从而导致虚拟结点需要的存储空间增加和查找速度的降低。假设结点i的计算能力为ai, 由文献[6]得知, 每台主机引入的虚拟设备为klog|N|, 其中k为常数, N为设备总数。若结点i的计算能力为ai, 计算能力最低结点的计算能力为amin, 则传统一致性哈希函数所需要分配的虚拟结点个数为:

当ai/amin的值很大时, 将引入大量的虚拟结点, 降低整个一致性哈希函数性能。

本文改进算法中, 将计算能力相差不大的结点分为一组, 组间按照各组结点计算能力的大小比例分割整个哈希值的值域, 数据先分配到不同的组中, 在组内采用一致性哈希算法, 再将数据分配到不同的结点上。由于组内结点计算能力相差不大, 因此可以采用均匀分配的方式。采用此方法可以解决异构主机引入虚拟结点过多的问题。假设结点共分为p组, 组i中有ni个结点, 由于结点计算能力相差不大, 则每组中引入的虚拟结点总数为niklog|N|, 整个分割系统引入总结点数为:

当结点计算能力相差很大时, 式 (1) 的值远远大于式 (2) 的值。

2.2 负载均衡策略

在传统一致性哈希算法中, 数据的分配是由概率决定的, 因此在容易产生负载不均衡。针对该问题, 本文基于上述的改进一致性哈希算法, 进一步进行负载均衡调整。系统周期性进行结点负载情况检查, 并根据不同组结点数据处理能力不同, 设定不同的负载均衡调整门限, 当负载不均衡程度超过门限时, 进行结点的负载均衡调整。

假设组i的权重为ci, 表示结点的计算能力, 计算能力越强的组ci的值越大, 计算能力最低的一组权重为cmin, 其中p为结点组的个数。组i负载均衡调整门限为Thresholdi, 计算能力最低一组的负载均衡调整门限为Thresholdmin则有:

设组内负载最轻结点负载为Lmin, 负载最重结点负载为Lmax, 负载居中结点为Lmid, 若类i中Lmax-Lmid>Thresholdi, 则进行负载过重调整, 减少Lmax对应结点的虚拟结点, 同时将分配到该结点的数据产生的T时间内的告警信息迁移到顺时针方向的下一个结点, 并清空该虚拟结点的告警信息。同理, 若组i中Lmid-Lmin>Thresholdi, 进行负载过轻调整, 增加Lmin对应的虚拟结点个数, 同时将下一结点中的T时间内部分告警信息迁移到新的结点中, 并清空旧节中迁移部分的告警信息。

负载均衡调整将有效提升一致性哈希算法负载均衡性。使调整后的结点负载接近负载中间结点。同时, 检测攻击行为并不需要太长时间的历史记录, 因此结点告警信息的迁移量很小, 并不会给系统增添过重的负担。

3 实验仿真

3.1 实验环境

本文采用C语言实现了网络数据抓包、TCP流重组, 以及分组一致性哈希算法和负载均衡调整算法, 并对该算法进行了测试。仿真测试主要测试算法改进后的负载均衡情况。仿真测试网络环境为实验室局域网通过100M交换机连接到校园网, 并连接互联网。模拟设置了15个结点, 分为3组, 每组5个结点;各组中结点计算能力分别分布在1000, 3000, 6000附近区间;设置计算能力最低的一组的虚拟结点数为20。

3.2 实验结果与分析

3.2.1 组间负载均衡实验

由于各组分配的数据量与各组计算能力成正比, 若各组负载均衡则该组中处理数据的总量比该组计算能力的值应大致相同。这个值定义为组间相对数据量。各组组间相对数据量差值越小, 说明组间负载均衡性越好。均方误差能较好的反应数据之间的离散程度, 均方误差越小说明数据之间的离散程度越低。因此本文采用组间相对数据量的均方误差作为评价组间负载均衡的评价指标, 并将本文改进算法与传统一致性哈希函数进行对比测试。实验结果如图1所示。

由图1可以看出, 本文改进算法中各组组间数据量均方误差远小于传统一致性哈希算法, 其原因在于本文算法将数据按照相对权重值的比例均匀分布到各组结点, 组间负载性能良好, 充分发挥结点的计算能力。

3.2.2 组内负载均衡实验

本实验将本文算法与传统哈希分割算法、传统一致性哈希算法进行对比测试。对比的两种算法将计算能力相同的结点视为一组, 同时取第二组结点在不同的数据量下进行负载均衡性测试。实验引入文献[7]中提出的负载均衡度作为评价指标。负载均衡度越小, 说明负载均衡性能越好。实验结果如图2所示。

由上图可以观察到, 由于传统算法没有加入动态调整策略, 当局部流量增大时, 将导致严重的负载不均衡现象, 此种情况需要经过较长时间的调整, 才能略有改善。本文算法进行负载均衡调整后, 负载均衡性能良好, 且波动范围很小, 基本实现组内各结点负载均衡。

4 结束语

近年来网络安全形势日趋严峻, 分布式入侵检测技术成为维护网络安全的有效手段, 分割算法又是影响分布式入侵检测系统性能的关键因素。本文给出改进的一致性哈希算法, 并应用于分布式入侵检测中进行数据分割。算法基于对采集数据的TCP流重组, 并采用分组方法进行结点分组并实现组间和组内的数据分配, 减少虚拟结点数量, 并通过对结点的负载均衡检测和调整, 改善了系统的负载均衡性。

参考文献

[1]李信满, 赵大哲, 赵宏, 等.基于应用的高速网络入侵检测系统研究[J].通信学报, 2002, 23 (9) :1-7.

[2]Xinidis K, Charitakis I, Antonatos S, et al.An active splitter architecture for intrusion detection and prevention[J].Dependable and Secure Computing, IEEE Transactions on, 2006, 3 (1) :31-44.

[3]刘衍珩, 田大新, 余雪岗, 等.基于分布式学习的大规模网络入侵检测算法[J].软件学报, 2008, 19 (4) :993-1003.

[4]Jiang W, Song H, Dai Y.Real-time intrusion detection for high-speed networks[J].Computers&security, 2005, 24 (4) :287-294.

[5]高明.高速网络入侵检测负载均衡机制研究[D].武汉:华中科技大学, 2009.

[6]Karger D, Lehman E, Leighton T, et al.Consistent hashing and random trees:Distributed caching protocols for relieving hot spots on the World Wide Web[C]//Proceedings of the twenty-ninth annual ACM symposium on Theory of computing.ACM, 1997:654-663.

巧用哈希数值传递文件 第2篇

现在网络中比较常见的哈希数值计算方式有两种，一种是MD5方式，另一种是SHA1方式。目前只有通过MD5这种方式计算出的结果，才可以成功转换为磁性链接信息。所以我们首先下载运行“MD5-Hash哈希值计算工具”这款软件，接着点击窗口下方“校验类型”中的“MD5”选项。然后点击“计算文件哈希值”按钮，在弹出的对话框中选择需要传递的文件，很快就可以在软件的“哈希值”里面看到计算出来的哈希数值了（图1）。

默认情况下计算出的哈希数值是32位的，但是转换为磁性链接的哈希数值必须是40位的。这里就涉及到一个数值转换问题。首先我们将数值转换为16位的哈希数值，这个转换方法倒是非常简单。只需要将32位的哈希数值前后八位掐头去尾，剩下的就是16位的哈希数值了。比如32位的哈希数值为B7FCE0CE2229E2A289D3E6816D26D507，那么它的16位哈希数值就是2229E2A289D3E681。而40位哈希数值的转换方式为，16位的哈希数值加上32位哈希数值的后8位，再加上32位哈希数值的后16位即可。通过这样的计算就可以得到40位哈希数值，本例的结果为：2229E2A289D3E6816D26D50789D3E6816D26D507。

转换为磁性链接内容

既然现在已经有了哈希数值的内容，接下来我们就可以将其转换成磁性链接了。首先下载运行HashToMagnet这款工具，将刚刚转换出来的哈希数值信息粘贴到窗口中（图2）。如果转换的哈希数值比较多，那么一行粘贴一个哈希数值就可以了。接着点击工具栏中的“哈希→磁力链接”按钮，然后在弹出的对话框中点击“转换”按钮（图3）。

当工具提示转换完成后关闭转换对话框，在软件的窗口里面就可以看到转换成功后的磁性链接信息。将得到的磁性链接信息通过微博、微信等方式发布出去，这样其他网友就可以获取到我们发布的相关文件了。

哈希算法 第3篇

按照坚强智能电网建设的总体要求, 保证智能电网建设规范有序推进, 实现电力用户用电信息采集系统建设“全覆盖、全采集、全费控”的总体目标, 国家电网公司对国内外采集系统建设应用现状进行调研和分析, 并充分结合通信技术、微处理器技术、制造工艺等技术的发展, 适时启动了电力用户用电信息采集系统的建设。

按照《电力用户用电信息采集系统管理规范第一部分:主设规范》的要求, 用电信息采集系统具有高性能、高可靠性和大容量的特点。

1) 高性能。要求在线终端数不小于25万台;工作站并发数大于500台;单台通信前置机连接数>30 000台, 并发数>600台。

2) 高可靠性。系统要求可用率≥99.5%, 各类设备的平均无故障时间 (MTBF) ≥3 104 h, 系统故障恢复时间2 h。

3) 大容量。系统要求接入的用户数>1 000万户;系统数据在线存储≥3年;接入终端数>25万台。

根据用电信息采集系统的特点, 系统应为分层分布式的架构, 如何对负载进行合理的分配是系统实现的关键, 而负载均衡的策略和算法是关键中的关键。本文采用一致哈希算法实现系统的可靠性和负载均衡, 并对哈希算法进行研究探讨。

1 哈希算法与实现

哈希, 是Hash的音译, 也叫做“散列”, 就是把任意长度的输入, 通过哈希算法, 变换成固定长度的输出, 该输出就是哈希值。哈希值的空间通常远小于输入的空间, 不同的输入可能会散列成相同的输出, 而不可能从散列值来唯一地确定输入值。数学表述为:h=H (M) , 其中H () 为单向哈希函数;M为任意长度明文;h为固定长度哈希值。

哈希算法具有单向性、抗冲突性、映射分布均匀性和差分分布均匀性等特征, 因此, 在文件校验、数据签名、鉴权协议和查找方面有重要用途。在查找方面, 链表查找的时间效率为O (N) , 二分法为O (logN) , B+Tree为O (logN) , Hash链表查找的时间效率为O (1) , 相对而言, Hash链表有更高的查找效率。

哈希算法的实现一般可以简单地划分为如下几类。

1) 加法:把输入元素一个一个地加起来构成最后的结果。

2) 位运算:通过利用各种位运算 (常见的是移位和异或) 来充分地混合输入元素。

3) 乘法或除法:利用乘法 (除法) 的不相关性, 获取相应结果。典型的应用有FNV算法, 在JDK5.0中字符串的hashCode () , 采用了h (n+1) =h (n) 31+str[n], 实际上, 在源代码中, hashCode () 的声明为:public native int hashCode () , 由于是native方法, 跟OS的处理方式相关, 源代码里仅有一个声明。

4) 查表:就是通过某些输入的特征值查表获取相应的值并运行计算, 比较典型的应用有CRC计算, 实际上CRC系列算法本身并不是查表, 但是查表是它的一种最快的实现方式, CRC并不是针对哈希而设计的, 但可以作为一种哈希算法应用。在JDK5.0以上版本中, 直接使用java.util.zip.CRC32类, 方法如下:

getValue () 返回CRC-32值;

reset () 复位CRC-32到初始值;

update (byte[]) 用指定的字节数组更新CRC-32;

update (byte[], int, int) 用指定的字节数组更新CRC-32;

update (int) 用指定的字节更新CRC-32。

5) 混合:利用以上各种方式, 常见有MD5、Tiger等。

哈希算法实现方式有很多种, 作为用电信息采集应用来说, 选择一个适合的算法是最重要的。根据系统采用J2EE平台, 优先采用JDK中实现的方法:hashCode () 和CRC32的算法。由于hashCode () 采用质数31的乘法, 在较短的字串会出现较小的哈希值, 导致在0～232-1中分布不均匀, 通过比较这两种算法的算法复杂度和分布情况, 在本系统中采用了CRC32作为哈希算法。

2 一致哈希算法

在日常负载均衡方案中, 除了采用硬件负载均衡外, 通常使用的方法是根据key的hash (Object) %服务器数 (N) 取余数的方法来决定当前这个key的内容发往哪一个服务器, 映射公式为hash (Object) %N, 该方案具有较好的分布性, 但是一旦出现服务器宕机或增加服务器时, 映射公式变为:hash (Object) % (N-1) 或hash (Object) % (N+1) , 这意味着所有的任务必须重新分配, 对于系统而言, 这是一场灾难。是否有更好的方法来解决问题, 这就是一致哈希算法。

一致哈希算法在1997年由麻省理工学院提出, 在移除、添加一个服务器时, 它能够尽可能小地改变已存在key映射关系, 尽可能地满足单调性的要求, 目前这种哈希算法的应用越来越广泛。基本原理如下:

1) 通常的hash算法 (CRC32) 都是将Object映射到一个32位的key值, 也即是0～232-1的数值空间, 形成一个首 (0) 尾 (232-1) 相接顺时针的圆环;

2) 将服务器的标识 (主机名或IP) 当作Server, 计算相应的hash值, 放入到0～232-1的环中;

3) 计算对象或任务标识, 将对象或任务 (Object) 交给顺时针最近的服务器, 即满足hash (Object) hash (Server) 的条件的最小哈希值服务器;

4) 当增加或删除服务器Server时, 计算服务器标识hash值, 并放入环中, 查找满足hash (Server1)

3 用电信息采集系统设计

用电信息采集系统实现包括逻辑架构设计、物理架构设计和算法实现3个部分。

3.1 逻辑架构设计

按照国家电网公司电力用电信息采集系统建设规范, 系统在逻辑方面分为采集层、通信层以及主站层3个层次 (见图1) , 其中主站层又分为数据采集、数据管理、基本功能及扩展功能等。

主站层实现采用分布式多层结构, 分表现层、应用层、服务层、数据层, 应用层进一步细分为采集子层和业务子层、对外接口等。在系统的实现中, 一致哈希算法主要应用于采集子层。

采集子层在逻辑上由通信前置模块、采集前置模块、采集接口模块和调度管理模块组成, 模块结构如图2所示。

通信前置模块实现通信管理、通信报文解析和报文转发功能。负责通道的初始化、建立、维护、通信和关闭;负责报文的组帧、分拆, 丢弃并记录异常报文, 对心跳报文进行应答;向终端转发采集前置下发的报文, 将终端上行的成帧的登录、注销、数据报文转发至采集前置, 并记录通信日志。

采集前置模块实现报文接收、协议解析、任务调度、数据处理和缓冲管理。负责接收通信前置转发报文, 接收采集接口转发的配置信息和实时任务;负责报文协议解析和按照规约组装报文;负责定时任务调度, 监控任务的执行;负责相关数据入库、异常数据处理;档案数据和入库数据的缓存管理。

采集接口模块实现应用命令、配置信息的接收和转发, 转发采集前置模块发送的实时任务。

调度管理模块实现服务器注册、运行监控、状态广播、任务切换、配置信息的接收和转发, 转发采集前置模块发送的实时任务。

3.2 物理架构设计

系统的物理架构包括负载均衡器、通信前置机、采集前置机、任务调度机、接口服务器、数据服务器和应用服务器 (见图3) 。

负载均衡器实现应用服务集群和通信前置集群的负载均衡, 为了提高负载均衡的吞吐率, 采用了4层交换。

通信前置机运行通信前置模块, 各前置机之间完全对称, 通过负载均衡器实现负载均衡和高可靠性。

任务调度机运行调度管理模块, 实现日志的统一存储, 通信前置机和采集前置机的状态监测和广播, 为消除单点故障, 任务调度机一般采用热备方式运行。

采集前置机运行采集前置模块, 各节点完全对称, 通过一致哈希算法实现负载均衡和高可靠性。

接口服务器运行采集接口模块, 是采集前置机和应用服务器间的桥梁。

数据库服务器采用Oracle10g, 实现采集档案和数据的存储。

应用服务器采用WebLogic9.2集群, 提供用户访问的服务。

3.3 一致哈希算法实现

一致哈希算法运行于通信前置机和接口服务器, 用于确定终端由哪台采集前置机处理, 具体步骤如下。

1) 采集前置机每10 s向任务调度机发送心跳报文, 心跳报文包括采集前置的标识 (Server ID) 。

2) 任务调度机监听心跳报文, 判断报文是否发生变化, 即是否有新增Server ID的报文或有超时未收到心跳报文, 如果有, 则连续监听3个周期 (30 s) , 确认是否发生了变化, 如发生了变化, 更新采集前置机列表, 向通信前置机、接口服务器和采集前置机发布状态变化信息。

3) 采集前置机收到任务调度机发布的状态信息后, 根据采集前置机服务器列表, 按照一致哈希算法, 将属于本机处理的终端信息加载至缓冲, 删除在缓冲中不属于本机处理的终端信息。

4) 通信前置机、接口服务器收到任务调度机发布的状态信息后, 更新采集前置机列表, 根据一致哈希算法重新计算终端的采集前置机。

4 结语

本文针对用电信息采集系统的现状, 对一致哈希算法、用电信息的逻辑架构、物理架构及算法的实现进行了探讨, 并对系统的负载均衡和高可靠性进行了研究, 采用硬件负载器和软件一致哈希算法相结合的方式, 满足了用电信息采集系统的高性能、高可靠性和大容量的需求, 验证了相关技术的可行性。

摘要：电网公司的用电信息采集系统具有数据量大、在线终端多、通道类型多和应用场景复杂等特点, 传统的负载均衡的方式, 在增加前置机或前置机故障时, 终端协议处理都会发生大规模的迁移。文章提出了采用硬件负载均衡器实现通信负载均衡, 采用一致哈希算法实现采集前置机的负载均衡;对哈希算法进行了分析比较, 选择CRC32查表法, 保证了哈希算法的高效、单调和均匀分布, 在前置机发生变化时, 仅有少数终端发生迁移, 不发生终端大规模的迁移, 确保负载均衡, 保证了系统的稳定性和可靠性。

关键词：用电信息采集,哈希算法,一致哈希算法,分布式,负载均衡

参考文献

[1]刘振亚.国家电网公司信息化建设工程全书一体化平台卷数据中心篇[M].北京:中国电力出版社, 2008.

[2]刘振亚.国家电网公司信息化建设工程全书一体化平台卷企业应用篇[M].北京:中国电力出版社, 2008.

[3]国家电网公司.国家电网公司标准Q/GDW378.1-2009电力用户用电信息采集系统设计导则第一部分:主站软件设计导则[S].

[4]KARGER D, LEHMAN E, LEIGHTON T, et al.Consistent hashing and random trees:Distributed caching protocols for relieving hot spots on the world wide web[A].ACM Symposium on Theory of Computing[C].1997.

基于双层哈希表的中文分词算法优化 第4篇

目前自动分词的基本算法主要分为三大类:基于词典的分词方法, 基于理解的分词方法、基于频度的分词方法。基于词典的分词方法出现较早, 方法简洁, 易于实现, 应用较广, 但要提高精度往往要结合其它方法。基于理解的分词方法是通过让计算机模拟人对句子的理解, 达到识别词的效果, 但这种方法需要使用大量的语言知识和信息, 数据量大, 同时汉语语言知识的笼统性、复杂性, 难以将各种语言信息组织成机器可直接读取的形式, 导致该方法尚处于试验阶段。基于统计的分词方法从形式上看, 词是稳定的字的组合, 因此在上下文中相邻的字同时出现的次数越多, 就越有可能构成一个词。但这种方法有一定的局限性, 会经常抽出一些共现频度高, 但并不是词的常用字组, 例如“这一”、“我的”等, 并且对常用词的识别精度差, 时空开销大。

2 算法实现

本算法改进的原则是缩短文本词库的读取时间, 以及提高分词的速度与效率, 所以主要从词典的数据结构和分词过程入手。

2.1 改进的分词词典

分词词典的查询速度是匹配算法效率的直接决定因素。常用的分词词典机制有: (1) 基于整词二分的分词词典机制; (2) 基于TRIE索引树的分词词典机制; (3) 基于逐字二分的分词词典机制。整词二分和TRIE索引树是分词词典机制的两个极端, 前者数据结构简单、占用空间小, 构建及维护也简单易行, 但由于采用全词匹配的查询过程, 效率低下。后者数据结构复杂, 空间浪费较为严重, 树的构造和维护也较为繁琐, 而其逐字匹配过程效率较高。逐字二分仍然采用整词二分的数据结构, 效率提升有限。

根据对通用词典的统计分析得知多字词语使用频度较低, 因此改进的词典吸纳了“整次二分”及“TRIE索引树”二者的优点, 采用两层哈希表加动态数组的结构, 只对词语的前两个字顺次建立哈希索引, 构成深度仅为2的TRIE子树, 词的剩余字串则按序组成类似“整词二分”的词典正文。第一层HASH表的键为待分字符串的首字, 即存储的是字典中的词S=C1C2C3C4C5C6的第一个字C1, 值对应的是内层哈希表, 此内层哈希表的键为待分字符串的次字, 即存储的是词S的第二个字C2, 值对应的是一个动态数组形式保存的剩余字串ArrayList, 即存储的是C3, C3C4C5, C3C4C5C6。

词典结构如表1所示:

2.2 改进的分词算法

数据结构改进后, 就必然要一种特定的算法与之匹配, 下面根据上文中的词典结构给出分词算法的实现, 其中词典采用一般的文本词库。

假设对字符串S=C1C2C3C4C5C6进行正向最大匹配分词, 其算法可描述如下: (1) 取首字C1和次字C2, 在词表首字哈希索引中定位C1; (2) 判断以C1为关键字的外层哈希表的次哈希表HashTable2中是否包含关键字C1; (3) 不包含C2, 则C1为单字, 一次分词结束; (4) 包含C2, 则用C3, C3C4, C3C4C5, C3C4C5Ci与次哈希表中关键字C2对应的ArrayList (即{C3, C3C4, C3C4C5, C3C4C5C6, }) 中的对象匹配; (5) 匹配不成功, 则C1C2为词, 分词成功; (6) 匹配成功则最后一次匹配成功的C3C4C5Ci就为成功分得的词; (7) 从字Ci+1开始下一次分词。

2.3 模块的评测

评价中文分词算法性能参数主要有四个:查准率、查全率、召回率和分词效率。

查准率:算法分得的正确的词的个数与分得的所有的词的个数之比。

查全率:算法所分得的词的个数和原文应有的词的个数之比。

召回率:算法最初分得的词数与经过处理 (歧义处理等之后) 剩下的词数之比。

分词效率:单位时间内所分得的词的个数。

经过一定量的文本测试, 改进算法的查准率为92.3%, 查全率为95.6%, 召回率为93.5%, 分词效率为253.56 (字/ms) .

在评测中我们随机选取一段新闻文字进行测试, 测试结果如图1所示。

在读取约2.5M的文本词典时只用了135毫秒的时间, 对数量较少的文本分词时间更是可以忽略不记。总体而言, 改进的算法达到了较好的分词效果, 具有较高的分词速度与效率。

3 结束语

本文提出的改进的基于双层哈希表的中文分词算法的优点是在节省空间的同时提高了分词速度与准确度。首先通过双哈希表的动态查找, 有效地降低了词语的查找范围, 提高了算法的效率。其次, 本算法基于适当的数据词典的容量, 改进后的词典结构在一定程度上提高了词库的读取速度。该方法对词的匹配时间不再受限于词典中的词条数目, 只与待切分的语句长度有关, 改进的正向增字最大匹配算法, 对于长句词语的选取有较高的准确度。同样, 本算法在短词精确度, 词语间歧义字的选择等方面仍然存在一定的问题, 有待改进。

参考文献

[1]李庆虎, 陈嘏健, 孙家广.一种中文分词词典新机制一双字哈希机制[J].中文信息学报, 2003 (4) .

[2]廖名学, 范植华.基于素数序列的Java哈希表性能优化[J].计算机工程与应用, 2008 (3) .

[3]严蔚敏, 吴伟民, 米宁.数据结构[M].北京:清华大学出版社, 1999.

[4]向晖, 郭一平, 王亮.基于Lucene的中文字典分词模块的设计与实现[J].现代图书情报技术, 2006 (8) .

哈希表查找算法的性能分析与研究 第5篇

1 哈希表一般知识

哈希查找是通过哈希函数将关键字集向地址集进行的一种映射, 通过这种映射关系建立起哈希表 (也称为散列表) 。一个好的哈希函数可以将记录集中的记录比较均匀地映射到地址集中, 而很少有冲突发生。 所谓 “冲突” 就是不同的关键字所对应的记录竞争同一个存储单元的现象。 但是, 无论多么好的哈希函数也很难不产生地址冲突。 因此, 哈希表查找过程要包括构造哈希函数、 指定处理冲突的方法、 并照此建立哈希表, 然后才能对哈希表进行查找及性能分析。

1.1 常用的构造哈希函数的方法

(1) 直接定址法

H (key) =a×key+b

(2) 数值分析法

分析关键字集, 找出分布均匀的某几列作为散列地址。

(3) 平方取中法

一个整数平方之后取出中间的某几位作为散列地址, 基本上也能均匀分布。

(4) 折叠法

可分为移位折叠与间界折叠两种方法。

(5) 随机数法

通过随机函数构成哈希地址, 如H (key) =rand (key) 。

(6) 除留余数法

H (key) =key Mod p。 通过经验分析, 除数p一般选取不超过表长的质数或超过整数20 的两个质数乘积 (不超过表长) 。

1.2 常用的处理冲突的方法

(1) 开放地址法

1) 线性探测再散列

冲突时向后依次探测空闲地址。 Hi (key) = (H (key) +di) Mod m。 其中, m为表长, di=1, 2, 3, ...。 这种方法总能找到空闲地址, 但容易产生数据聚集现象, 从而达不到记录的均匀分布。

2) 平方 (二次) 探测再散列

Hi (key) = (H (key) +di) Mod m。 其中, m为表长, di=12, -12, 22, -22, 32, -32, ...。 这种方法能在一定程度上避免数据的聚集现象, 但是可能永远找不到空闲地址。

(2) 链地址法 (也称拉链法或外部链接法)

冲突时, 将冲突的记录存入相应的链表中。

(3) 建立公共溢出区

冲突时, 将所有冲突的记录存入一个链表或数组中, 该链表或数组就称为公共溢出区。

一般地, 在查找过程当中找到指定元素后带回找到的对象所在数据表中的位置, 即整数下标或地址指针, 否则带回-1或空指针。

为讨论问题方便, 以整数作为记录的关键字, 且仅考虑记录与关键字相同的情形, 哈希函数采用除留余数法, 即H (key) =key % R。

以下算法当中使用的编程语言环境为Turbo C 2.0 或Vi-sual C++ 6.0。

2 链地址法处理冲突的哈希表

示例, 假设表长为7, 哈希函数为H (key) =key%7, 处理冲突的方法为链地址法, 试根据输入序列{ 27, 38, 91, 20, 7, 54, 68, 19, 25, 36} 构造哈希表, 并计算成功与失败的平均查找长度 (ASL) 。

先初始化一个空的指针数组, 再按照给定的哈希函数 (H (key) =key%7) 将生成的结点插入到各自的链表中 (如下图所示) , 即可建立一个哈希表。

成功时的平均查找长度计算为: ASLsucc= (1*6+2*3+3*1) /10=15/10=1.5。

失败时的平均查找长度计算为: ASLfail= (0*1+1*3+2*2+3*1) /7=10/7≈1.43

2.1 建立哈希表的算法

2.2 哈希表的查找算法

2.3 平均查找长度的计算算法

(1) 成功时的平均查找长度

(2) 失败时的查找长度

3 结语

关于哈希表查找算法, 各类相关教材中都有介绍, 但计算平均查找长度的算法介绍的不多。 通过平均查找长度的计算, 更能清楚地哈希表的查找过程。 以上仅简略介绍了哈希表在链地址法处理冲突的情况下查找算法的性能分析, 主要是平均查找长度的计算方法, 希望能对同行和读者有些帮助, 不妥之处还希望指正。

参考文献

[1]秦玉平, 马靖善.数据结构 (C语言版) [M].2版.北京:清华大学出版社, 2012.

[2]严蔚敏, 吴伟民.数据结构 (C语言版) [M].北京:清华大学出版社, 2007.

[3]秦玉平, 王丽君, 刘伟.查找算法平均查找长度的计算方法[J].渤海大学学报 (自然科学版) , 2012, 32 (4) :353-357.

[4]马靖善, 秦玉平.顺序存储二叉树的遍历及其应用研究[J].渤海大学学报 (自然科学版) , 2013, 34 (2) :172-175.

哈希算法 第6篇

根据现行机动车牌照标准GA 36.1-2001,车牌的主要颜色为蓝底白字、黄底黑字、白底黑字、黑底白字。对于通用汽车牌照,其尺寸为440mm长,140mm宽,长宽比3.14:1。格式为Xl X2·X3X4X5X6X7。X1是各省、直辖市的简称,有50个左右的汉字;X2是英文字母,各省、直辖市下属地市区的排序;X3X4X5是英文字母或阿拉伯数字;X6X7是阿拉伯数字。各字符均为45mm宽,90mm高。

汽车牌照目标区域的特征分析:(1)字符和牌照底色在灰度值上存在明显跳变,而字符本身、牌照底色本身都有比较均匀的灰度;(2)汽车牌照有一个连续或由于磨损而不连续的边框,通用车牌由7个字符组成,基本呈水平排列,间隔均匀;(3)不同图像中牌照字符的具体大小、位置不确定,但字符的长宽比变化有一定范围。

2 算法流程

根据上述对车牌特征的分析,预识别车牌字符,首先对车牌图像进行预处理,包括灰度化、灰度拉伸、倾斜度矫正、二值化处理等操作,针对该二值图像运用削峰填谷操作,从而实现对车牌的字符分割;然后对每个字符进行特征提取;再根据字符结构特征对车牌字符进行分类判决、模糊识别,最终确定该字符在字库中的唯一编号,进而达到识别车牌的目的。

3 算法实现

3.1 基本数据结构。

(1)链表头结点(Ch)Ch是一个结构体,有三个成员,first作为指向链表头结点的指针,last作为指向链表最后一个结点的指针,number表示该链表中结点的个数,该链表用来临时存储投影分块后各块的数据。(2)链表结点(Ct)Ct是一个结构,有五个成员,ave表示每个投影分块内的均值,left表示该投影块在图像中左侧的起点坐标,right表示该投影块在图像中右侧的结束坐标pre是链表中指向前驱结点的指针,next是链表中指向后继结点的指针。

3.2 算法的实现。

(1)汽车牌照预处理:本过程输入为一个经过定位处理的汽车牌照子图像,该子图像分别经过灰度化处理、灰度拉伸、倾斜度矫正,从而获得位置端正的车牌图像,然后再对其进行优化的二值化处理、削峰填谷操作,最终获得车牌上每个字符的边界位置信息,并将其按从左到右的顺序存入链表List中。

(2)车牌字符特征提取:经过牌照预处理操作,已经获得了车牌上每个字符的黑白二值子图像的边界,本算法充分考虑车牌字符的结构特点,将每个字符按照计算出的边界值均匀四等分,形成左上(LT)、左下(BT)、右上(RT)、右下(RT)四个部分。分别计算每个部分字符黑色像素所占的百分比,再计算整个字符黑色像素所占的百分比,于是对于每个字符通过上述划分计算,共获取了5个特征。

(3)车牌字符的分类判决:对车牌字符分类是基于非线性的哈希散列技术。首先按照如下算法计算每个字符所对应的数组编号。考虑车牌字符、尤其是汉字的结构特征,算法中前两个比较对应字符的左右两部分进行,而中间两个比较对应字符的上下两部分进行,这两部分的权值较大,后两个则是对字符对角的两组特征进行比较,权值较小。经过上述比较后,得到的sum的值是一个介于0和63之间的整数,也是散列字符的初始地址。

(4)车牌字符的模糊识别:经过上面的哈希散列,得到了一个对应被判断字符的初始位置,但理论和实验都证明,有若干字符的结构是相似的,即有若干字符经过第3步的判定,它们得到相同的位置,即哈希散列发生了冲突,于是只能借助七个特征中的其它三个来解决。

4 实验结果及分析

本例利用一个完整的车牌图像进行检验,该图片为一个212×71的彩色车牌图像,经过牌照字符特征提取数据。其中CR1~CR7分别表示字符黑点整体百分比、左上(LT)、左下(BT)、右上(RT)、右下(RT)分块黑点百分比、字符水平中线黑点数统计值、字符垂直中线黑点数统计值。

分类判决和冲突的解决两部分均用到了模糊判断。对车牌字符分类时,用的比较并不关心前者大于后者多少,这很符合车牌的实际情况。因为车牌在实际使用时会有磨损、污损,获取车牌图像时会受光照等因素的影响,车牌字符实际点数的多少不一定与理想车牌一致,但上述影响对一个字符的各个部分基本是一致的,因此模糊判决可大大提高字符分类的健壮性,也是优于模板匹配算法的关键。

接下来又对近百幅车牌图像进行了字符识别测试,成功率达94.5%,经分析识别错误主要是因为车牌字符局部严重污损而导致的字符所在位置的黑点数发生扭曲。

5 结束语

5.1 哈希散列技术较好的解决了车牌字符的分类问题,此处用

到了二叉迭代分类算法,使散列范围基本上比较均匀,为解决冲突时的二次散列奠定了较好的基础。

5.2 模糊识别技术极大的增强了系统适应复杂环境条件的能力,使系统运行更健壮。

综上所述,本文提出的算法较好的解决了车牌字符的"均匀"散列以及复杂条件下的字符识别的稳定性-两个车牌识别中的关键技术。与同类算法相比,其适应能力明显增强。

参考文献

[1]OZBAY S,ERCELEBIE.Automatic Vehicle Identification by PlateRecognition[J].Transactions on Engineering,Computer and Technology,2005,9.

[2]Lienhart R,Membe,Wemicke A.Localizing and Segmenting Text inImages and Vidoes[J].IEEE Transactions on Circuits and Systems forVideoTechnology,2002,12(4):256-268.

哈希算法 第7篇

关键词：哈希算法,FPGA软核,以太网网桥

1 引言

以太网网桥工作在数据链路层, 它根据MAC帧的目的地址对收到的帧进行转发, 具有帧过滤功能, 通过可配置的策略可以实现以太网数据的通信管理。FPGA已经广泛应用于电子通信领域, 具有丰富的IP核资源, 本文中使用了三态以太网软核, 支持IEEE 802.3标准, 可以进行灵活的配置, 适用于快速的以太网设计。哈希表作为一种快速查找表, 在以太网桥的地址表的维护中, 效率和处理速度高于MAC地址直接构成的查找表。

2 设计方案

网桥用于连接两个或者多个不同的局域网。当一帧到达时, 网桥必须决定将其丢弃还是转发。如果转发, 则必须决定发往那个LAN接口, 在插入网桥之初, 由于网桥不知任何目的地的位置, 因而采用扩散方式, 将每个到来的帧送往除发送该帧的LAN接口外的所有其他LAN接口[1];随时间的推移, 网桥通过收集以太网帧的源MAC地址, 创建并完善MAC地址表后, 将以太网帧的目的MAC地址在MAC地址表内查找, 查找到相同的MAC地址后, 该帧将不会被转发, 而直接丢弃处理, 当MAC地址表内不能找到相同的MAC地址, 则对该帧进行转发处理。使用哈希算法对地址表内的MAC地址进行运算后将运算所得的哈希值存储, 创建哈希表, 可以将原来48位的MAC地址表缩小若干倍, 从而减少查找相同MAC地址所需的时间。

3 硬件设计

以太网网桥的硬件设计组成由以太网接口电路、FPGA电路以及时钟、电源等组成。

以太网接口电路提供设备对外的以太网接口, FPGA电路完成设备的数据处理操作;界面显示用来显示设备运行状态;时钟电路向其他电路提供工作所需的时钟信号;电源电路负责设备的供电。以太网网桥的硬件连接图如下图1所示。

4 软件设计

本文设计的以太网网桥软件部分位于F PGA芯片内, 采用VHDL编程语言完成。软件主要由两部分组成, 以太网媒体访问控制 (MAC) 模块设计和数据转发控制模块。

4.1 MAC模块设计

MAC模块负责对以太网数据帧的封装、解封装 (发送、接收) :包括成帧 (帧定界、同步) 、寻址 (处理原地址和目的地址) 、校验 (检测物理层的传输错误) 、介质分配 (避免冲突产生) 、和竞争解决 (冲突的处理) 等功能。

MAC模块使用了Altera公司的Triple Speed Ethernet Mega Core软核作为主体进行了设计。该软核支持IEEE 802.3标准, 可以提供一个10/100/1000Mb的以太网MAC, 并支持半双工和全双工工作模式[2]。

Triple Speed Ethernet Mega Core软核通过GMII/MII接口直接连接外部的PHY芯片进行数据通信, 并通过PHY的管理接口对PHY进行配置和管理;使用Quarters软件的IP核配置向导对软核进行配置后, 再通过VHDL程序模块根据用户需求进行初始化配置后, 便可正常使用。

4.2 数据转发控制模块设计

数据转发控制模块用来完成以太网数据帧的转发管理, 决定数据帧是否丢弃或者转发。

数据转发控制模块的实现步骤为:1) 当数据帧到达数据转发控制模块后, 提取出该帧的源MAC地址和目的MAC地址;2) 依据哈希函数Hash_SA[n]=SA[n]+SA[n+10]+SA[n+20]+SA[n+30]+SA[n+40]0≤n≤7;Hash_SA[8]=SA[8]+SA[18]+SA[28]+SA[38];Hash_SA[9]=SA[9]+SA[19]+SA[29]+SA[39];其中SA[0~47]为48为的源目的地址, 可以得到10为的Hash_SA[0~9], 同理可以得到10位的Hash_DA[0~9][3];3) 利用Hash_SA[0~9]创建并更新哈希表;4) 遍历哈希表清楚5分钟内未更新的MAC地址, 以保持哈希表的时效性;5) 利用Hash_DA[0~9]进行哈希表的查找;6) 当可以哈希值对应的地址区内找到与目的MAC相同的MAC地址时, 丢弃该帧, 反之将该帧转发给另一个端口。

5 结语

本文设计的以太网网桥在以Altera公司的Cyclone II系列的EP2C35F672C8为平台的网桥设备上进行了试验验证。使用了FPGA内4824个LE (15%) 和2.8Mbit (50%) 的存储器资源, 经验证, 可以正常完成以太网网桥的设计功能。

参考文献

[1]周明天.TCP/IP网络原理与技术.北京:清华大学出版社, 1996.

[2]周华茂等.以太网MAC层IP软核设计方法研究[J].半导体技术, 2007, 32 (8) :692-696.

哈希算法 第8篇

哈希(hash)计算是常见的数据分布技术,其通过求模运算来计算哈希值,然后据此将数据映射到存储空间中。设有由N个存储节点组成的存储空间,采用简单哈希计算将一个数据对象object映射到存储空间上的公式为:hash(object)%N。由于只是采用了简单的求模运算,使得简单哈希计算存在很多不足:

1)增删节点时,更新效率低。当系统中存储节点数量发生增加或减少时,映射公式将发生变化为hash(object)%(N±1),这将使得所有object的映射位置发生变化,整个系统数据对象的映射位置都需要重新进行计算,系统无法对外界访问进行正常响应,将导致系统处于崩溃状态。

2)平衡性差,未考虑节点性能差异。由于硬件性能的提升,新添加的节点具有更好的承载能力,如何对算法进行改进,使节点性能可以得到较好利用,也是亟待解决的一个问题。

3)单调性不足。衡量数据分布技术的一项重要指标是单调性,单调性[1]是指如果已经有一些内容通过哈希计算分派到了相应的缓冲中,当又有新的缓冲加入到系统中时,哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去,而不会被映射到旧的缓冲集合中的其他缓冲区。

由上述分析可知,简单地采用模运算来计算object的hash值的算法显得过于简单,存在节点冲突,且难以满足单调性要求。修改后的一致性哈希算法正是近年来提出的一个解决方案,在Amazon公司的Dynamo中得到了很好的体现。

2 一致性哈希算法的工作原理

一致性哈希算法[2,3]是当前较主流的分布式哈希表协议之一,它对简单哈希算法进行了修正,解决了热点(hot Pot)问题,它的原理分为两步,如图1所示:

首先,对存储节点的哈希值进行计算,其将存储空间抽象为一个环,将存储节点配置到环上。环上所有的节点都有一个值。

其次,对数据进行哈希计算,按顺时针方向将其映射到离其最近的节点上去。

当有节点出现故障离线时,按照算法的映射方法,受影响的仅仅为环上故障节点开始逆时针方向至下一个节点之间区间的数据对象,而这些对象本身就是映射到故障节点之上的。当有节点增加时,比如,在节点A和B之间重新添加一个节点H,受影响的也仅仅是节点H逆时针遍历直到B之间的数据对象,将这些重新映射到H上即可,因此,当有节点出现变动时,不会使得整个存储空间上的数据都进行重新映射,解决了简单哈希算法增删节点,重新映射所有数据带来的效率低下的问题。

一致性哈希算法作为分布式存储领域的一个重要算法,它基本解决了以P2P为代表的存储环境中一个关键的问题如何在动态的网络拓扑中对数据进行分发和选择路由。在算法所构成的存储拓扑中,每个存储节点仅需维护少量相邻节点的信息,并且在节点加入/退出系统时,仅有相关的少量节点参与到拓扑的维护中,这使得一致性哈希算法成为一个具有实用意义的DHT(Distributed Hash Table,分布式哈希表)算法。

但是一致性哈希算法尚有不足之处。第一,在查询过程中,查询消息要经过O(n)步(n代表系统内的节点总数)才能到达被查询的节点。不难想象,当系统规模非常大时,节点数量可能超过百万,这样的查询效率显然难以满足使用的需要。第二,当应用一致性哈希算法的分布式存储系统中添加或者删除新的物理节点时,要将下一个节点与之相关的数据迁移过来,查询命中率和存储效率下降,影响系统的整体性能。

3 一致性哈希算法的改进

一致性哈希算法具有随机性,当节点数量较少时节点在环上分布不够均匀,对于节点可能存在的性能差异也没有考虑,为解决这个问题,以Dynamo为代表,提出了基于虚拟节点的改进算法,其核心思路是引入虚拟节点,每个虚拟节点都有一个对应的物理节点,而每个物理节点可以对应若干个虚拟节点。

Dynamo将圆环划分成了M等分,若加入物理节点为N个,则每个物理节点拥有V=M/N个节点数。当有物理节点离线时,由于该节点对应的虚拟节点均匀地分布在环上,其附近的节点将会均匀地分担这个节点的原有负载,当有新节点加入时,同理,其他节点的负担也将均匀转移到其上。此外依据物理节点的实际性能为权值分配环上的虚拟节点数目给物理节点,也解决了存储节点性能差异的问题。

为解决数据迁移带来的效率降低问题,可以将新增节点完成的数据迁移分布在每一次的查询任务中去,相当于每一次查询都可以迁移一小部分数据,此外,还可以在系统闲暇时间进行数据迁移,这样可以有效地提高效率。

4 一致性哈希散列函数的选择

对于一致性哈希算法来说,哈希值的计算尤为重要,从一致性哈希算法提出至今,已经有多种应用于一致性哈希算法的哈希函数,比较有代表性的有CRC32_HASH、KETAMA_HASH、FNV1_32 HASH、NATIVE_HASH、MYSQL_HASH等。下面将在使用一致性哈希算法的情况下,通过增加物理节点,测试不同散列函数下命中率和数据分布所发生的变化,测试方法参考了资料[4]。

对一段英文进行单词统计,并将结果存储到10个节点上去,在存储统计结果之后,再增加两台存储节点,设单词为哈希计算中的key,次数为value,单词总数为3996,并统计此时的缓冲命中率和数据分布的情况,结果如表1所示。

NATIVE命中率最高,但其分布极不均匀,主要集中在1个节点上;KETAMA是基于MD5的散列函数,其在保证较高命中率的同时,数据分布也最为均匀,事实上,它也是公认的广受推荐的一致性哈希算法的散列函数。

5 总结

在以云存储为代表的分布式存储系统日益发展的今天,作为数据均衡算法的一个代表,改进后的一致性哈希算法可以使得系统负载更加均衡,最大程度的避免资源浪费以及服务器过载,降低硬件变化带来的数据迁移代价和风险,如何进一步优化算法性能,值得进一步研究。

参考文献

[1]刘鹏.云计算[M].北京:电子工业出版社,2010:71-76.

[2]Robert Devine.Design and Implementation of DDH:A Distributed Dynamic Hashing Algorithm[C].Proceedings of 4th International Con-ference on Foundations of Data Organizations and Algorithms,1993.