網(wǎng)上有很多關于如何查找pos機,詳解哈希表的查找的知識，也有很多人為大家解答關于如何查找pos機的問題，今天pos機之家(www.mxllmx.com)為大家整理了關于這方面的知識，讓我們一起來看下吧!

本文目錄一覽：

1、如何查找pos機

如何查找pos機

哈希表和哈希函數(shù)

在記錄的存儲位置和它的關鍵字之間是建立一個確定的對應關系（映射函數(shù)），使每個關鍵字和一個存儲位置能唯一對應。

這個映射函數(shù)稱為哈希函數(shù)，根據(jù)這個原則建立的表稱為哈希表(Hash Table)，也叫散列表。

以上描述，如果通過數(shù)學形式來描述就是：

若查找關鍵字為 key，則其值存放在 f(key) 的存儲位置上。由此，不需比較便可直接取得所查記錄。

注：哈希查找與線性表查找和樹表查找最大的區(qū)別在于，不用數(shù)值比較。

沖突

若 key1 ≠ key2 ，而 f(key1) = f(key2)，這種情況稱為沖突(Collision)。

根據(jù)哈希函數(shù)f(key)和處理沖突的方法將一組關鍵字映射到一個有限的連續(xù)的地址集（區(qū)間）上，并以關鍵字在地址集中的“像”作為記錄在表中的存儲位置，這一映射過程稱為構(gòu)造哈希表。

構(gòu)造哈希表這個場景就像汽車找停車位，如果車位被人占了，只能找空的地方停。

構(gòu)造哈希表

由以上內(nèi)容可知，哈希查找本身其實不費吹灰之力，問題的關鍵在于如何構(gòu)造哈希表和處理沖突。

常見的構(gòu)造哈希表的方法有 5 種：

（1）直接定址法

說白了，就是小學時學過的一元一次方程。

即 f(key) = a * key + b。其中，a和b 是常數(shù)。

（2）數(shù)字分析法

假設關鍵字是R進制數(shù)（如十進制）。并且哈希表中可能出現(xiàn)的關鍵字都是事先知道的，則可選取關鍵字的若干數(shù)位組成哈希地址。

選取的原則是使得到的哈希地址盡量避免沖突，即所選數(shù)位上的數(shù)字盡可能是隨機的。

（3）平方取中法

取關鍵字平方后的中間幾位為哈希地址。通常在選定哈希函數(shù)時不一定能知道關鍵字的全部情況，僅取其中的幾位為地址不一定合適；

而一個數(shù)平方后的中間幾位數(shù)和數(shù)的每一位都相關， 由此得到的哈希地址隨機性更大。取的位數(shù)由表長決定。

（4）除留余數(shù)法

取關鍵字被某個不大于哈希表表長 m 的數(shù) p 除后所得的余數(shù)為哈希地址。

即 f(key) = key % p (p ≤ m)

這是一種最簡單、最常用的方法，它不僅可以對關鍵字直接取模，也可在折疊、平方取中等運算之后取模。

注意：p的選擇很重要，如果選的不好，容易產(chǎn)生沖突。根據(jù)經(jīng)驗，一般情況下可以選p為素數(shù)。

（5）隨機數(shù)法

選擇一個隨機函數(shù)，取關鍵字的隨機函數(shù)值為它的哈希地址，即 f(key) = random(key)。

通常，在關鍵字長度不等時采用此法構(gòu)造哈希函數(shù)較為恰當。

解決沖突

設計合理的哈希函數(shù)可以減少沖突，但不能完全避免沖突。

所以需要有解決沖突的方法，常見有兩類

（1）開放定址法

如果兩個數(shù)據(jù)元素的哈希值相同，則在哈希表中為后插入的數(shù)據(jù)元素另外選擇一個表項。

當程序查找哈希表時，如果沒有在第一個對應的哈希表項中找到符合查找要求的數(shù)據(jù)元素，程序就會繼續(xù)往后查找，直到找到一個符合查找要求的數(shù)據(jù)元素，或者遇到一個空的表項。

例子

若要將一組關鍵字序列 {1, 9, 25, 11, 12, 35, 17, 29} 存放到哈希表中。

采用除留余數(shù)法構(gòu)造哈希表；采用開放定址法處理沖突。

不妨設選取的p和m為13，由 f(key) = key % 13 可以得到下表。

需要注意的是，在上圖中有兩個關鍵字的探查次數(shù)為 2 ，其他都是1。

這個過程是這樣的：

a. 12 % 13 結(jié)果是12，而它的前面有個 25 ，25 % 13 也是12，存在沖突。

我們使用開放定址法 (12 + 1) % 13 = 0，沒有沖突，完成。

