网络爬虫需求

《网络爬虫需求》由会员分享，可在线阅读，更多相关《网络爬虫需求（19页珍藏版）》请在装配图网上搜索。

1、学校：中南大学学院：信息科学与技术学院专业班别：计算机软件专业NIIT081姓 名： 谭东方指导教师：完成日期：摘要随着网络的迅速发展，万维网成为大量信息的载体，如何有效地提取并利用这些信息 成为一个巨大的挑战。搜索引擎(Search Engine)，例如传统的通用搜索引擎AltaVi sta，Yahoo!和Google等，作为一个辅助人们检索信息的工具成为用户访问万维网的 入口和指南。但是，这些通用性搜索引擎也存在着一定的局限性，如：(1) 不同领域、不同背景的用户往往具有不同的检索目的和需求，通用搜索引擎 所返回的结果包含大量用户不关心的网页。(2) 通用搜索引擎的目标是尽可能大的网络覆盖

2、率，有限的搜索引擎服务器资源与无限的网络数据资源之间的矛盾将进一步加深。(3) 万维网数据形式的丰富和网络技术的不断发展，图片、数据库、音频/视频多媒体等不同数据大量出现，通用搜索引擎往往对这些信息含量密集且具有一定结构的数据无能为力，不能很好地发现和获取。(4) 通用搜索引擎大多提供基于关键字的检索，难以支持根据语义信息提出的查 询。为了解决上述问题，定向抓取相关网页资源的聚焦爬虫应运而生。聚焦爬虫是一 个自动下载网页的程序，它根据既定的抓取目标，有选择的访问万维网上的网页与相关的链接，获取所需要的信息。与通用爬虫(general purpose web crawler)不同,聚焦爬虫并不追

3、求大的覆盖，而将目标定为抓取与某一特定主题内容相关的网页，为 面向主题的用户查询准备数据资源。关键字：网络爬虫程序，WEB爬虫，网页蜘蛛，网络机器人AbstractThis paper first introduces the key techniques and theories which are required in the realizationof the extensible Spider, on the basis of which we then usethe oriented-object methods to have analyzed and designed a We

4、b Spider with extensibility. Finally, the programming work has been realized on the JCreator platform with the Java language.The designing of the extensible Spider is made up of two major parts: the Client crawler and the Server monitor. The Client is responsible for the page-collection job, which r

5、eceives URL of the web pages to be crawled from the server and transmits those out of its crawling range. In order to reduce the response time, the page-collection has borrowed the multithreading technique to improve the system s performance. The URL transition has utilized the “Character Conversion

6、 function of the MD5 algorithm and the “Splitting Construetor” of the hashing function. The server monitor takes charge of the arrangement of the active spiders and the transition of the arriving URL: the system would allocate an unique ID for every crawler to realize unified management as well as m

7、aking a reasonable judgment for every URL from clients to determine which active spider this URL should be sent to. In the system, the running process, including the start and interruption, of the crawlers is comple tely cont rolled by the server, and the server can dynamicallysupervise the collecti

8、on status of each of the crawler.It has been proved by the experiment that this system has the characteristic of good extensibility. Also, it is capable of adding the active spiders during the running process as well as remembering the collection interruption point .Meanwhile, weve found that the sp

9、eed of the downloading pages as well as the number of the active crawlers is the key factor that would have an effect on the whole systems performance.Keywords: Extensibility; Web Spider; Multithreading; the URL Transition.第1章绪论：1.1课题背景随着国际互联网(internet )的迅速发展，网上的信息越来越多，全球目前的网页超过20亿，每天新增加730万网页。要在如此浩

