當前位置:首頁 » 服務存儲 » 散列存儲的地址取多少
擴展閱讀
webinf下怎麼引入js 2023-08-31 21:54:13
堡壘機怎麼打開web 2023-08-31 21:54:11

散列存儲的地址取多少

發布時間: 2023-05-21 11:32:23

A. 散列表的平均查找長度怎麼計算

對於含有n個數據元素的查找表,查找成功的平均查找長度為:ASL=∑PiCi (i=1,2,3,…,n),可以簡單以數學上的期望來這么理解。其中:Pi 為查找表中第i個數據元素的概率,Ci為找到第i個數據元素時已經比較過的次數。

在查找表中查找不到待查元素,但是找到待查元素應該在表中存在的位置的平均查找次數稱為查找不成功時的平均查找長度,不成功。

(1)散列存儲的地址取多少擴展閱讀

散列表的查找過程基本上和造表過程相同。一些關鍵碼可通過散列函數轉換的地址直接找到,另一些關鍵碼在散列函數得到的地址上產生了沖突,需要按處理沖突的方法進行查找。在介紹的三種處理沖突的方法中,產生沖突後的查找仍然是給定值與關鍵碼進行比較的過程。所以,對散列表查找效率的量度,依然用平均查找長度來衡量。

查找過程中,關鍵碼的比較次數,取決於產生沖突的多少,產生的沖突少,查找效率就高,產生的沖突多,查找效率就低。因此,影響產生沖突多少的因素,也就是影響查找效率的因素。影響產生沖突多少有以下三個因素:

1、散列函數是否均勻;

2、處理沖突的方法;

3、散列表的裝填因子。

散列表的裝填因子定義為:α= 填入表中的元素個數 / 散列表的長度

α是散列表裝滿程度的標志因子。由於表長是定值,α與「填入表中的元素個數」成正比,所以,α越大,填入表中的元素較多,產生沖突的可能性就越大;α越小,填入表中的元素較少,產生沖突的可能性就越小。

實際上,散列表的平均查找長度是裝填因子α的函數,只是不同處理沖突的方法有不同的函數。

參考資料來源:網路-平均查找長度

參考資料來源:網路-散列表

B. 哈希表詳解

哈希表:即散列存儲結構。
散列法存儲的基本思想:建立記錄關鍵碼字與其存儲位置的對應關系,或者說,由關鍵碼的值決定數據的存儲地址。
這樣,不經過比較,一次存取就能得到所查元素的查找方法
優點:查找速度極快(O(1)),查找效率與元素個數n無關!

哈希方法(雜湊法)
選取某個函數,依該函數按關鍵字計算元素的存儲位置並按此存放;查找時也由同一個函數對給定值k計算地址,將k與地址中內容進行比較,確定查找是否成功。

哈希函數(雜湊函數)
哈希方法中使用的轉換函數稱為哈希函數(雜湊函數).在記錄的關鍵碼與記錄的存儲地址之間建立的一種對應關系

有數據元素序列(14,23,39,9,25,11),若規定每個元素k的存儲地址H(k)=k , H(k)稱為散列函數,畫出存儲結構圖。

根據散列函數H(k)=k ,可知元素14應當存入地址為14的單元,元素23應當存入地址為23的單元,……,

根據存儲時用到的散列函數H(k)表達式,迅即可查到結果!
例如,查找key=9,則訪問H(9)=9號地址,若內容為9則成功;
若查不到,應當設法返回一個特殊值,例如空指針或空記錄。
很顯然這種搜索方式空間效率過低。

哈希函數可寫成:addr(ai)=H(ki)

選取某個函數,依該函數按關鍵字計算元素的存儲位置並按此存放;查找時也由同一個函數對給定值k計算地址,將k與地址中內容進行比較,確定查找是否成功。哈希方法中使用的轉換函數稱為哈希函數(雜湊函數).在記錄的關鍵碼與記錄的存儲地址之間建立的一種對應關系。

通常關鍵碼的集合比哈希地址集合大得多,因而經過哈希函數變換後,可能將不同的關鍵碼映射到同一個哈希地址上,這種現象稱為沖突。

有6個元素的關鍵碼分別為:(14,23,39,9,25,11)。
選取關鍵碼與元素位置間的函數為H(k)=k mod 7

根據哈希函數算出來發現同一個地址放了多個關鍵碼,也就是沖突了。
在哈希查找方法中,沖突是不可能避免的,只能盡可能減少。
所以,哈希方法必須解決以下兩個問題:

1)構造好的哈希函數
(a)所選函數盡可能簡單,以便提高轉換速度;
(b)所選函數對關鍵碼計算出的地址,應在哈希地址內集中並大致均勻分布,以減少空間浪費。

