哈希表是一種數據結構，它可以提供快速的插入操作和查找操作。

哈希表的缺點：基于數組，數組創建后難于擴展。不能有序遍歷

哈希化

把關鍵字轉換成數組下標（哈希函數）

沖突（碰撞）

開放地址法

線性探測

// hash.java // demonstrates hash table with linear probing // to run this program: C:>java HashTableApp import java.io.*; class DataItem{ // (could have more data)private int iData; // data item (key) //--------------------------------------------------------------public DataItem(int ii) // constructor{ iData = ii; } //--------------------------------------------------------------public int getKey(){ return iData; } //--------------------------------------------------------------} // end class DataItem class HashTable{private DataItem[] hashArray; // array holds hash tableprivate int arraySize;private DataItem nonItem; // for deleted items // -------------------------------------------------------------public HashTable(int size) // constructor{arraySize = size;hashArray = new DataItem[arraySize];nonItem = new DataItem(-1); // deleted item key is -1} // -------------------------------------------------------------public void displayTable(){System.out.print("Table: ");for(int j=0; j<arraySize; j++){if(hashArray[j] != null)System.out.print(hashArray[j].getKey() + " ");elseSystem.out.print("** ");}System.out.println("");} // -------------------------------------------------------------public int hashFunc(int key){return key % arraySize; // hash function} // -------------------------------------------------------------public void insert(DataItem item) // insert a DataItem// (assumes table not full){int key = item.getKey(); // extract keyint hashVal = hashFunc(key); // hash the key// until empty cell or -1,while(hashArray[hashVal] != null &&hashArray[hashVal].getKey() != -1){++hashVal; // go to next cellhashVal %= arraySize; // wraparound if necessary}hashArray[hashVal] = item; // insert item} // end insert() // -------------------------------------------------------------public DataItem delete(int key) // delete a DataItem{int hashVal = hashFunc(key); // hash the keywhile(hashArray[hashVal] != null) // until empty cell,{ // found the key?if(hashArray[hashVal].getKey() == key){DataItem temp = hashArray[hashVal]; // save itemhashArray[hashVal] = nonItem; // delete itemreturn temp; // return item}++hashVal; // go to next cellhashVal %= arraySize; // wraparound if necessary}return null; // can't find item} // end delete() // -------------------------------------------------------------public DataItem find(int key) // find item with key{int hashVal = hashFunc(key); // hash the keywhile(hashArray[hashVal] != null) // until empty cell,{ // found the key?if(hashArray[hashVal].getKey() == key)return hashArray[hashVal]; // yes, return item++hashVal; // go to next cellhashVal %= arraySize; // wraparound if necessary}return null; // can't find item} // -------------------------------------------------------------} // end class HashTable class HashTableApp{public static void main(String[] args) throws IOException{DataItem aDataItem;int aKey, size, n, keysPerCell;// get sizesSystem.out.print("Enter size of hash table: ");size = getInt();System.out.print("Enter initial number of items: ");n = getInt();keysPerCell = 10;// make tableHashTable theHashTable = new HashTable(size);for(int j=0; j<n; j++) // insert data{aKey = (int)(java.lang.Math.random() *keysPerCell * size);aDataItem = new DataItem(aKey);theHashTable.insert(aDataItem);}while(true) // interact with user{System.out.print("Enter first letter of ");System.out.print("show, insert, delete, or find: ");char choice = getChar();switch(choice){case 's':theHashTable.displayTable();break;case 'i':System.out.print("Enter key value to insert: ");aKey = getInt();aDataItem = new DataItem(aKey);theHashTable.insert(aDataItem);break;case 'd':System.out.print("Enter key value to delete: ");aKey = getInt();theHashTable.delete(aKey);break;case 'f':System.out.print("Enter key value to find: ");aKey = getInt();aDataItem = theHashTable.find(aKey);if(aDataItem != null){System.out.println("Found " + aKey);}elseSystem.out.println("Could not find " + aKey);break;default:System.out.print("Invalid entry\n");} // end switch} // end while} // end main() //--------------------------------------------------------------public static String getString() throws IOException{InputStreamReader isr = new InputStreamReader(System.in);BufferedReader br = new BufferedReader(isr);String s = br.readLine();return s;} //--------------------------------------------------------------public static char getChar() throws IOException{String s = getString();return s.charAt(0);} //-------------------------------------------------------------public static int getInt() throws IOException{String s = getString();return Integer.parseInt(s);} //--------------------------------------------------------------} // end class HashTableApp

擴展數組

二次探測

雙重散列/二次哈希