10、瀚的信息海洋里寻找信息，就像“大海捞针”一样困难。搜索引擎正是为了解决这个问题而出现的技术。搜索引擎是通过互联网搜索信息的重要途径。它要用到信息检索、人工 智能、计算机网络、分布式处理、数据库、数据挖掘、数字图书馆、自然语言 处理等多领域的理论和技术，具有很高的综合性和很强的挑战性。本文研究的 内容是作为搜索引擎关键的一部分的网络爬虫，首先，简略介绍一下搜索引搜索引擎虽然所采用的技术和实现的方法各有不同，但是总体来说可以分 为两类，一种是基于目录的搜索引擎，另一种是基于全文检索的搜索引擎。 早期的搜索引擎很多都是基于目录的搜索引攀，由于人工干预较多，故在 覆盖的范围上要远远的小于基于信息采集器

11、的搜索引擎。一般来说，由于使用 了人（专家）来对网站进行归纳和分类，网站分类技术为网络信息导航带来了极 大的方便，广受人们的欢迎。但是它的缺陷除了成本较高之外，对网站的描述 也十分简略，其描述能力不能深入网站的内部细节，因此用户查询不到网站内 部的重要信息，造成了信息丢失1。例如：如果对一个进行电脑硬件销售站点 的目录分为是商业与经济 公司电脑硬件公司。对其描述为“显示器、电源、 硬盘内存等销售”。用户在以“显示器”、“硬盘”为关键字进行检索时，就 能检索到。但如果该站点中还包含有对于主板和显卡的介绍，用户在检索“主 板”、“显卡”时，就无法检索到了。同时，对于基于目录的搜索引擎技术而 言，其

12、覆盖范围相对与基于全文检索的搜索引擎而言十分有限。 目前，在国内外各主要商业搜索引擎在技术上主要使用了全文检索技术， 下面对基于使用全文检索技术的搜索引擎进行讨论。 基于全文检索技术的搜索引擎主要由三部分组成，如图 1-1 所示，信息采 集器（网络爬虫），索引器、搜索接口。图 1-1 搜索引擎的基本构成信息采集器：主要功能就是搜集互联网上的信息资源（主要是网页和文字 信息资源）。运行信息采集器时，只要提供极少量的起始网页，信息采集器就 能够按一定的规则沿着网页上的超级链接在网络上漫游，收集资源信息，直至 遍历整个网站。它的性能在很大程度上影响了搜索引擎站点的规模。这部分是 本论文要讨论的重点。

13、索引器：由信息采集器从网上取来的信息杂乱无章，如果把它们直接用于 查询，效率将极为低微。索引器的主要功能就是分析收集的信息，建立索引库 以供查询。它主要用到的技术有分词、索引词选取、停用词过滤、索引归并、 索引压缩、索引更新、倒排文件缓存。查询接口：它是用户与搜索引擎的接口。它通常是一个Web应用程序，主要负责接收、解释用户的请求、查询索引库以及返回排序后的搜索结果。它的 用户界面友好与否是用户能否最大限度地使用搜索引擎功能的关键。 信息采集模块主动派出信息采集器进行自动搜索，信息采集器自动地在网上漫游，从一个URL或一组URL开始，访问该URL，记录该URL所指文件中所 有新的URL。然后再

14、以这些新URL的为起点，继续进行本地索引，直到再没有 满足条件的新 URL 为止。对于一些新出现的网站或在自动搜索中有所遗漏的站 点，用户也可以自行向搜索引擎提交网站地址，使得站点内容能被及时得以搜 索。得到网页内容后，信息预处理模块过滤文件系统信息，为文件系统的表达 提供各种满意的索引输出，获取最优的索引记录，使用户能很容易地检索到所 需信息。信息预处理模块要完成以下一些功能：格式过滤、词语切分、词性标注和短语识别等。最后这些被处理完的信息被送入一个数据库中，使用者在执行查询时，实际上是从这一数据库中寻找匹配网页、或资料的过程。全文检索己是一个比较成熟的技术，它能够解决对大量网页细节的检索问

