【導(dǎo)讀】程當(dāng)中起著承上啟下的作用，其重要性不言而喻。但是，目前許多銀行在具體的。下，而且無(wú)法達(dá)到理想的效果。本文針對(duì)上述問題，采用軟件工程的開發(fā)原理，軟件應(yīng)用、軟件維護(hù)等過程開發(fā)了一個(gè)銀行帳目管理系統(tǒng)?？诹畋?、銀行系統(tǒng)的用戶信息表等數(shù)據(jù)表。解決了銀行系統(tǒng)中存在的數(shù)據(jù)安全性。、數(shù)據(jù)一致性以及系統(tǒng)運(yùn)行速度等問題。取款機(jī)信息管理模塊：管理員管理查詢和維護(hù)、客戶查詢和取款等?？偭肯M(fèi)統(tǒng)計(jì)、工作量負(fù)荷統(tǒng)計(jì)等功能。理的任務(wù)，提高賬目管理效率，使銀行的賬目管理工作系統(tǒng)化、規(guī)范化、自動(dòng)化。各階段分工明確。經(jīng)過實(shí)踐證明，該劃分是合理的，極大得提高了本系統(tǒng)的實(shí)現(xiàn)?，F(xiàn)今，人們的金融意識(shí)、科技意識(shí)己經(jīng)有了很大的提高，

　　

