散列查找 散列表（哈希表）
哈希表的平均查找長度是（）的函數。
A.哈希表的長度
B.哈希表的裝填因子
C.哈希函數
D.表中元素的多少
裝填因子 = 關鍵字個數 / 表長
符號表：是 “名字（Name）–屬性（Attribute）”對的集合
符號表也叫散列表（哈希表）
散列是一種重要的查找方法
它的基本思想是：以數據對象的關鍵字key為自變量，通過一個確定的函數關系h，計算出
對應的函數值h(key)，把這個值解釋為數據對象的存儲地址，并按此存放，即“存儲位置=h(key)”
散列方法中使用的計算函數稱為**“散列函數/哈希函數”**
按這個思想構造的表稱為散列表
散列函數的構造方法：
數字關鍵詞的散列函數構造
- 直接定址法：h(key)=a*key+b
- 除留余數法:h(key)=key mod p
- 數字分析法
字符串關鍵詞的散列函數構造
處理沖突的方法：
開放地址法
線性探測法
沖突發生時，順序查看表中下一單元，直到找出一個空單元或查遍全表
二次探測法
沖突發生時，在表的左右進行跳躍式探測，比較靈活
采用開放定址法處理沖突中的二次探測再散列（也即是題目中的二元探測法）,則哈希函數變為Hash(key） = (Hash(key) + d) % 11，其中d = 12, -12, 22, -22, 32,……，則開始計算。
分離鏈接法
其做法就是將散列到同一個值的所有元素保存到一個表中。
雙散列探測方法
對于使用平方探測的開放定址散列法，當元素填得太滿的時候，操作運行的時間將消耗過長，而且插入操作有可能失敗，此時則可以進行一次再散列來解決這一問題。
再散列會創建一個新的散列表，新的散列表大小為大于原散列表大小2倍的第一個素數，隨后將原散列表的值重新散列至新的散列表中。
假定有K個關鍵字互為同義詞，若用線性探測法把這K個關鍵字存入散列表中，至少要進行多少次探測？
A.K?1
B.K
C.K+1
D.K(K+1)/2
從一個具有N個結點的單鏈表中查找其值等于X的結點時，在查找成功的情況下，需平均比較多少個結點？
A.N/2
B.N
C.(N?1)/2
D.(N+1)/2
由于單鏈表只能進行單向順序查找，以從第一個節點開始查找為例，查找第m個節點需要比較的節點數f(m)=m，查找成功的最好情況是第一次就查找成功，只用比較1個節點，最壞情況則是最后才查找成功，需要比較n個節點。
所以一共有n種情況，平均下來需要比較的節點為(1+2+3+…+(n-1)+n)/n=(n+1)/2。
下面關于哈希查找的說法，不正確的是（ ）。
A.采用鏈地址法處理沖突時，查找一個元素的時間是相同的
B.采用鏈地址法處理沖突時，若插入規定總是在鏈首，則插入任一個元素的時間是相同的
C.用鏈地址法處理沖突，不會引起二次聚集現象
D.用鏈地址法處理沖突，適合表長不確定的情況
總結
以上是生活随笔為你收集整理的散列查找 散列表（哈希表）的全部內容，希望文章能夠幫你解決所遇到的問題。