2)制定一個好的解決沖突的方案
查找時,如果從哈希函數計算出的地址中查不到關鍵碼,則應當依據解決沖突的規則,有規律地查詢其它相關單元。

從上面兩個例子可以得出如下結論:
哈希函數只是一種映象,所以哈希函數的設定很靈活,只要使任何關鍵碼的哈希函數值都落在表長允許的范圍之內即可
沖突:key1≠key2,但H(key1)=H(key2)
同義詞:具有相同函數值的兩個關鍵碼
哈希函數沖突不可避免,只能盡量減少。所以,哈希方法解決兩個問題:
構造好的哈希函數;

制定解決沖突基本要求:
要求一:n個數據原僅佔用n個地址,雖然散列查找是以空間換時間,但仍希望散列的地址空間盡量小。
要求二:無論用什麼方法存儲,目的都是盡量均勻地存放元素,以避免沖突。

Hash(key) = a·key + b (a、b為常數)
優點:以關鍵碼key的某個線性函數值為哈希地址,不會產生沖突.
缺點:要佔用連續地址空間,空間效率低。

例.關鍵碼集合為{100,300,500,700,800,900},
選取哈希函數為Hash(key)=key/100,
則存儲結構(哈希表)如下:

Hash(key)=key mod p (p是一個整數)
特點:以關鍵碼除以p的余數作為哈希地址。
關鍵:如何選取合適的p?p選的不好,容易產生同義詞
技巧:若設計的哈希表長為m,則一般取p≤m且為質數
(也可以是合數,但不能包含小於20的質因子)。

Hash(key)= ⎣ B ( A key mod 1 ) ⎦
(A、B均為常數,且0<A<1,B為整數)
特點:以關鍵碼key乘以A,取其小數部分,然後再放大B倍並取整,作為哈希地址。
例:欲以學號最後兩位作為地址,則哈希函數應為:
H(k)=100 (0.01 k % 1 )
其實也可以用法2實現: H(k)=k % 100

特點:選用關鍵字的某幾位組合成哈希地址。選用原則應當是:各種符號在該位上出現的頻率大致相同。
例:有一組(例如80個)關鍵碼,其樣式如下:

討論:
① 第1、2位均是「3和4」,第3位也只有「 7、8、9」,因此,這幾位不能用,餘下四位分布較均勻,可作為哈希地址選用。

② 若哈希地址取兩位(因元素僅80個),則可取這四位中的任意兩位組合成哈希地址,也可以取其中兩位與其它兩位疊加求和後,取低兩位作哈希地址。

特點:對關鍵碼平方後,按哈希表大小,取中間的若干位作為哈希地址。(適於不知道全部關鍵碼情況)
理由:因為中間幾位與數據的每一位都相關。
例:2589的平方值為6702921,可以取中間的029為地址。

特點:將關鍵碼自左到右分成位數相等的幾部分(最後一部分位數可以短些),然後將這幾部分疊加求和,並按哈希表表長,取後幾位作為哈希地址。
適用於:關鍵碼位數很多,且每一位上各符號出現概率大致相同的情況。
法1:移位法 ── 將各部分的最後一位對齊相加。
法2:間界疊加法──從一端向另一端沿分割界來回折疊後,最後一位對齊相加。
例:元素42751896,
用法1: 427+518+96=1041
用法2: 427 518 96—> 724+518+69 =1311

7、隨機數法
Hash(key) = random ( key ) (random為偽隨機函數)
適用於:關鍵字長度不等的情況。造表和查找都很方便。

小結:構造哈希函數的原則:
① 執行速度(即計算哈希函數所需時間);
② 關鍵字的長度;
③ 哈希表的大小;
④ 關鍵字的分布情況;
⑤ 查找頻率。

設計思路:有沖突時就去尋找下一個空的哈希地址,只要哈希表足夠大,空的哈希地址總能找到,並將數據元素存入。
1)線性探測法
Hi=(Hash(key)+di) mod m ( 1≤i < m )
其中:
Hash(key)為哈希函數
m為哈希表長度
di 為增量序列 1,2,…m-1,且di=i

關鍵碼集為 {47,7,29,11,16,92,22,8,3},
設:哈希表表長為m=11;
哈希函數為Hash(key)=key mod 11;
擬用線性探測法處理沖突。建哈希表如下:

解釋:
① 47、7是由哈希函數得到的沒有沖突的哈希地址;
② Hash(29)=7,哈希地址有沖突,需尋找下一個空的哈希地址:由H1=(Hash(29)+1) mod 11=8,哈希地址8為空,因此將29存入。
③ 另外,22、8、3同樣在哈希地址上有沖突,也是由H1找到空的哈希地址的。
其中3 還連續移動了(二次聚集)