// hashDouble.java // demonstrates hash table with double hashing // to run this program: C:>java HashDoubleApp import java.io.*; class DataItem{ // (could have more items)private int iData; // data item (key) //--------------------------------------------------------------public DataItem(int ii) // constructor{ iData = ii; } //--------------------------------------------------------------public int getKey(){ return iData; } //--------------------------------------------------------------} // end class DataItem class HashTable{private DataItem[] hashArray; // array is the hash tableprivate int arraySize;private DataItem nonItem; // for deleted items // -------------------------------------------------------------HashTable(int size) // constructor{arraySize = size;hashArray = new DataItem[arraySize];nonItem = new DataItem(-1);} // -------------------------------------------------------------public void displayTable(){System.out.print("Table: ");for(int j=0; j<arraySize; j++){if(hashArray[j] != null)System.out.print(hashArray[j].getKey()+ " ");elseSystem.out.print("** ");}System.out.println("");} // -------------------------------------------------------------public int hashFunc1(int key){return key % arraySize;} // -------------------------------------------------------------public int hashFunc2(int key){// non-zero, less than array size, different from hF1// array size must be relatively prime to 5, 4, 3, and 2return 5 - key % 5;} // -------------------------------------------------------------// insert a DataItempublic void insert(int key, DataItem item)// (assumes table not full){int hashVal = hashFunc1(key); // hash the keyint stepSize = hashFunc2(key); // get step size// until empty cell or -1while(hashArray[hashVal] != null &&hashArray[hashVal].getKey() != -1){hashVal += stepSize; // add the stephashVal %= arraySize; // for wraparound}hashArray[hashVal] = item; // insert item} // end insert() // -------------------------------------------------------------public DataItem delete(int key) // delete a DataItem{int hashVal = hashFunc1(key); // hash the keyint stepSize = hashFunc2(key); // get step sizewhile(hashArray[hashVal] != null) // until empty cell,{ // is correct hashVal?if(hashArray[hashVal].getKey() == key){DataItem temp = hashArray[hashVal]; // save itemhashArray[hashVal] = nonItem; // delete itemreturn temp; // return item}hashVal += stepSize; // add the stephashVal %= arraySize; // for wraparound}return null; // can't find item} // end delete() // -------------------------------------------------------------public DataItem find(int key) // find item with key// (assumes table not full){int hashVal = hashFunc1(key); // hash the keyint stepSize = hashFunc2(key); // get step sizewhile(hashArray[hashVal] != null) // until empty cell,{ // is correct hashVal?if(hashArray[hashVal].getKey() == key)return hashArray[hashVal]; // yes, return itemhashVal += stepSize; // add the stephashVal %= arraySize; // for wraparound}return null; // can't find item} // -------------------------------------------------------------} // end class HashTable class HashDoubleApp{public static void main(String[] args) throws IOException{int aKey;DataItem aDataItem;int size, n;// get sizesSystem.out.print("Enter size of hash table: ");size = getInt();System.out.print("Enter initial number of items: ");n = getInt();// make tableHashTable theHashTable = new HashTable(size);for(int j=0; j<n; j++) // insert data{aKey = (int)(java.lang.Math.random() * 2 * size);aDataItem = new DataItem(aKey);theHashTable.insert(aKey, aDataItem);}while(true) // interact with user{System.out.print("Enter first letter of ");System.out.print("show, insert, delete, or find: ");char choice = getChar();switch(choice){case 's':theHashTable.displayTable();break;case 'i':System.out.print("Enter key value to insert: ");aKey = getInt();aDataItem = new DataItem(aKey);theHashTable.insert(aKey, aDataItem);break;case 'd':System.out.print("Enter key value to delete: ");aKey = getInt();theHashTable.delete(aKey);break;case 'f':System.out.print("Enter key value to find: ");aKey = getInt();aDataItem = theHashTable.find(aKey);if(aDataItem != null)System.out.println("Found " + aKey);elseSystem.out.println("Could not find " + aKey);break;default:System.out.print("Invalid entry\n");} // end switch} // end while} // end main() //--------------------------------------------------------------public static String getString() throws IOException{InputStreamReader isr = new InputStreamReader(System.in);BufferedReader br = new BufferedReader(isr);String s = br.readLine();return s;} //--------------------------------------------------------------public static char getChar() throws IOException{String s = getString();return s.charAt(0);} //-------------------------------------------------------------public static int getInt() throws IOException{String s = getString();return Integer.parseInt(s);} //--------------------------------------------------------------} // end class HashDoubleApp

鏈地址法

數組 + 鏈表，桶結構

裝載因子

