網(wǎng)上有很多關(guān)于如何查找pos機(jī),詳解哈希表的查找的知識(shí)，也有很多人為大家解答關(guān)于如何查找pos機(jī)的問(wèn)題，今天pos機(jī)之家(m.dsth100338.com)為大家整理了關(guān)于這方面的知識(shí)，讓我們一起來(lái)看下吧!
本文目錄一覽：
如何查找pos機(jī)
哈希表和哈希函數(shù)
在記錄的存儲(chǔ)位置和它的關(guān)鍵字之間是建立一個(gè)確定的對(duì)應(yīng)關(guān)系（映射函數(shù)），使每個(gè)關(guān)鍵字和一個(gè)存儲(chǔ)位置能唯一對(duì)應(yīng)。
這個(gè)映射函數(shù)稱(chēng)為哈希函數(shù)，根據(jù)這個(gè)原則建立的表稱(chēng)為哈希表(Hash Table)，也叫散列表。
以上描述，如果通過(guò)數(shù)學(xué)形式來(lái)描述就是：
若查找關(guān)鍵字為 key，則其值存放在 f(key) 的存儲(chǔ)位置上。由此，不需比較便可直接取得所查記錄。
注：哈希查找與線(xiàn)性表查找和樹(shù)表查找最大的區(qū)別在于，不用數(shù)值比較。
沖突
若 key1 ≠ key2 ，而 f(key1) = f(key2)，這種情況稱(chēng)為沖突(Collision)。
根據(jù)哈希函數(shù)f(key)和處理沖突的方法將一組關(guān)鍵字映射到一個(gè)有限的連續(xù)的地址集（區(qū)間）上，并以關(guān)鍵字在地址集中的“像”作為記錄在表中的存儲(chǔ)位置，這一映射過(guò)程稱(chēng)為構(gòu)造哈希表。
構(gòu)造哈希表這個(gè)場(chǎng)景就像汽車(chē)找停車(chē)位，如果車(chē)位被人占了，只能找空的地方停。
構(gòu)造哈希表
由以上內(nèi)容可知，哈希查找本身其實(shí)不費(fèi)吹灰之力，問(wèn)題的關(guān)鍵在于如何構(gòu)造哈希表和處理沖突。
常見(jiàn)的構(gòu)造哈希表的方法有 5 種：
（1）直接定址法
說(shuō)白了，就是小學(xué)時(shí)學(xué)過(guò)的一元一次方程。
即 f(key) = a * key + b。其中，a和b 是常數(shù)。
（2）數(shù)字分析法
假設(shè)關(guān)鍵字是R進(jìn)制數(shù)（如十進(jìn)制）。并且哈希表中可能出現(xiàn)的關(guān)鍵字都是事先知道的，則可選取關(guān)鍵字的若干數(shù)位組成哈希地址。
選取的原則是使得到的哈希地址盡量避免沖突，即所選數(shù)位上的數(shù)字盡可能是隨機(jī)的。
（3）平方取中法
取關(guān)鍵字平方后的中間幾位為哈希地址。通常在選定哈希函數(shù)時(shí)不一定能知道關(guān)鍵字的全部情況，僅取其中的幾位為地址不一定合適；
而一個(gè)數(shù)平方后的中間幾位數(shù)和數(shù)的每一位都相關(guān)， 由此得到的哈希地址隨機(jī)性更大。取的位數(shù)由表長(zhǎng)決定。
（4）除留余數(shù)法
取關(guān)鍵字被某個(gè)不大于哈希表表長(zhǎng) m 的數(shù) p 除后所得的余數(shù)為哈希地址。
即 f(key) = key % p (p ≤ m)
這是一種最簡(jiǎn)單、最常用的方法，它不僅可以對(duì)關(guān)鍵字直接取模，也可在折疊、平方取中等運(yùn)算之后取模。
注意：p的選擇很重要，如果選的不好，容易產(chǎn)生沖突。根據(jù)經(jīng)驗(yàn)，一般情況下可以選p為素?cái)?shù)。
（5）隨機(jī)數(shù)法
選擇一個(gè)隨機(jī)函數(shù)，取關(guān)鍵字的隨機(jī)函數(shù)值為它的哈希地址，即 f(key) = random(key)。
通常，在關(guān)鍵字長(zhǎng)度不等時(shí)采用此法構(gòu)造哈希函數(shù)較為恰當(dāng)。
解決沖突
設(shè)計(jì)合理的哈希函數(shù)可以減少?zèng)_突，但不能完全避免沖突。
所以需要有解決沖突的方法，常見(jiàn)有兩類(lèi)
（1）開(kāi)放定址法
如果兩個(gè)數(shù)據(jù)元素的哈希值相同，則在哈希表中為后插入的數(shù)據(jù)元素另外選擇一個(gè)表項(xiàng)。
當(dāng)程序查找哈希表時(shí)，如果沒(méi)有在第一個(gè)對(duì)應(yīng)的哈希表項(xiàng)中找到符合查找要求的數(shù)據(jù)元素，程序就會(huì)繼續(xù)往后查找，直到找到一個(gè)符合查找要求的數(shù)據(jù)元素，或者遇到一個(gè)空的表項(xiàng)。
例子
若要將一組關(guān)鍵字序列 {1, 9, 25, 11, 12, 35, 17, 29} 存放到哈希表中。
采用除留余數(shù)法構(gòu)造哈希表；采用開(kāi)放定址法處理沖突。
不妨設(shè)選取的p和m為13，由 f(key) = key % 13 可以得到下表。
需要注意的是，在上圖中有兩個(gè)關(guān)鍵字的探查次數(shù)為 2 ，其他都是1。
這個(gè)過(guò)程是這樣的：
a. 12 % 13 結(jié)果是12，而它的前面有個(gè) 25 ，25 % 13 也是12，存在沖突。
我們使用開(kāi)放定址法 (12 + 1) % 13 = 0，沒(méi)有沖突，完成。
b. 35 % 13 結(jié)果是 9，而它的前面有個(gè) 9，9 % 13也是 9，存在沖突。
我們使用開(kāi)放定址法 (9 + 1) % 13 = 10，沒(méi)有沖突，完成。
（2）拉鏈法
將哈希值相同的數(shù)據(jù)元素存放在一個(gè)鏈表中，在查找哈希表的過(guò)程中，當(dāng)查找到這個(gè)鏈表時(shí)，必須采用線(xiàn)性查找方法。
在這種方法中，哈希表中每個(gè)單元存放的不再是記錄本身，而是相應(yīng)同義詞單鏈表的頭指針。
例子
如果對(duì)開(kāi)放定址法例子中提到的序列使用拉鏈法，得到的結(jié)果如下圖所示：
實(shí)現(xiàn)一個(gè)哈希表
假設(shè)要實(shí)現(xiàn)一個(gè)哈希表，要求
a. 哈希函數(shù)采用除留余數(shù)法，即 f(key) = key % p (p ≤ m)
b. 解決沖突采用開(kāi)放定址法，即 f2(key) = (f(key)+i) % size (p ≤ m)
（1）定義哈希表的數(shù)據(jù)結(jié)構(gòu)
class HashTable {
public int key = 0; // 關(guān)鍵字
public int data = 0; // 數(shù)值
public int count = 0; // 探查次數(shù)
}
（2）在哈希表中查找關(guān)鍵字key
根據(jù)設(shè)定的哈希函數(shù)，計(jì)算哈希地址。如果出現(xiàn)地址沖突，則按設(shè)定的處理沖突的方法尋找下一個(gè)地址。
如此反復(fù)，直到不沖突為止（查找成功）或某個(gè)地址為空（查找失敗）。
/**
* 查找哈希表
* 構(gòu)造哈希表采用除留取余法，即f(key) = key mod p (p ≤ size)
* 解決沖突采用開(kāi)放定址法，即f2(key) = (f(key) + i) mod p (1 ≤ i ≤ size-1)
* ha為哈希表，p為模，size為哈希表大小，key為要查找的關(guān)鍵字
*/
public int searchHashTable(HashTable[] ha, int p, int size, int key) {
int addr = key % p; // 采用除留取余法找哈希地址
// 若發(fā)生沖突，用開(kāi)放定址法找下一個(gè)哈希地址
while (ha[addr].key != KEY && ha[addr].key != key) {
addr = (addr + 1) % size;
}
if (ha[addr].key == key) {
return addr; // 查找成功
} else {
return FAILED; // 查找失敗
}
}
（3）刪除關(guān)鍵字為key的記錄
在采用開(kāi)放定址法處理沖突的哈希表上執(zhí)行刪除操作，只能在被刪記錄上做刪除標(biāo)記，而不能真正刪除記錄。
找到要?jiǎng)h除的記錄，將關(guān)鍵字置為刪除標(biāo)記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; // 將該位置的關(guān)鍵字置為DELKEY
return SUCCESS;
} else {
return KEY; // 查找不到記錄，直接返回KEY
}
}
（4）插入關(guān)鍵字為key的記錄
將待插入的關(guān)鍵字key插入哈希表
先調(diào)用查找算法，若在表中找到待插入的關(guān)鍵字，則插入失??；
若在表中找到一個(gè)開(kāi)放地址，則將待插入的結(jié)點(diǎn)插入到其中，則插入成功。
public void insertHashTable(HashTable[] ha, int p, int size, int key) {
int i = 1;
int addr = 0;
addr = key % p; // 通過(guò)哈希函數(shù)獲取哈希地址
if (ha[addr].key == KEY || ha[addr].key == DELKEY) { // 如果沒(méi)有沖突，直接插入
ha[addr].key = key;
ha[addr].count = 1;
} else { // 如果有沖突，使用開(kāi)放定址法處理沖突
do {
addr = (addr + 1) % size; // 尋找下一個(gè)哈希地址
i++;
} while (ha[addr].key != KEY && ha[addr].key != DELKEY);
ha[addr].key = key;
ha[addr].count = i;
}
}
（5）建立哈希表
先將哈希表中各關(guān)鍵字清空，使其地址為開(kāi)放的，然后調(diào)用插入算法將給定的關(guān)鍵字序列依次插入。
public void createHashTable(HashTable[] ha, int[] list, int p, int size) {
int i = 0;
// 將哈希表中的所有關(guān)鍵字清空
for (i = 0; i < ha.length; i++) {
ha[i].key = KEY;
ha[i].count = 0;
}
// 將關(guān)鍵字序列依次插入哈希表中
for (i = 0; i < list.length; i++) {
this.insertHashTable(ha, p, size, list[i]);
}
}
完整代碼
class HashTable {
public int key = 0; // 關(guān)鍵字
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)
* 解決沖突采用開(kāi)放定址法，即f2(key) = (f(key) + i) mod p (1 ≤ i ≤ size-1)
* ha為哈希表，p為模，size為哈希表大小，key為要查找的關(guān)鍵字
*/
public int searchHashTable(HashTable[] ha, int p, int size, int key) {
int addr = key % p; // 采用除留取余法找哈希地址
// 若發(fā)生沖突，用開(kāi)放定址法找下一個(gè)哈希地址
while (ha[addr].key != KEY && ha[addr].key != key) {
addr = (addr + 1) % size;
}
if (ha[addr].key == key) {
return addr; // 查找成功
} else {
return FAILED; // 查找失敗
}
}
/**
* 刪除哈希表中關(guān)鍵字為key的記錄
* 找到要?jiǎng)h除的記錄，將關(guān)鍵字置為刪除標(biāo)記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; // 將該位置的關(guān)鍵字置為DELKEY
return SUCCESS;
} else {
return KEY; // 查找不到記錄，直接返回KEY
}
}
/**
* 將待插入的關(guān)鍵字key插入哈希表
* 先調(diào)用查找算法，若在表中找到待插入的關(guān)鍵字，則插入失?。?/p>
* 若在表中找到一個(gè)開(kāi)放地址，則將待插入的結(jié)點(diǎn)插入到其中，則插入成功。
*/
public void insertHashTable(HashTable[] ha, int p, int size, int key) {
int i = 1;
int addr = 0;
addr = key % p; // 通過(guò)哈希函數(shù)獲取哈希地址
if (ha[addr].key == KEY || ha[addr].key == DELKEY) { // 如果沒(méi)有沖突，直接插入
ha[addr].key = key;
ha[addr].count = 1;
} else { // 如果有沖突，使用開(kāi)放定址法處理沖突
do {
addr = (addr + 1) % size; // 尋找下一個(gè)哈希地址
i++;
} while (ha[addr].key != KEY && ha[addr].key != DELKEY);
ha[addr].key = key;
ha[addr].count = i;
}
}
/**
* 創(chuàng)建哈希表
* 先將哈希表中各關(guān)鍵字清空，使其地址為開(kāi)放的，然后調(diào)用插入算法將給定的關(guān)鍵字序列依次插入。
*/
public void createHashTable(HashTable[] ha, int[] list, int p, int size) {
int i = 0
// 將哈希表中的所有關(guān)鍵字清空
for (i = 0; i < ha.length; i++) {
ha[i].key = KEY;
ha[i].count = 0;
}
// 將關(guān)鍵字序列依次插入哈希表中
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)習(xí)題與解析》（B級(jí)第3版）
轉(zhuǎn)自：靜默虛空
http://www.cnblogs.com/jingmoxukong/p/4332252.html
-----這里是數(shù)學(xué)思維的聚集地------
“超級(jí)數(shù)學(xué)建模”（微信號(hào)supermodeling），每天學(xué)一點(diǎn)小知識(shí)，輕松了解各種思維，做個(gè)好玩的理性派。50萬(wàn)數(shù)學(xué)精英都在關(guān)注！
以上就是關(guān)于如何查找pos機(jī),詳解哈希表的查找的知識(shí)，后面我們會(huì)繼續(xù)為大家整理關(guān)于如何查找pos機(jī)的知識(shí)，希望能夠幫助到大家！