線性探測法的優點:只要哈希表未被填滿,保證能找到一個空地址單元存放有沖突的元素;
線性探測法的缺點:可能使第i個哈希地址的同義詞存入第i+1個哈希地址,這樣本應存入第i+1個哈希地址的元素變成了第i+2個哈希地址的同義詞,……,
因此,可能出現很多元素在相鄰的哈希地址上「堆積」起來,大大降低了查找效率。
解決方案:可採用二次探測法或偽隨機探測法,以改善「堆積」問題。

2) 二次探測法
仍舉上例,改用二次探測法處理沖突,建表如下:
Hi=(Hash(key)±di) mod m
其中:Hash(key)為哈希函數
m為哈希表長度,m要求是某個4k+3的質數;
di為增量序列 1^2,-1 ^2,2 ^2,-2 ^2,…,q ^2

註:只有3這個關鍵碼的沖突處理與上例不同,
Hash(3)=3,哈希地址上沖突,由
H1=(Hash(3)+1 ^2) mod 11=4,仍然沖突;
H2=(Hash(3)-1 ^2) mod 11=2,找到空的哈希地址,存入。

3) 若di=偽隨機序列,就稱為偽隨機探測法

基本思想:將具有相同哈希地址的記錄(所有關鍵碼為同義詞)鏈成一個單鏈表,m個哈希地址就設m個單鏈表,然後用一個數組將m個單鏈表的表頭指針存儲起來,形成一個動態的結構。

設{ 47, 7, 29, 11, 16, 92, 22, 8, 3, 50, 37, 89 }的哈希函數為:
Hash(key)=key mod 11,
用拉鏈法處理沖突,則建表如圖所示。

Hi=RHi(key) i=1, 2, …,k
RHi均是不同的哈希函數,當產生沖突時就計算另一個哈希函數,直到沖突不再發生。
優點:不易產生聚集;
缺點:增加了計算時間。

思路:除設立哈希基本表外,另設立一個溢出向量表。
所有關鍵字和基本表中關鍵字為同義詞的記錄,不管它們由哈希函數得到的地址是什麼,一旦發生沖突,都填入溢出表。

明確:散列函數沒有「萬能」通式(雜湊法),要根據元素集合的特性而分別構造。
討論:哈希查找的速度是否為真正的O(1)?
不是。由於沖突的產生,使得哈希表的查找過程仍然要進行比較,仍然要以平均查找長度ASL來衡量。
一般地,ASL依賴於哈希表的裝填因子α,它標志著哈希表的裝滿程度。

0≤α≤1
α 越大,表中記錄數越多,說明表裝得越滿,發生沖突的可能性就越大,查找時比較次數就越多。

例 已知一組關鍵字(19,14,23,1,68,20,84,27,55,11,10,79)
哈希函數為:H(key)=key MOD 13, 哈希表長為m=16,
設每個記錄的查找概率相等
(1) 用線性探測再散列處理沖突,即Hi=(H(key)+di) MOD m

(2) 用二次探測再散列處理沖突,即Hi=(H(key)+di) MOD m

(3) 用鏈地址法處理沖突

1) 散列存儲的查找效率到底是多少?
答:ASL與裝填因子α有關!既不是嚴格的O(1),也不是O(n)
2)「沖突」是不是特別討厭?
答:不一定!正因為有沖突,使得文件加密後無法破譯!(單向散列函數不可逆,常用於數字簽名和間接加密)。
利用了哈希表性質:源文件稍稍改動,會導致哈希表變動很大。

C. 關於散列表,散列函數的兩個問題。

散列表是一種數據結構,通過散列函數(也就是 hash 函數)將輸入映射到一個數字,一般用映射出的數字作為存儲位置的索引。數組在查找時效率很高,但是插入和刪除卻很低。而鏈表剛好反過來。設計合理的散列函數可以集成鏈表和數組的優點,在查找、插入、刪除時實現 O(1) 的效率。散列表的存儲結構使用的也是數組加鏈表。執行效率對比可以看下圖 1.3:

散列表的主要特點:

  1. 將輸入映射到數字

    2.不同的輸入產生不同的輸出

    3.相同的輸入產生相同的輸出

    4. 當填裝因子超過閾值時,能自動擴展。填裝因子 = 散列表包含的元素數 / 位置總數,當填裝因子 =1,即散列表滿的時候,就需要調整散列表的長度,自動擴展的方式是:申請一塊舊存儲容量 X 擴容系數的新內存地址,然後把原內存地址的值通過其中的 key 再次使用 hash 函數計算存儲位置,拷貝到新申請的地址。

    5. 值呈均勻分布。這里的均勻指水平方向的,即數組維度的。如果多個值被映射到同一個位置,就產生了沖突,需要用鏈表來存儲多個沖突的鍵值。極端情況是極限沖突,這與一開始就將所有元素存儲到一個鏈表中一樣。這時候查找性能將變為最差的 O(n),如果水平方向填充因子很小,但某些節點下的鏈表又很長,那值的均勻性就比較差。