b. 35 % 13 結(jié)果是 9，而它的前面有個 9，9 % 13也是 9，存在沖突。

我們使用開放定址法 (9 + 1) % 13 = 10，沒有沖突，完成。

（2）拉鏈法

將哈希值相同的數(shù)據(jù)元素存放在一個鏈表中，在查找哈希表的過程中，當查找到這個鏈表時，必須采用線性查找方法。

在這種方法中，哈希表中每個單元存放的不再是記錄本身，而是相應同義詞單鏈表的頭指針。

例子

如果對開放定址法例子中提到的序列使用拉鏈法，得到的結(jié)果如下圖所示：

實現(xiàn)一個哈希表

假設要實現(xiàn)一個哈希表，要求

a. 哈希函數(shù)采用除留余數(shù)法，即 f(key) = key % p (p ≤ m)

b. 解決沖突采用開放定址法，即 f2(key) = (f(key)+i) % size (p ≤ m)

（1）定義哈希表的數(shù)據(jù)結(jié)構(gòu)

class HashTable {

public int key = 0; // 關鍵字

public int data = 0; // 數(shù)值

public int count = 0; // 探查次數(shù)

}

（2）在哈希表中查找關鍵字key

根據(jù)設定的哈希函數(shù)，計算哈希地址。如果出現(xiàn)地址沖突，則按設定的處理沖突的方法尋找下一個地址。

如此反復，直到不沖突為止（查找成功）或某個地址為空（查找失?。?。

/**

* 查找哈希表

* 構(gòu)造哈希表采用除留取余法，即f(key) = key mod p (p ≤ size)

* 解決沖突采用開放定址法，即f2(key) = (f(key) + i) mod p (1 ≤ i ≤ size-1)

* ha為哈希表，p為模，size為哈希表大小，key為要查找的關鍵字

*/

public int searchHashTable(HashTable[] ha, int p, int size, int key) {

int addr = key % p; // 采用除留取余法找哈希地址

// 若發(fā)生沖突，用開放定址法找下一個哈希地址

while (ha[addr].key != KEY && ha[addr].key != key) {

addr = (addr + 1) % size;

}

if (ha[addr].key == key) {

return addr; // 查找成功

} else {

return FAILED; // 查找失敗

}

}

（3）刪除關鍵字為key的記錄

在采用開放定址法處理沖突的哈希表上執(zhí)行刪除操作，只能在被刪記錄上做刪除標記，而不能真正刪除記錄。

找到要刪除的記錄，將關鍵字置為刪除標記DELKEY。

public int deleteHashTable(HashTable[] ha, int p, int size, int key) {

int addr = 0;

addr = searchHashTable(ha, p, size, key);

if (FAILED != addr) { // 找到記錄

ha[addr].key = DELKEY; // 將該位置的關鍵字置為DELKEY

return SUCCESS;

} else {

return KEY; // 查找不到記錄，直接返回KEY

}

}

（4）插入關鍵字為key的記錄

將待插入的關鍵字key插入哈希表

先調(diào)用查找算法，若在表中找到待插入的關鍵字，則插入失??；

若在表中找到一個開放地址，則將待插入的結(jié)點插入到其中，則插入成功。

public void insertHashTable(HashTable[] ha, int p, int size, int key) {

int i = 1;

int addr = 0;

addr = key % p; // 通過哈希函數(shù)獲取哈希地址

if (ha[addr].key == KEY || ha[addr].key == DELKEY) { // 如果沒有沖突，直接插入

ha[addr].key = key;

ha[addr].count = 1;

} else { // 如果有沖突，使用開放定址法處理沖突

do {

addr = (addr + 1) % size; // 尋找下一個哈希地址

i++;

} while (ha[addr].key != KEY && ha[addr].key != DELKEY);

ha[addr].key = key;

ha[addr].count = i;

}

}

（5）建立哈希表

先將哈希表中各關鍵字清空，使其地址為開放的，然后調(diào)用插入算法將給定的關鍵字序列依次插入。

public void createHashTable(HashTable[] ha, int[] list, int p, int size) {

int i = 0;

// 將哈希表中的所有關鍵字清空

for (i = 0; i < ha.length; i++) {

ha[i].key = KEY;

ha[i].count = 0;

}

// 將關鍵字序列依次插入哈希表中

for (i = 0; i < list.length; i++) {

this.insertHashTable(ha, p, size, list[i]);

}

}

完整代碼

class HashTable {

public int key = 0; // 關鍵字

public int data = 0; // 數(shù)值

public int count = 0; // 探查次數(shù)

}