15、题。从理论上说，只要网页上出现了某个关键词（如果是中文，这个关键词必须是一个词或者是词的组合），就能够使用全文检索用关键词匹配把该网页查 出来。网络爬虫，又称为Robots， Spiders以及Wanderers，几乎与网络同时出现。 第一个网络爬虫是Matthew Gray的Wanderer，出现于1993的春天。在头两届国 际万维网会议上出现过数篇关于网络爬虫的论文，如文献 24。但是那时候互 联网上的信息规模比现在要小得多，那些文章中并没有阐述如何处理现在所面 临的海量网络信息的技术。每个搜索引擎的后台，都有相应的网络爬虫在工作 着。但是出于互相竞争的原因，这些网络爬虫的设计并没有公开，

16、除了以下 3个： Google Crawler , InternetArchive Crawler 以及 Mercator 5。搜索引擎Google中，采用了多台机器进行分布式爬行6。它的网络爬虫包括5个功能模块，分别运行在不同的进程中。一个URL Server,进程负责从一个文件里读取URL (Uniform Resource Locator )，并把它们分发给多个 Crawler进 程。每个Crawler进程运行在不同的机器上，采用单线程和异步I/O同时从近300个网站上获取数据。所有的Crawler将下载来的数据传输到同一个St ore Server进程，它将这些页面压缩并存放在磁盘上。

17、Indexer进程将这些页面从磁 盘上读出，它将、URL从HTML页面中抽取出来，并将它们存放在另一个磁盘文 件中。一个URL Resolver进程读取这个存放链接的文件，将其中的相对链接转 化为绝对链接，然后存入一个文件，这个文件供 URL Server 进程读取。Internet Archive Crawler 也使用多台机器进行爬行。每个Crawler进程可分配 64 个站点同时爬行，并且每个站点最多只分配给一个 Crawler 来爬行。每个单线程的 Crawler 进程从磁盘中读取分配给其爬行的站点的种子URL ，把它们发送到各自站点的爬行队列中。然后采用异步 I/O 从这些队列读取链

18、接，下载对 -3-哈尔滨工业大学工学硕士学位论文应的网页。一旦一个HTML网页下载下来，Crawler就将包含在其中的链接抽取 出来。如果链接指向同一个网站，那就将该链接加入到该站点的队列中；否 则，就将该链接存放到磁盘中。一个批处理进程周期地将这些链接进行过滤， 去除重复链接，并把它们放入相应站点的队列中。Mercator是一个在可扩展性方面做得非常出色的Crawler8。Mercator 完全用Java实现。它采用的数据结构可以不管爬行规模的大小，在内存中只占有限 的空间。这些数据结构的大部分都在磁盘上，在内存中只存放有限的部分，伸 缩性很强。 Mercator 采用模块化设计的思想，通过

19、替换以及增减模块可以很方 便地实现各种功能，如进行各类 Web 信息统计以及 Web 快照，体现了良好的可 扩展性。 Mercator 由 5 个部分构成，分别负责：给即将付诸下载的 URL 进行排 序；将主机名解析为 IP 地址；使用 HTTP 协议下载文档；从 HTML 文档中提取链 接；检测一个 URL 是否已经遇到过。一个网络爬虫程序通常网络爬虫从种子 URL 开始，通过网页内容解析， 跟随网页上的超链接进行下载。互联网上的信息更新很快，必须定期更新已经 搜集过的旧信息，避免无效链接，同时获取最新信息。只有高效深度的挖掘才 能使搜索引擎提供全面、即时的服务。应用于大规模系统的数据采集软

20、件有两个主要设计要求：一是必须有合理 的挖掘策略，主要是何时下载哪些页面。常用策略包括：主题式挖掘，根据 URL链接分析和网页内容对URL列表进行主题分类，然后根据类别进行有目 的的挖掘；分级式挖掘，根据站点规模、权威性、数据更新频率等参数将站点 列表进行分级，实现等级式采集。二是必须要有高度优化的采集架构，能高速 下载大量网页，要占用合理的网络流量、具有鲁棒性、易于管理。目前主要采 用服务器集群技术，由中央控制软件进行任务分发、负载平衡和运行监控。第2章分布式网络爬虫基本构架 本章讨论一个良好的网络爬虫的设计目标，然后讨论单个结点的结构设 计，最后讨论分布式网络爬虫的结构设计2.1 聚焦爬虫

