一、數(shù)據(jù)結(jié)構(gòu)里的間界疊加

數(shù)據(jù)結(jié)構(gòu)里的間界疊加是間界疊加：從一端到另一端沿各部分分界來回折疊后，最后一位對(duì)齊相加。如：key=2534635870三位一分界。間界疊加：253+364+587+50（即奇數(shù)段正序，偶數(shù)段反序）。

哈希表定義：也叫散列表。根據(jù)設(shè)定的哈希函數(shù)及處理沖突的方法，將元素存儲(chǔ)在一段有限的連續(xù)空間中。即存儲(chǔ)地址H（key）與關(guān)鍵字key的關(guān)系構(gòu)建。

直接定址法：利用線性函數(shù)來設(shè)置。H（key）=a*key+b；其中a≠0，b為常數(shù)。

舉例：統(tǒng)計(jì)各年齡段的人口，用直接定址法設(shè)定哈希函數(shù)。

數(shù)字分析法：若關(guān)鍵字是x進(jìn)制數(shù)，且可預(yù)知可能出現(xiàn)的所有關(guān)鍵字值，則可以去關(guān)鍵字的若干位構(gòu)成哈希地址函數(shù)。

舉例：

平方取中法：若關(guān)鍵字較短，則可以先平方再類似上面，取個(gè)別的位數(shù)為哈希地址。和上面差不多，就不舉例了。

折疊法：分為移位疊加和間界疊加。將關(guān)鍵字值分割成位數(shù)相同的幾部分，然后取這幾部分的疊加和（舍棄進(jìn)位）作為哈希地址。

1）移位疊加：圖書館編號(hào)有0-442-20586-4，即0442205864，按此編號(hào)構(gòu)造哈希地址：將該編號(hào)分成三部分，將每四位對(duì)齊后疊加，進(jìn)位舍棄，得出來的數(shù)據(jù)就是哈希地址。

2）間界疊加：先將低四位寫上，再將第二部分倒寫對(duì)齊，第三部分又與名列前茅部分一樣，如此間界的對(duì)齊，得出的哈希地址就是間界疊加。

除留余數(shù)法：設(shè)有一組關(guān)鍵字，試用除留余數(shù)法求設(shè)計(jì)哈希函數(shù)。關(guān)鍵字組：（19,14,23,01,68,20,84,27,55,11,10,79,12,39,21）。

可以設(shè)置為H(key)=key%13；為什么取13？我們可以假設(shè)它取9，得出的余數(shù)分別為1 5 5 1 5 2 3 0 1 2 1 7 3 3 3。可以看出1 3 5的余數(shù)非常多，當(dāng)它映射到存儲(chǔ)地址時(shí)，會(huì)更容易的造成沖突。所以我們?cè)谶x擇取余數(shù)時(shí)，一般取質(zhì)數(shù)，讓它的沖突盡可能的少。

延伸閱讀：

二、線性結(jié)構(gòu)是什么

簡單地說，線性結(jié)構(gòu)是一個(gè)數(shù)據(jù)元素的有序（次序）集合。它有四個(gè)基本特征：1）集合中必存在少數(shù)的一個(gè)“名列前茅個(gè)元素”。

2）集合中必存在少數(shù)的一個(gè)“最后的元素”。

3）除最后元素之外，其它數(shù)據(jù)元素均有少數(shù)的“后繼”。

4）除名列前茅元素之外，其它數(shù)據(jù)元素均有少數(shù)的“前驅(qū)”。數(shù)據(jù)結(jié)構(gòu)中線性結(jié)構(gòu)指的是數(shù)據(jù)元素之間存在著“一對(duì)一”的線性關(guān)系的數(shù)據(jù)結(jié)構(gòu)。如（a1,a2,a3,…..,an）,a1 為名列前茅個(gè)元素，an 為最后一個(gè)元素，此集合即為一個(gè)線性結(jié)構(gòu)的集合。