淺談hashppt課件(存儲(chǔ)版)
【正文】 46,5) h(k)+c 0 1 2 3 4 5 6 7 8 9 10 11 12 54 43 18 46 60 75 90 54 43 18 46 60 75 90 5 A:(18,75,60,43,54,90,46,5) 46 90 18 15 75 43 60 5 15 1 1 11 1 1 1 1 1 1 Record, key link r:=m 哈希表支持的運(yùn)算主要有： 初始化 (makenull)、哈希函數(shù)值的運(yùn)算 (h(x))、插入元素(insert)、查找元素 (member)。 【 例 3】 將一組關(guān)鍵字 (0100， 0110， 1010， 1001， 0111)平方后得 (0010000， 0012100， 1020220， 1002022， 0012321)，若取表長(zhǎng)為 1000，則可取中間的三位數(shù)作為散列地址集： (100， 121， 201， 020， 123)。而素?cái)?shù)的約數(shù)是最少的，因此我們選用大素?cái)?shù)。一般地說(shuō)，如果 m 的約數(shù)越 多，那么沖突的幾率就越大。 我們需要用 O(n)的時(shí)間來(lái)查找某個(gè)元素 也可以定義 a:array[1..1353] of longint 使 a[key]:=key。也就是說(shuō)， [b div a]的值只有 b+1 種可 能，而 m 是一個(gè)預(yù)先確定的數(shù)。 【 例 2】 對(duì)下列關(guān)鍵碼集合（表中左邊一列）進(jìn)行關(guān)鍵碼到地址的轉(zhuǎn)換，要求用三位地址。 一般是先將關(guān)鍵字分割成位數(shù)相同的幾段（最后一段的位數(shù)可少一些），段的位數(shù)取決于散列 地址的位數(shù)，由實(shí)際需要而定，然后將它們的對(duì)應(yīng)位疊加和（舍去最高位進(jìn)位）作為散列地址。 // 用非常大的整數(shù)代表這個(gè)位置沒有存儲(chǔ)元素 p=9997。 我們注意到，插入和查找首先都需要對(duì)這個(gè)元素定位，即如果這個(gè)元素若存在，它應(yīng)該存儲(chǔ)在什么位置，因此加入一個(gè)定位的函數(shù) locate function locate(x:longint):integer。 var posi:integer。 end。 查找元素是否已經(jīng)在表中 procedure member(x:longint):boolean。 while (iS)and(A[(orig+i)mod S]x)and(A[(orig
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1