21、工作原理网络爬虫是一个自动提取网页的程序，它为搜索引擎从万维网上下载网页，是搜索引 擎的重要组成。传统爬虫从一个或若干初始网页的 URL开始，获得初始网页上的URL, 在抓取网页的过程中，不断从当前页面上抽取新的URL放入队列，直到满足系统的一定停止条件，如图1(a)流程图所示。聚焦爬虫的工作流程较为复杂，需要根据一定的 网页分析算法过滤与主题无关的链接，保留有用的链接并将其放入等待抓取的 URL队 列。然后，它将根据一定的搜索策略从队列中选择下一步要抓取的网页URL，并重复上述过程，直到达到系统的某一条件时停止，如图1(b)所示。另外，所有被爬虫抓取的网页将会被系统存贮，进行一定的分析、过滤

22、，并建立索引，以便之后的查询和检 索；对于聚焦爬虫来说，这一过程所得到的分析结果还可能对以后的抓取过程给出反 馈和指导。相对于通用网络爬虫，聚焦爬虫还需要解决三个主要问题：(1) 对抓取目标的描述或定义；(2) 对网页或数据的分析与过滤；(3) 对URL的搜索策略。抓取目标的描述和定义是决定网页分析算法与 URL搜索策略如何制订的基础。而网页分析算法和候选URL排序算法是决定搜索引擎所提供的服务形式和爬虫网页抓取行为的关键所在。这两个部分的算法又是紧密相关的。2.2抓取目标描述现有聚焦爬虫对抓取目标的描述可分为基于目标网页特征、基于目标数据模式和基于领域概念3种。基于目标网页特征的爬虫所抓取、

23、存储并索引的对象一般为网站或网页。根据种 子样本获取方式可分为：(1) 预先给定的初始抓取种子样本;（2）预先给定的网页分类目录和与分类目录对应的种子样本，如Yahoo!分类结构等；（3）通过用户行为确定的抓取目标样例，分为：a）用户浏览过程中显示标注的抓取样本；b）通过用户日志挖掘得到访问模式及相关样本。其中，网页特征可以是网页的内容特征，也可以是网页的链接结构特征，等等。现有的聚焦爬虫对抓取目标的描述或定义可以分为基于目标网页特征，基于目标数据模式和基于领域概念三种。基于目标网页特征的爬虫所抓取、存储并索引的对象一般为网站或网页。具体的 方法根据种子样本的获取方式可以分为：（1）预先给定的

24、初始抓取种子样本；（2） 预先给定的网页分类目录和与分类目录对应的种子样本，如Yahoo!分类结构等；（3）通过用户行为确定的抓取目标样例。其中，网页特征可以是网页的内容特征，也可以 是网页的链接结构特征，等等。2.3系统结构2.3.1单个Spider的系统结构图单个Spider的系统结构如上图所示.每个爬虫从一组种子URL开始,首先根据初始URL 并按照机器人拒绝协议检测被访问主机是否允许访问该URL,通过检测后由HTTP/HTTPS下 载模块下载该网页。URL抽取器从下载的网页中抽取出新的URL,然后由URL过滤器逐个检 测URL是否符合过滤器限制。最后，用哈希函数计算各个URL的哈希值，