public class HashSearch {

private final static int MAXSIZE = 20;

private final static int KEY = 1;

private final static int DELKEY = 2;

private final static int SUCCESS = 0;

private final static int FAILED = 0xFFFFFFFF;

/**

* 查找哈希表

* 構(gòu)造哈希表采用除留取余法，即f(key) = key mod p (p ≤ size)

* 解決沖突采用開放定址法，即f2(key) = (f(key) + i) mod p (1 ≤ i ≤ size-1)

* ha為哈希表，p為模，size為哈希表大小，key為要查找的關鍵字

*/

public int searchHashTable(HashTable[] ha, int p, int size, int key) {

int addr = key % p; // 采用除留取余法找哈希地址

// 若發(fā)生沖突，用開放定址法找下一個哈希地址

while (ha[addr].key != KEY && ha[addr].key != key) {

addr = (addr + 1) % size;

}

if (ha[addr].key == key) {

return addr; // 查找成功

} else {

return FAILED; // 查找失敗

}

}

/**

* 刪除哈希表中關鍵字為key的記錄

* 找到要刪除的記錄，將關鍵字置為刪除標記DELKEY

*/

public int deleteHashTable(HashTable[] ha, int p, int size, int key) {

int addr = 0;

addr = searchHashTable(ha, p, size, key);

if (FAILED != addr) { // 找到記錄

ha[addr].key = DELKEY; // 將該位置的關鍵字置為DELKEY

return SUCCESS;

} else {

return KEY; // 查找不到記錄，直接返回KEY

}

}

/**

* 將待插入的關鍵字key插入哈希表

* 先調(diào)用查找算法，若在表中找到待插入的關鍵字，則插入失??；

* 若在表中找到一個開放地址，則將待插入的結(jié)點插入到其中，則插入成功。

*/

public void insertHashTable(HashTable[] ha, int p, int size, int key) {

int i = 1;

int addr = 0;

addr = key % p; // 通過哈希函數(shù)獲取哈希地址

if (ha[addr].key == KEY || ha[addr].key == DELKEY) { // 如果沒有沖突，直接插入

ha[addr].key = key;

ha[addr].count = 1;

} else { // 如果有沖突，使用開放定址法處理沖突

do {

addr = (addr + 1) % size; // 尋找下一個哈希地址

i++;

} while (ha[addr].key != KEY && ha[addr].key != DELKEY);

ha[addr].key = key;

ha[addr].count = i;

}

}

/**

* 創(chuàng)建哈希表

* 先將哈希表中各關鍵字清空，使其地址為開放的，然后調(diào)用插入算法將給定的關鍵字序列依次插入。

*/

public void createHashTable(HashTable[] ha, int[] list, int p, int size) {

int i = 0

// 將哈希表中的所有關鍵字清空

for (i = 0; i < ha.length; i++) {

ha[i].key = KEY;

ha[i].count = 0;

}

// 將關鍵字序列依次插入哈希表中

for (i = 0; i < list.length; i++) {

this.insertHashTable(ha, p, size, list[i]);

}

}

/**

* 輸出哈希表

*/

public void displayHashTable(HashTable[] ha) {

int i = 0;

System.out.format("pos:\", "pos");

for (i = 0; i < ha.length; i++) {

System.out.format("M", i);

}

System.out.println;

System.out.format("key:\");

for (i = 0; i < ha.length; i++) {

if (ha[i].key != KEY) {

System.out.format("M", ha[i].key);

} else {

System.out.format(" ");

}

}

System.out.println;

System.out.format("count:\");

for (i = 0; i < ha.length; i++) {

if (0 != ha[i].count) {

System.out.format("M", ha[i].count);

} else {

System.out.format(" ");

}

}

System.out.println;

}

public static void main(String[] args) {

int list = { 3, 112, 245, 27, 44, 19, 76, 29, 90 };

HashTable ha = new HashTable[MAXSIZE];

for (int i = 0; i < ha.length; i++) {

ha[i] = new HashTable;

}

HashSearch search = new HashSearch;

search.createHashTable(ha, list, 19, MAXSIZE);

search.displayHashTable(ha);

}

}

參考資料

《數(shù)據(jù)結(jié)構(gòu)習題與解析》（B級第3版）

轉(zhuǎn)自：靜默虛空

http://www.cnblogs.com/jingmoxukong/p/4332252.html

-----這里是數(shù)學思維的聚集地------

“超級數(shù)學建模”（微信號supermodeling），每天學一點小知識，輕松了解各種思維，做個好玩的理性派。50萬數(shù)學精英都在關注！

以上就是關于如何查找pos機,詳解哈希表的查找的知識，后面我們會繼續(xù)為大家整理關于如何查找pos機的知識，希望能夠幫助到大家！