// hashChain.java // demonstrates hash table with separate chaining // to run this program: C:>java HashChainApp import java.io.*; class Link{ // (could be other items)private int iData; // data itempublic Link next; // next link in list // -------------------------------------------------------------public Link(int it) // constructor{ iData= it; } // -------------------------------------------------------------public int getKey(){ return iData; } // -------------------------------------------------------------public void displayLink() // display this link{ System.out.print(iData + " "); }} // end class Link class SortedList{private Link first; // ref to first list item // -------------------------------------------------------------public void SortedList() // constructor{ first = null; } // -------------------------------------------------------------public void insert(Link theLink) // insert link, in order{int key = theLink.getKey();Link previous = null; // start at firstLink current = first;// until end of list,while( current != null && key > current.getKey() ){ // or current > key,previous = current;current = current.next; // go to next item}if(previous==null) // if beginning of list,first = theLink; // first --> new linkelse // not at beginning,previous.next = theLink; // prev --> new linktheLink.next = current; // new link --> current} // end insert() // -------------------------------------------------------------public void delete(int key) // delete link{ // (assumes non-empty list)Link previous = null; // start at firstLink current = first;// until end of list,while( current != null && key != current.getKey() ){ // or key == current,previous = current;current = current.next; // go to next link}// disconnect linkif(previous==null) // if beginning of listfirst = first.next; // delete first linkelse // not at beginningprevious.next = current.next; // delete current link} // end delete() // -------------------------------------------------------------public Link find(int key) // find link{Link current = first; // start at first// until end of list,while(current != null && current.getKey() <= key){ // or key too small,if(current.getKey() == key) // is this the link?return current; // found it, return linkcurrent = current.next; // go to next item}return null; // didn't find it} // end find() // -------------------------------------------------------------public void displayList(){System.out.print("List (first-->last): ");Link current = first; // start at beginning of listwhile(current != null) // until end of list,{current.displayLink(); // print datacurrent = current.next; // move to next link}System.out.println("");}} // end class SortedList class HashTable{private SortedList[] hashArray; // array of listsprivate int arraySize; // -------------------------------------------------------------public HashTable(int size) // constructor{arraySize = size;hashArray = new SortedList[arraySize]; // create arrayfor(int j=0; j<arraySize; j++) // fill arrayhashArray[j] = new SortedList(); // with lists} // -------------------------------------------------------------public void displayTable(){for(int j=0; j<arraySize; j++) // for each cell,{System.out.print(j + ". "); // display cell numberhashArray[j].displayList(); // display list}} // -------------------------------------------------------------public int hashFunc(int key) // hash function{return key % arraySize;} // -------------------------------------------------------------public void insert(Link theLink) // insert a link{int key = theLink.getKey();int hashVal = hashFunc(key); // hash the keyhashArray[hashVal].insert(theLink); // insert at hashVal} // end insert() // -------------------------------------------------------------public void delete(int key) // delete a link{int hashVal = hashFunc(key); // hash the keyhashArray[hashVal].delete(key); // delete link} // end delete() // -------------------------------------------------------------public Link find(int key) // find link{int hashVal = hashFunc(key); // hash the keyLink theLink = hashArray[hashVal].find(key); // get linkreturn theLink; // return link} // -------------------------------------------------------------} // end class HashTable class HashChainApp{public static void main(String[] args) throws IOException{int aKey;Link aDataItem;int size, n, keysPerCell = 100;// get sizesSystem.out.print("Enter size of hash table: ");size = getInt();System.out.print("Enter initial number of items: ");n = getInt();// make tableHashTable theHashTable = new HashTable(size);for(int j=0; j<n; j++) // insert data{aKey = (int)(java.lang.Math.random() *keysPerCell * size);aDataItem = new Link(aKey);theHashTable.insert(aDataItem);}while(true) // interact with user{System.out.print("Enter first letter of ");System.out.print("show, insert, delete, or find: ");char choice = getChar();switch(choice){case 's':theHashTable.displayTable();break;case 'i':System.out.print("Enter key value to insert: ");aKey = getInt();aDataItem = new Link(aKey);theHashTable.insert(aDataItem);break;case 'd':System.out.print("Enter key value to delete: ");aKey = getInt();theHashTable.delete(aKey);break;case 'f':System.out.print("Enter key value to find: ");aKey = getInt();aDataItem = theHashTable.find(aKey);if(aDataItem != null)System.out.println("Found " + aKey);elseSystem.out.println("Could not find " + aKey);break;default:System.out.print("Invalid entry\n");} // end switch} // end while} // end main() //--------------------------------------------------------------public static String getString() throws IOException{InputStreamReader isr = new InputStreamReader(System.in);BufferedReader br = new BufferedReader(isr);String s = br.readLine();return s;} //-------------------------------------------------------------public static char getChar() throws IOException{String s = getString();return s.charAt(0);} //-------------------------------------------------------------public static int getInt() throws IOException{String s = getString();return Integer.parseInt(s);} //--------------------------------------------------------------} // end class HashChainApp

哈希函數

快速的計算

隨機的關鍵字

使用質數作為取模的基數

總結

以上是生活随笔為你收集整理的Java数据结构和算法：哈希表的全部內容，希望文章能夠幫你解決所遇到的問題。

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