D. 散列儲存(hash儲存)的理解

設要存儲對象的個數為num, 那麼我們就用len個內存單元來存儲它們(len>=num); 以每個對象ki的關鍵字為自變數,用一個函數h(ki)來映射出ki的內存地址,也就是ki的下標,將ki對象的元素內容全部存入這個地址中就行了。這個就是Hash的基本思路。
為什麼要用一個函數來映射出它們的地址單元呢?
假設現在我要存儲 4個元素 13 7 14 11
顯然,我們可以用 數組 來存。也就是: a[1] = 13; a[2] = 7; a[3] = 14; a[4] = 11 ;
當然,我們也可以用Hash來存。下面給出一個簡單的 Hash存儲
先來確定那個函數。我們就用 h(ki) = ki%5 ;
對於第一個元素 h(13) = 13%5 = 3 ; 也就是說 13 的下標為 3 ;即 Hash[3] = 13 ;
對於第二個元素 h(7) = 7 % 5 = 2 ; 也就是說譽橡 7 的下標為 2 ; 即 Hash[2] = 7 ;
同理, Hash[4] = 14; Hash[1] = 11 ;
現在我要你查找 11 這個元素是否存在。你會怎麼做呢?當然,對於數組來說,那是相當的簡單,一個for循環就可以辯虛御了。
也就是說我們要找4次。
下面我們來用Hash找一下。
首先,我們攜岩將要找的元素 11 代入剛才的函數中來映射出它所在的地址單元。也就是 h(11) = 11%5 = 1 了。下面我們來比較一下 Hash[1]?=11 , 這個問題就很簡單了。也就是說我們就找了1次。這個就是Hash的妙處了,通過制定一個規則(函數)來映射出它的地址,數據也就能通過這個規則去找到它的內存地址了。

E. 數據結構的存儲方式有哪幾種

數據結構的存儲方式有順序存儲方法、鏈接存儲方法、索引存儲方法和散列存儲方法這四種。

1、順序存儲方式:順序存儲方式就是在一塊連續的存儲區域一個接著一個的存放數據,把邏輯上相連的結點存儲在物理位置上相鄰的存儲單元里,結點間的邏輯關系由存儲單元的鄰接掛安息來體現。順序存儲方式也稱為順序存儲結構,一般採用數組或者結構數組來描述。

2、鏈接存儲方法:它比較靈活,其不要求邏輯上相鄰的結點在物理位置上相鄰,結點間的邏輯關系由附加的引用欄位表示。一個結點的引用欄位往往指導下一個結點的存放位置。鏈接存儲方式也稱為鏈接式存儲結構,一般在原數據項中增加應用類型來表示結點之間的位置關系。

3、索引存儲方法:除建立存儲結點信息外,還建立附加的索引表來標識結點的地址。它細分為兩類:稠密索引:每個結點在索引表中都有一個索引項,索引項的地址指示結點所在的的存儲位置;稀疏索引:一組結點在索引表中只對應一個索引項,索引項的地址指示一組結點的起始存儲位置。

4、散列存儲方法:就是根據結點的關鍵字直接計算出該結點的存儲地址。

(5)散列存儲的地址取多少擴展閱讀

順序存儲和鏈接存儲的基本原理

在順序存儲中,每個存儲空間含有所存元素本身的信息,元素之間的邏輯關系是通過數組下標位置簡單計算出來的線性表的順序存儲,若一個元素存儲在對應數組中的下標位置為i,則它的前驅元素在對應數組中的下標位置為i-1,它的後繼元素在對應數組中的下標位置為i+1。

在鏈式存儲結構中,存儲結點不僅含有所存元素本身的信息,還含有元素之間邏輯關系的信息。數據的鏈式存儲結構可用鏈接表來表示。其中data表示值域,用來存儲節點的數值部分。Pl,p2,…,Pill(1n≥1)均為指針域,每個指針域為其對應的後繼元素或前驅元素所在結點的存儲位置。

在數據的順序存儲中,由於每個元素的存儲位置都可以通過簡單計算得到,所以訪問元素的時間都相同;而在數據的鏈接存儲中,由於每個元素的存儲位置保存在它的前驅或後繼結點中,所以只有當訪問到其前驅結點或後繼結點後才能夠按指針訪問到,訪問任一元素的時間與該元素結點在鏈式存儲結構中的位置有關。

F. 數據結構 哈希表建立

國防部和發簡訊