本文根據(jù)《大話數(shù)據(jù)結構》一書，實現(xiàn)了Java版的一個簡單的散列表（哈希表）。

基本概念

對關鍵字key，將其值存放在f(key)的存儲位置上。由此，在查找時不需比較，只需計算出f(key)便可直接取得所查記錄。這個函數(shù) f() 就叫做散列函數(shù)，按這個思想建立的表稱為散列表。

散列技術即是一種存儲方法，又是一種查找方法：

　　存儲過程：根據(jù)關鍵字key，算出f(key)，將記錄存放在f(key)的位置上；

　　查找過程：根據(jù)關鍵字key，算出f(key)，該位置上的值即為要找的記錄。

?

散列函數(shù)的構造方法

直接定址法

直接取關鍵字的線性函數(shù)為散列地址：f(key)=a×key+b（a，b為常數(shù)）

如：對下表的記錄，關鍵字key取為出生年份，令f(key)=key-1980即可。

數(shù)字分析法

分析一組數(shù)據(jù)，找出其規(guī)律，盡可能利用這些數(shù)據(jù)來構造沖突幾率較低的散列地址

如：以員工的手機號碼作為關鍵字，前7位數(shù)字基本相同，可以選擇后面四位數(shù)字作為散列地址。

平方取中法

當無法確定關鍵字中哪幾位分布較均勻時，可以先求出關鍵字的平方值，然后按需要取平方值的中間幾位作為散列地址。

折疊法

將關鍵字分割成位數(shù)相同的幾部分，最后一部分位數(shù)可以不同，然后取這幾部分的疊加和（去除進位）作為散列地址。

除留余數(shù)法

最為常用的方法，取關鍵字被某個不大于散列表表長m的數(shù)p除后所得的余數(shù)為散列地址。

f(key) = key MOD p,p<=m。

隨機數(shù)法

?選擇一隨機函數(shù)（偽隨機），取關鍵字的隨機值作為散列地址，通常用于關鍵字長度不同的場合。

?

處理散列沖突的方法

當兩個關鍵字key1和key2不同時，有f(key1)=f(key2)，這種現(xiàn)象稱為沖突。一般情況下，我們會盡量設計恰當?shù)纳⒘泻瘮?shù)減少沖突，但無法完全避免，這就需要對沖突進行處理。

開放尋址法

一旦發(fā)生沖突，就去尋找下一個空的散列地址，只要散列表足夠大，空的散列地址總能找到，并將記錄存入。根據(jù)下一個位置的不同，又可分為以下三種：

①線性探測法：

②二次探測法

③隨機探測法

再散列函數(shù)法

在同義詞產(chǎn)生地址沖突時計算另一個散列函數(shù)地址，直到?jīng)_突不再發(fā)生，這種方法不易產(chǎn)生“聚集”，但增加了計算時間。如下圖所示（RHi代表不同的散列函數(shù)）：

?

鏈地址法

相同地址的記錄存放在一個單鏈表中，散列表值存儲所有同義詞子表的頭指針。如下圖所示：

公共溢出區(qū)法

為所有沖突的關鍵字建立一個公共的溢出區(qū)來存放。

?

代碼實現(xiàn)

接下來建立一個簡單的散列表，其散列函數(shù)采用上述的除留余數(shù)法，處理沖突的方法采用開放定址法下的線性探測法。

Java代碼如下：

package HashTable;/*** 散列表* @author Yongh**/ public class HashTable {int[] elem;int count;private static final int Nullkey = -32768;public HashTable(int count) {this.count = count;elem = new int[count];for (int i = 0; i < count; i++) {elem[i] = Nullkey; // 代表位置為空}}/** 散列函數(shù)*/public int hash(int key) {return key % count; // 除留余數(shù)法}/** 插入操作*/public void insert(int key) {int addr = hash(key); // 求散列地址while (elem[addr] != Nullkey) { // 位置非空，有沖突addr = (addr + 1) % count; // 開放地址法的線性探測}elem[addr] = key;}/** 查找操作*/public boolean search(int key) {int addr = hash(key); // 求散列地址while (elem[addr] != key) {addr = (addr + 1) % count; // 開放地址法的線性探測if (addr == hash(key) || elem[addr] == Nullkey) { // 循環(huán)回到原點或者到了空地址System.out.println("要查找的記錄不存在！");return false;}}System.out.println("存在記錄:" + key + ",位置為：" + addr);return true;}public static void main(String[] args) {int[] arr = { 12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34 };HashTable aTable = new HashTable(arr.length);for (int a : arr) {aTable.insert(a);}for (int a : arr) {aTable.search(a);}} }

　　

存在記錄:12,位置為：0 存在記錄:67,位置為：7 存在記錄:56,位置為：8 存在記錄:16,位置為：4 存在記錄:25,位置為：1 存在記錄:37,位置為：2 存在記錄:22,位置為：10 存在記錄:29,位置為：5 存在記錄:15,位置為：3 存在記錄:47,位置為：11 存在記錄:48,位置為：6 存在記錄:34,位置為：9 HashTable

　　代碼中重點可以看：插入操作是如何處理沖突 以及查找操作是如何判斷記錄是否存在的。

?

轉載于:https://www.cnblogs.com/yongh/p/9284896.html

總結

以上是生活随笔為你收集整理的【Java】 大话数据结构(13) 查找算法(4) （散列表（哈希表））的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。