25、如果属于本Spider 的爬行范围，则将该URL加入到本地URL数据库中；否则把该URL插入到URL发送队列中， 由URL分发器定时转发给对应的Spider.232可扩展Spider的系统结构图及其爬行策略如图上图所示，为了能够高效地采集页面数据，我们在 Spider 系统中采用了 Client/Server 结构。“网络蜘蛛”由一台或多台 Spider 构成，它们通过内部通信，由信 息服务器统一管理并协同工作。由于Spider的效率受采集平台、网络性能等诸多限制，为 了达到比较理想的采集速度，我们采用了用多个Spider同时并行采集的策略。具体并行的 Spider个数需要根据实际的采集速度要

26、求和网络环境而定。显而易见，采用服务器/采集器的结构使采集系统具有很好的可扩展性。管理员可根据 系统采集规模的变化动态地调整采集器的数量，在保证系统性能的前提下尽量减少系统开 销，达到最佳的性能/价格比。而且在规模动态变化的过程中，系统能维持一致的管理和数 据输出接口。这里所说的信息服务器主要负责对全局URL队列中的URL进行分发、对采集到的页面 信息和文件信息进行缓存和压缩以及在采集过程中的一些协调和控制。为了实现的简单性， 我们采用了轮转法进行分配。并且当某个Spider没有待采集的URL时，它也会主动向URL 分发器发送URL请求。每个Spider的任务就是将信息服务器分配给它的URL按

27、照到来的先 后顺序插入到自己的URL队列中，然后不停的从队首取出URL进行采集，直到自己的URL 队列为空。为了提高进一步的采集效率，在每个Spider 上我们采用了多线程方式。3可扩展Spider使用的关键技术31 相关协议的介绍Internet构建在很多相关的协议基础上，协议（Protocol）是用于两个或多个系统之 间协作通信的方式。该系统的实现是基于In terne t协议之上的，主要有：Socke t套接字 协议，HTTP超文本传输协议，HTTPS超文本传输安全协议，下面就这些协议作介绍。3.1.1 Socket套接字协议“套接字”（Socket）是一种软件形式的抽象，用于表达两台机

28、器间一个连接的“终端”。 针对一个特定的连接，每台机器上都有一个“套接字”，可以想象它们之间有一条虚拟的“线 缆”。套接字不关心数据的格式，它和底层的TCP/IP协议都只需确保数据到达正确的目的 地。套接字的工作很像邮政服务，它们所做的就是将信息分遣到世界各地的计算机系统。Java有非常简单的套接字编程，其中定义有两个类：Socket和ServerSocket，在套 接字程序设计中特别重要。如果编写的程序是扮演服务器的角色，它就应该使用 ServerSocket;如果程序是连接到服务器的，那么它扮演客户端的角色，就应该使用Socket 类。无论是通过子类ServerSocket完成的服务器还是

29、客户端，Socket类只用于最初的开 始连接，一旦连接建立，就使用输入和输出流来促进客户端和服务器之间的通信。连接成 功后，客户端和服务器之间的区别就完全没意义了。任意一端都可以往套接字读写数据。从套接字得到的结果是一个InputStream以及OutputStream （若使用恰当的转换器， 则分别是Reader和Writer），以便将连接作为一个IO流对象对待。一旦客户（程序）申 请建立一个套接字连接，ServerSocket就会返回（通过accept（）方法）一个对应的服务器 端套接字，以便进行直接通信。从此时起，我们就得到了真正的“套接字一套接字”连接, 可以用同样的方式对待连接的两端

30、，因为它们本来就是相同的！此时可以利用 getInputStream（）以及 getOutputStream（）从每个套接字产生对应的InputStream 和OutputStream对象，这些数据流必须封装到缓冲区内。首先，构造客户端套接字。当客户端套接字被第一次实例化时，必须指定两个参数： 连接的主机和将要连接的端口号，例如:其次，如果在连接指定的主机时出现任何错误，Socket构造函数将抛出IOException。 一旦连接成功，就通过Socket.getlnputStream和Socket.getOutputStream方法获得输入 和输出流。例如：J首先，构造服务器套接字。Serve

