哈希表 哈希冲突解决之链地址法
哈希函数: 使用特定的哈希算法,将关键字哈希化,压缩到一个较小的范围
哈希表: 使用哈希算法, 把一个大范围的数字哈希化成一个小范围的数字。 这个小范围对应着数组的下标。 使用哈希函数向数组插入数据后, 这个数组称为哈希表
链地址法: 开放地址法中,通过在哈希表中寻找一个空位解决哈希冲突问题。另一个方法是在哈希表每个单元中设置链表。某个数据项的关键字还是像通常一样映射到哈希表的单元,而数据项本身插入到这个单元的链表中。
装填因子: 链地址法中的装填因子(数据项数和哈希表容量的比值)与开发地址法的不同。 在链地址法中,需要在有N个单元的数组中装入N个或更多的数据项;因此装填因子一般为1,或比一大。 这没问题;因为,某些位置包含的链表中包含两个或两个以上的数据项。
下面将使用链地址法 实现哈希表并解决哈希冲突问题
1. 创建一个link类
public class Link { private int iData; public Link next; public Link(int it){ this.iData = it; } public int getKey(){ return iData; } public void displayLink(){ System.err.print(iData+" "); } }
2. 创建一个SortedList类
public class SortedList { private Link first; public void SortedList(){ first = null; } public void insert(Link theLink){ int key = theLink.getKey(); Link previous =null; Link current = first; while(current !=null && key> current.getKey()){ previous = current; current = current.next; } if (previous ==null){ first = theLink; }else{ previous.next = theLink; theLink.next = current; } } public void delete(int key){ Link previous = null; Link current = first; while(current !=null && key != current.getKey()){ previous = current; current = current.next; } if (previous == null){ first = first.next; }else{ previous.next = current.next; } } public Link find(int key){ Link current = first; while(current!=null && current.getKey()<= key){ if (current.getKey() == key){ return current; } current = current.next; } return null; } public void displayList(){ System.out.print("List (first --> last):"); Link current = first; while(current!=null ){ current.displayLink(); current = current.next; } System.out.print(""); } }
3. 使用链地址法实现哈希表
public class LinkHashTable { private SortedList[] hashArray; private int arraySize; public LinkHashTable(int size){ arraySize = size; hashArray = new SortedList[arraySize]; for (int j=0; j<arraySize; j++){ hashArray[j] = new SortedList(); } } public void displayTable(){ for (int j = 0; j<arraySize;j++){ System.out.print(j+ ". "); hashArray[j].displayList(); } } public int hashFunc(int key){ return key % arraySize; } public void insert (Link theLink){ int key = theLink.getKey(); int hashVal = hashFunc(key); hashArray[hashVal].insert(theLink); } public void delete(int key){ int hashVal = hashFunc(key); hashArray[hashVal].delete(key); } public Link find(int key){ int hashVal = hashFunc(key); Link theLink = hashArray[hashVal].find(key); return theLink; } }
4. 编辑测试类
public class HashChainApp { public static void main(String[] args) throws IOException{ int aKey; Link aDataItem; int size, n, keysPerCell = 100; System.out.print("Enter size of hash table: "); size = getInt(); System.out.print("Enter initial number of items: "); n =getInt(); LinkHashTable theHashTable = new LinkHashTable(size); for (int j=0; j<n; j++){ aKey = (int) (Math.random() * keysPerCell * size); aDataItem = new Link(aKey); theHashTable.insert(aDataItem); } while(true){ 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("Entry 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.print("Found " + aKey); }else{ System.out.println("could not find " +aKey); } break; default: System.out.print("Invalid entry\n"); } } } 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); } }