【正文】 如下： 系統(tǒng)功能分析在系統(tǒng)開發(fā)的總體任務(wù)的基礎(chǔ)上完成。本系統(tǒng)實(shí)現(xiàn)的主要功能模塊如下 : （ 1） 帳戶管理 本模塊的功能在于管理員通過簡(jiǎn)單的操作，可以實(shí)現(xiàn)銀行對(duì)賬戶管理一般功能。如：存款、取款、開戶、銷戶、修改信息、辦卡和掛失卡等等，內(nèi)容豐富 . （ 2） 取款機(jī)管理 本模塊的功能就是模擬 ATM 取款機(jī)的取款過程。具體實(shí)現(xiàn)的功能為：用戶輸 入取款機(jī)號(hào)、卡號(hào)、密碼，通過驗(yàn)證后進(jìn)入交易，用戶可以查看余額，取出現(xiàn)金。系統(tǒng)自動(dòng)更新用戶賬號(hào)及卡號(hào)中的存款余額，并在用戶存取款信息中作記錄，在 ATM 機(jī)的存取款信息中作記錄。 （ 3） 用戶查詢 本模塊的功能就是使用戶查詢自己帳戶的信息。在用戶查詢之前，處于安全的考慮，要進(jìn)行相應(yīng)的驗(yàn)證，以用戶輸入的密碼和數(shù)據(jù)庫(kù)中的原始設(shè)置的密碼相匹配，能夠匹配一致的即可進(jìn)入數(shù)據(jù)庫(kù)中查詢相應(yīng)的信息；匹配不成功的即會(huì)退出此模塊而進(jìn)入主模塊界面，以防止使用者對(duì)數(shù)據(jù)庫(kù)的非法修改。 （ 4） 查詢統(tǒng)計(jì) 本模塊主要實(shí)現(xiàn)以下五項(xiàng)功能： ① 金牌用戶統(tǒng)計(jì)： 統(tǒng)計(jì)持卡消費(fèi)頻率達(dá)到某一標(biāo)準(zhǔn)的用戶，如日平均消費(fèi)次數(shù)超過一次的。 ② ATM 業(yè)務(wù)量統(tǒng)計(jì)： 統(tǒng)計(jì)每臺(tái) ATM 機(jī)的刷卡次數(shù)，根據(jù)次數(shù)可以讓銀行根據(jù) ATM 地點(diǎn)的分布考慮如何合理安排。 ③ 異動(dòng)查詢： 統(tǒng)計(jì)在短期內(nèi)某帳戶大進(jìn)大出的情況，發(fā)現(xiàn)異常，則提供帳戶的監(jiān)管。 ④ 持卡總量消費(fèi)統(tǒng)計(jì)： 統(tǒng)計(jì)某時(shí)段內(nèi)持卡消費(fèi)的總次數(shù)的變化情況，可以畫出條形圖、餅形圖，提供宏觀的分析。 ⑤ 提供操作員的工作負(fù)荷統(tǒng)計(jì)，每個(gè)操作員的日工作量，以次確定操作員的 業(yè)績(jī)，進(jìn)行考核。 算法及數(shù)據(jù)結(jié)構(gòu) 哈希查找 本文主要采用了 DES 加密算法和哈希算法， DES算法我們已經(jīng)在第二章作過詳細(xì)介紹，就不再贅述，我們?cè)诖酥粚?duì)哈希查找作詳細(xì)的介紹。 什么是哈希表 較主要的查找方法有順序、折半、二叉樹查找等，但是，這一類查找方法建立在“比較”的基礎(chǔ)上。在順序查找時(shí)，比較的結(jié)果為“ =”與“≠”兩種可能；在折半查找、二叉排序樹查找和 B樹查找時(shí)，比較的結(jié)果為“＜”、“ =”、“＞”三種可能。查找的效率依賴于查找過程中 所進(jìn)行的比較次數(shù)。 理想的情況是希望不經(jīng)過任何比較，一次存取便能得到所查記錄，那就必須在記錄的存儲(chǔ)位置和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系 f，使每個(gè)關(guān)鍵字和結(jié)構(gòu)中一個(gè)唯一的存儲(chǔ)位置相對(duì)應(yīng)。因而在查找時(shí)，只要根據(jù)這個(gè)對(duì)應(yīng) f找到給定值 K 的像 f（ K）。若結(jié)構(gòu)中存在關(guān)鍵字和 K相等的記錄，則必定在 f（ K）的存儲(chǔ)位置上，由此，不需要進(jìn)行比較便可直接取得所查記錄。我們稱這個(gè)對(duì)應(yīng)關(guān)系 f 為哈希（ Hash）函數(shù)，按這個(gè)思想建立的表為哈希表。 （ 1） 哈希函數(shù)是一個(gè)映象，因此哈希函數(shù)的設(shè)定很靈活，只要使得任何關(guān)鍵字由此所得的哈希函數(shù)值 都落在表長(zhǎng)允許的范圍之內(nèi)即可。 （ 2） 對(duì)不同的關(guān)鍵字可能得到同一哈希地址，這種現(xiàn)象稱為沖突。在一般情況下，沖突只能盡可能地少，而不能完全避免。因?yàn)?，哈希函?shù)是從關(guān)鍵字集合到地址集合的映象。通常，關(guān)鍵字集合比較大，它的元素包括所有可能的關(guān)鍵字，而地址集合的元素僅為哈希表中的地址值。因此，在一般情況下，哈希函數(shù)是一個(gè)壓縮映象，這就不可避免產(chǎn)生沖突。因此，在建造哈希表時(shí)不僅要設(shè)定一個(gè)“好”的哈希函數(shù)，而且要設(shè)定一種處理沖突的方法。 綜上所述，可如下描述哈希表：根據(jù)設(shè)定的哈希函數(shù) H（ key）和處理沖突的方法將一組關(guān)鍵字映 象到一個(gè)有限的連續(xù)的地址集（區(qū)間）上，并以關(guān)鍵字在地址集中的“象”作為記錄在表中的存儲(chǔ)位置，這種表便稱為哈希表，這一映象過程稱為哈希造表或散列，所得存儲(chǔ)位置稱哈希地址或散列地址。 哈希函數(shù)的構(gòu)造方法 若對(duì)于關(guān)鍵字集合中的任一個(gè)關(guān)鍵字，經(jīng)哈希函數(shù)映象到地址集合中任何一個(gè)地址的概率是相等的，則成此類哈希函數(shù)為均勻的哈希函數(shù)。換句話說(shuō)，就是使關(guān)鍵字經(jīng)過哈希函數(shù)得到一個(gè)“隨即的地址”，以便使一組關(guān)鍵字的哈希地址均勻分布在整個(gè)地址區(qū)間中，從而減少?zèng)_突。 常用的構(gòu)造哈希函數(shù)的方法有： （ 1） 直接定址法 取關(guān) 鍵字或關(guān)鍵字的某個(gè)線性函數(shù)值為哈希地址。即： H（ key） =key 或 H（ key） =a*key＋ b 其中， a和 b為常數(shù)（這種哈希函數(shù)叫做自身函數(shù)）。 由于直接定址所得地址集合和關(guān)鍵字集合的大小相同，因此，對(duì)于不同的關(guān)鍵字不會(huì)發(fā)生沖突。但實(shí)際中能使用這種哈希函數(shù)的情況很少。 （ 2） 數(shù)字分析法 假設(shè)關(guān)鍵字是以 r 為基的數(shù)（如：以 10為基的十進(jìn)制數(shù)），并且哈希表中可能出現(xiàn)的關(guān)鍵字都是事先知道的，則可取關(guān)鍵字的若干數(shù)位組成哈希地址。 例如，有 80 個(gè)記錄，其關(guān)鍵字為 8 位十進(jìn)制數(shù)。假設(shè)哈希表的表長(zhǎng)為10010，則可取兩位十 進(jìn)制數(shù)組成哈希地址。取哪兩位？原則是使得到的哈希地址盡量避免產(chǎn)生沖突，則需從分析這 80 個(gè)關(guān)鍵字著手。假設(shè)這 80個(gè)關(guān)鍵字中的一部分如下所列： ?? 8 1 3 4 6 5 3 2 8 1 3 7 2 2 4 2 8 1 3 8 7 4 2 2 8 1 3 0 1 3 6 7 8 1 3 2 2 8 1 7 8 1 3 3 8 9 6 7 8 1 3 5 4 1 5 7 8 1 3 6 8 5 3 7 8 1 4 1 9 3 5 5 ?? ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ 對(duì)關(guān)鍵字全體的分析中我們發(fā)現(xiàn)：第①②位都是“ 8 1”，第③位只可能取 3 或 4，第⑧位只可能取 5 或 7，因此這四位都不可取。由于中間的四位可看成是近乎隨機(jī)的，因此可取其中任意兩位，或取其中兩位與另外兩位的疊加求和后舍去進(jìn)位作為哈希地址。 （ 3） 平方取中法 取關(guān)鍵字平方后的中間幾位為哈希地址。這是一種較常用的構(gòu)造哈希函數(shù)的方法。通常在選定哈希函數(shù)時(shí)不一定能知道關(guān)鍵字的全部情 況，取其中哪幾位也不一定合適，而一個(gè)數(shù)平方后的中間幾位數(shù)和數(shù)的每一位都有關(guān)，由此使隨機(jī)分布的關(guān)鍵字得到的哈希地址也是隨機(jī)的。取的位數(shù)由表長(zhǎng)決定。 （ 4） 折疊法 將關(guān)鍵字分割成位數(shù)相同的幾部分（最后一部分的位數(shù)可以不同），然后取這幾部分的疊加和（舍去進(jìn)位）作為哈希地址，這種方法稱為折疊法。 （ 5） 除留余數(shù)法 取關(guān)鍵字被某個(gè)不大于哈希表長(zhǎng) m的數(shù) p 除后所得余數(shù)為哈希地址。即 H（ key） =key MOD p P≤ m 這是一種最簡(jiǎn)單，也最常用的構(gòu)造哈希函數(shù)的方法。它不僅可以對(duì)關(guān)鍵字直接取模（ MOD），也可在折疊、平方取中等運(yùn)算之后取模。 （ 6） 隨機(jī)數(shù)法 選擇一個(gè)隨機(jī)函數(shù)，取關(guān)鍵字的隨機(jī)函數(shù)值為它的哈希地址，即 H（ key）=random(key)，其中 random 為隨機(jī)函數(shù)。通常，當(dāng)關(guān)鍵字長(zhǎng)度不等時(shí)采用此法構(gòu)造哈希函數(shù)較恰當(dāng)。 實(shí)際工作中需視不同的情況采用不同的哈希函數(shù)。通常，考慮的因素有： （ 1） 計(jì)算哈希函數(shù)所需時(shí)間（包括硬件指令的因素）； （ 2） 關(guān)鍵字的長(zhǎng)度； （ 3） 哈希表的大??； （ 4） 關(guān)鍵字的分布情況； （ 5） 記錄的查找頻率。 處理沖突的方法 “處理沖突”就是為該關(guān)鍵字的記錄找到另一個(gè)“空”的哈 希地址。通常用的處理沖突的方法有： （ 1） 開放定址法 Hi=（ H（ key）＋ di） MOD m i=1， 2，?， k （ k≤ m－ 1） 其中， H（ key）為哈希函數(shù)； m為表長(zhǎng)； di為增量序列，可有下列三種取法： di=1， 2， 3，?， m－ 1，稱線性探測(cè)再散列； di=12，－ 12， 22，－ 22， 32，?，177。 k2，（ k≤ m/2），稱二次探測(cè)再散列； di=偽隨機(jī)序列，稱偽隨機(jī)探測(cè)再散列。 （ 2） 再哈希法 Hi=RHi（ key） i=1， 2，?， k RHi 均是不的哈希函數(shù)，即在同義詞產(chǎn)生地址沖突時(shí)計(jì)算另一個(gè) 哈希函數(shù)地址，直到?jīng)_突不再發(fā)生。這種方法不易產(chǎn)生“聚集”但增加了計(jì)算的時(shí)間。 （ 3） 鏈地址法 將所有關(guān)鍵字為同義詞的記錄存儲(chǔ)在同一線性鏈表中。假設(shè)某哈希函數(shù)產(chǎn)生的哈希地址在區(qū)間 [0， m－ 1]上，則設(shè)立一個(gè)指針型向量 chainhash:ARRAY[0..m－ 1] OF pointer； 其每個(gè)分量的初始狀態(tài)都是空指針。凡哈希地址為 i 的記錄都插入到頭指針為 chainhash[i]的鏈表中。在鏈表中的插入位置可以在表頭或表尾；也可以在中間，以保持同義詞在同一線性鏈表中按關(guān)鍵字有序。 （ 4） 建立一個(gè)公共溢出區(qū) 這也是處 理沖突的一種方法。假設(shè)哈希函數(shù)的值域?yàn)?[0， m－ 1]，設(shè)向量hashtable（ 0: m－ 1）為基本表，每個(gè)分量存放一個(gè)記錄，另設(shè)立向量overtable[0:v]為溢出表。所有關(guān)鍵字和基本表中關(guān)鍵字為同義詞的記錄，不管它們由哈希函數(shù)得到的哈希地址是什么，一旦發(fā)生沖突，都填入溢出表。 哈希表的查找及其分析 在哈希表上進(jìn)行查找的過程和哈希造表的過程基本一致。給定 K值，根據(jù)造表時(shí)設(shè)定的哈希函數(shù)求得哈希地址，若表中此位置上沒有記錄，則查找不成功；否則比較關(guān)鍵字，若和給定值相等，則查找成功；否則根據(jù)造表 時(shí)設(shè)定的處理沖突的方法找“下一地址”，直至哈希表中某個(gè)位置為“空”或者表中所填記錄的關(guān)鍵字等于給定值為止。 算法 為以開放定址等（除鏈地址法外）方法處理沖突的哈希表的查找過程（不考慮插入和刪除）。 例 已知上例中所示的一組關(guān)鍵字按哈希函數(shù) H（ key） =key MOD 13 和線性探測(cè)處理沖突構(gòu)造所的哈希表 a(0..15) 如圖 所示。 給定值 K=84 的查找過程為：首先求得哈希地址 H（ 84） =6，因 ??6a 不空且? ? 846 ??keya ,則 找第一次沖突處理后的地址 716)16(1 ??? M ODH ，而 ? ?7a 不空且 ? ? ?keya ，則找第二次沖突處理后的地址 816)26(2 ??? M ODH ， ??8a 不空且 ? ? ?keya ，則查找成功，返回記錄在表中序號(hào) 8。 給定值 K=38 的查找過程為：先求哈希地址 H（ 38） =12， ? ?12a 不空且? ? ?keya ，則找下一地址 1316)112(1 ??? M O DH ，由于 ??13a 是空記錄，則表明表中不存在關(guān)鍵字等于 38的記錄。 從哈希表的查找過程可見 ： 1）雖然哈希表在關(guān)鍵字與記錄的存儲(chǔ)位置之間建立了直接映象，但由于“沖突”的產(chǎn)生，使得哈希表的查找過程仍然是一個(gè)給定值和關(guān)鍵字進(jìn)行比較的過程。因此，仍需以平均查找長(zhǎng)度作為衡量哈希表的查找效率的量度。 2）查找過程中需和給定值進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)取決于下列三個(gè)因素：哈希函數(shù)，處理沖突的方法和哈息表 的裝填因子。 哈希函數(shù)的“好壞”首先影響出現(xiàn)沖突的頻繁程度。但是，對(duì)于“均勻的”哈希函數(shù)可以假定：不同的哈希函數(shù)對(duì)同一組隨機(jī)的關(guān)鍵字，產(chǎn)生沖突的可能性相同，因?yàn)橐话闱闆r下設(shè)定的哈希函數(shù)是均勻的，則可不考慮它對(duì)平均查找長(zhǎng)度的影響。 對(duì)同樣一組關(guān)鍵字，設(shè)定相同的哈希函數(shù)，則不同的處理沖突的方法得到的哈希表不同，它們的平均查找長(zhǎng)度也不同。如例 93和 94中的兩個(gè)哈希表，在記錄的查找概率相等的前提下，前者（鏈地址法）的平均查找長(zhǎng)度為 )434261(121)12( ???????A SL 后者（線性探測(cè)再散列）的平均查找 長(zhǎng)度為 )9433261(121)12( ????????A SL 容易看出，線性探測(cè)再散列在處理沖突的過程中易產(chǎn)生記錄的二次聚集，如即使得哈希地址不相同的記錄又產(chǎn)生了新的沖突；而鏈地址發(fā)處理沖突不會(huì)發(fā)生類似情況，因?yàn)楣５刂凡煌挠涗浽诓煌逆湵碇小? 在一般情況下，處理沖突方法相同的哈希表，起平均查找長(zhǎng)度依賴于哈希表的裝填因子。 哈希表的裝填因子定義為 ? = 哈希表的長(zhǎng)度表中填入的記錄數(shù) 標(biāo)志哈希表的裝滿程度。直觀地看， ? 越小，發(fā)生沖突的可能性就越?。环粗?， ? 越大，表中已添入的記錄越多，再記錄時(shí)，發(fā)生沖突的可能性就越大，則查找時(shí)，給定值需與之進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)也就越多。 可以證明： 線形探測(cè)再散列的哈希表查找成功的平均查找長(zhǎng)度為 Snl ? 21 ( ???111 ) 隨機(jī)探測(cè)再散列，二次探測(cè)再散列和哈希表查找成功時(shí)的查找平均長(zhǎng)度為 Snr ? ?1 ln(1? ) 鏈地址法處理沖突的哈希表查找成功時(shí)的平均查找長(zhǎng)度為 Snc ? 1 + 2? 由于哈希表在查找 不成功時(shí)所用比較次數(shù)也和給定值有關(guān)，則可以類似的定義哈希表查找不成功時(shí)的平均查找長(zhǎng)度為：查找不成功時(shí)需和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的期望值。同樣可證明，不同的處理沖突方法構(gòu)成的哈希表查找不成功時(shí)的查找長(zhǎng)度分別為： Unl ?