31、rSocket对象有几个可利用的构造函数，最简单的构造函数仅仅接受程序将要侦听的端口号，例如：trys二new ServerSocket (端 口号 port);catch(Exception e)try语句块是必须要的，因为当程序尝试注册端口号port时，可能会出现不少错误， 导致最常见的错误原因是本机已经有服务器在侦听端口 port。其次，一旦程序成功注册了端口 port,它就可以开始侦听连接了。以下代码是用于等 待连接的：Socket remote=s.accept();通过accept返回的Socket对象正好和客户端套接字使用的是同一个类。一旦连接被 建立，客户端套接字和服务器套接字

32、之间的不同就消失了。客户端套接字和服务器套接字 之间的主要的不同就在于它们的连接方式，客户端套接字连接到其他端，而服务器套接字 等待其他端连接它。3.1.2 HTTP/HTTPS 协议HTTP（Hypertext Transfer Protocol）是建立在TCP/IP网络协议基础上的用于WWW数 据传输的标准协议。通过HTTP协议，搜索引擎与WWW服务器建立通信机制，向服务器提出 对网页各种特征提取的请求，并从服务器的应答中获得相应数据。HTTP协议的通讯包是由头字段和实体两部分组成。头字段用于描述各种信息，实体用 于装载内容息。重要的头字段有HTTP/1.1（版本号）、Server （服务

33、器类型）、Date （获取 时间）、Con ten t_t ype （媒体类型）、Las t-modified （最后修改时间）、Con ten t-leng th （内 容长度）等。了解了 HTTP请求/响应通讯包的构造方法，可以很容易获取网页的内容。HTTPS（Hypertext Transfer Protocol Secure）在许多方面都非常类似 HTTP，由于提 供底层加密协议的安全套接字层（Secure Socket Layer,简称SSL）,才使HTTPS与HTTP有 所区分。一旦数据包被解密，协议的大多数元素都是相同的。3.2 URL地址结构及分类Internet上的位置是通过

34、URL（Uniform Resourse Locator,统一资源定位器）来指定的。 这就是唯一标识Internet上具体资源的地址。例如，服务器上的图像。URL 由 Scheme（模式），Hos tnamej （主机名），Por t（端口），Pa th（路径）和 Anchor（锚点） 组成，其中某些URL的端口号和锚点可以省略URL有绝对和相对之分，绝对URL将指定一个准确的、无歧义的In terne t资源位置。绝对URL包含主机名和文件名。例如：，就是一个绝对的URL：主机名，myfile.html是文 件名。“直接来源于主机”。这意味着它将使用同样的主机名，完全替换其中的主机名。不 以

35、斜杠开始的相对地址，将被简单地连接到正在查看页面所在的目录。3.3 多线程与线程同步多线程是一个程序在同一时刻运行超过一个任务的能力。但多线程不是多任务，二者 区别是：多线程是在一个程序内部，多任务是在一个计算机内部。在实际应用中，基于单线程的系统无法满足我们的需要。当一个应用程序正在下载某 个文件时，我们并不希望它只专注于原来的任务，也许我们还想同时用它来打开已经下载 的多媒体文件或者向它添加新的下载任务，在这个时候，我们要用多线程来打造一个反应 灵敏的用户界面。多线程的另一个作用是用来提高系统的并发性。对于多CPU的PC，多线 程实现了真正的并行，使程序高效的运行。对于单CPU的PC来说，

36、操作系统会自动进行任 务切换，给人的感觉是同时发生的，其实并不是真正的并发。但是一旦这些任务在执行过 程中需要等待，那这种伪并行会在一个任务等待其它资源的时候执行其它任务，以解决程 序中存在的瓶颈问题。例如，一个Spider程序需要下载十个网页，要完成这个任务，Spider程序必须向服 务器发出请求然后接收数据，而Spider程序等待响应是一个平颈。若采用多线程则可提高 效率，因为众多的线程允许这十个网页的等待时间结合在一起，而不是让他们一个接一个 地执行。如果让Spider仅等待一个网页效率是十分底的，多线程能让Spider同时等待大 量的网页。线程一起工作时，不仅必须共享数据，而且还必须知

