一、数据结构里的间界叠加

数据结构里的间界叠加是间界叠加：从一端到另一端沿各部分分界来回折叠后，最后一位对齐相加。如：key=2534635870三位一分界。间界叠加：253+364+587+50（即奇数段正序，偶数段反序）。

哈希表定义：也叫散列表。根据设定的哈希函数及处理冲突的方法，将元素存储在一段有限的连续空间中。即存储地址H（key）与关键字key的关系构建。

直接定址法：利用线性函数来设置。H（key）=a*key+b；其中a≠0，b为常数。

举例：统计各年龄段的人口，用直接定址法设定哈希函数。

数字分析法：若关键字是x进制数，且可预知可能出现的所有关键字值，则可以去关键字的若干位构成哈希地址函数。

举例：

平方取中法：若关键字较短，则可以先平方再类似上面，取个别的位数为哈希地址。和上面差不多，就不举例了。

折叠法：分为移位叠加和间界叠加。将关键字值分割成位数相同的几部分，然后取这几部分的叠加和（舍弃进位）作为哈希地址。

1）移位叠加：图书馆编号有0-442-20586-4，即0442205864，按此编号构造哈希地址：将该编号分成三部分，将每四位对齐后叠加，进位舍弃，得出来的数据就是哈希地址。

2）间界叠加：先将低四位写上，再将第二部分倒写对齐，第三部分又与名列前茅部分一样，如此间界的对齐，得出的哈希地址就是间界叠加。

除留余数法：设有一组关键字，试用除留余数法求设计哈希函数。关键字组：（19,14,23,01,68,20,84,27,55,11,10,79,12,39,21）。

可以设置为H(key)=key%13；为什么取13？我们可以假设它取9，得出的余数分别为1 5 5 1 5 2 3 0 1 2 1 7 3 3 3。可以看出1 3 5的余数非常多，当它映射到存储地址时，会更容易的造成冲突。所以我们在选择取余数时，一般取质数，让它的冲突尽可能的少。

延伸阅读：

二、线性结构是什么

简单地说，线性结构是一个数据元素的有序（次序）集合。它有四个基本特征：1）集合中必存在少数的一个“名列前茅个元素”。

2）集合中必存在少数的一个“最后的元素”。

3）除最后元素之外，其它数据元素均有少数的“后继”。

4）除名列前茅元素之外，其它数据元素均有少数的“前驱”。数据结构中线性结构指的是数据元素之间存在着“一对一”的线性关系的数据结构。如（a1,a2,a3,…..,an）,a1 为名列前茅个元素，an 为最后一个元素，此集合即为一个线性结构的集合。

上一篇

数据标签定义是什么?

下一篇

数据结构和算法通常用来做什么?