37、道其它线程的状态和活动。当你 创建了一个多线程时，就相当于建立了一支规定人数的军队。你让他们各自不停地去执行 相同的任务。比如这些军人都是工兵，你给他们下达了排除某地地雷的任务，任务的具体 内容就是：每个人都独立地去发现地雷、排除地雷、作好标记（即多线程）。这些工兵在给 定范围内重复相同的动作，他们之间会协调各自的行为。任何一个工兵都不会在已经排完 雷、作好标记的地区再进行排雷，也不可能几个工兵聚集在同一点上排同一个雷（即线程 同步）。为使Spider程序高效地运行，Spider程序的工作检查众多的网页被分成小的任务，然后把这些任务分给不同的线程。这些线程相互通信以确定获得新的工作，通过线 程

38、同步，各个Spider不会把已经完成的工作当做新的工作。3.4 MD5算法及散列函数实现可扩展Spider的关键之处在于设计一个合理的URL转发器，使得各爬虫能均匀地 分配到属于自己爬行范围的URL。而MD5算法及散列函数的应用是实现URL转发器的关键 所在：3.4.1 MD5算法的用途MD5算法属于众多数字签名算法中的Hash签名算法，是一种加密算法。MD5算法是MD4 的改进算法，它比MD4更复杂，但设计思想相似,输入的消息可任意长，输出结果也仍为128 位（bit）,特别适用于高速软件实现,是基于32-位操作数的一些简单的位操作。该算法的输入是一个字节串，每个字节8个bit。经过补位、附

39、加数据长度、初始化MD5 参数、定义四个MD5基本的按位操作函数以及变换输入数据五个主要步骤后，能将输入的 字符串变换成32位16进制数字的字符串。必须声明的是：本系统采用MD5算法不是处于数据加密的用途，而是利用该算法的特殊 功能来实现将一个个用URL表示的字符串转换成对应的数字字符串，对该字符串做相应处 理后再利用散列函数实现对URL的转发。3.4.2 散列函数的构造法散列函数的应用成功解决了该系统中的一个关键问题-实现对 URL 的均匀转发，其中经常使用的散列函数有：(1) 数字分析法其思想是利用通常情况下关键码位数比存储区的地址码位数多的特点，将关键码的各位进行分析，丢掉分布不均匀的位

40、而留下分布均匀的位作为地址。(2) 除余法其思想是选择一个适当的正整数P,用P去除关键码，余数作为散列地址，即h(key)二key%P。这个方法的关键是选取适当的P。如果P为偶数，则总是把奇数的关键码 转换为奇地址，把偶数的关键码转换为偶地址；如果P是关键码的基数的幂次(对整数关 键码而言，就是取P=10 i),则相当于选择关键码的最后几位数字作为地址，这两情况都不 好。一般P为小于基本区域长度m的最大素比较好。(3) 折叠法如果关键码的位数比地址位数多，且各位分布均匀，不适于用数字分析法，则可以考 虑折叠法。折叠法将关键码从某些地方断开，分为几部分，其中一部分的长度(位数)等 于地址码的长度(位数)，与其它几部分相加，舍弃进位。(4) 中平方法先求出关键码的平方，然后取中间几位作为地址。(5) 基数转换法其思想是把关键码看作是另一个进制的表示，然后再转换成原来进制的数，最后用数字分析法取其中几位作为散地址。一般转换基数大于原基数，且两个基数最好互素。散列函数也称杂凑函数，顾名思义就是拼凑出来的，具体方法很多，在此不可以一一列举，也不存在一种通用的最佳方案。具体问题具体分析是选择散列函数的基本原则。