主题:哈希表
定义:根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。
给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能得到包含该关键字的记录在表中的地址,则称表M为哈希(Hash)表,函数f(key)为哈希(Hash) 函数。
/** ********************* * The second constructor. For Hash code only. It is assumed that * paraKeyArray.length <= paraLength. * * @param paraKeyArray The array of the keys. * @param paraContentArray The array of contents. * @param paraLength The space for the Hash table. ********************* */ public DataArray(int[] paraKeyArray, String[] paraContentArray, int paraLength) { // Step 1. Initialize. length = paraLength; data = new DataNode[length]; for (int i = 0; i < length; i++) { data[i] = null; } // Of for i // Step 2. Fill the data. int tempPosition; for (int i = 0; i < paraKeyArray.length; i++) { // Hash. tempPosition = paraKeyArray[i] % paraLength; // Find an empty position while (data[tempPosition] != null) { tempPosition = (tempPosition + 1) % paraLength; System.out.println("Collision, move forward for key " + paraKeyArray[i]); } // Of while data[tempPosition] = new DataNode(paraKeyArray[i], paraContentArray[i]); } // Of for i }// Of the second constructor /** ********************* * Hash search. * * @param paraKey The given key. * @return The content of the key. ********************* */ public String hashSearch(int paraKey) { int tempPosition = paraKey % length; while (data[tempPosition] != null) { if (data[tempPosition].key == paraKey) { return data[tempPosition].content; } // Of if System.out.println("Not this one for " + paraKey); tempPosition = (tempPosition + 1) % length; } // Of while return "null"; }// Of hashSearch /** ********************* * Test the method. ********************* */ public static void hashSearchTest() { int[] tempUnsortedKeys = { 16, 33, 38, 69, 57, 95, 86 }; String[] tempContents = { "if", "then", "else", "switch", "case", "for", "while" }; DataArray tempDataArray = new DataArray(tempUnsortedKeys, tempContents, 19); System.out.println(tempDataArray); System.out.println("Search result of 95 is: " + tempDataArray.hashSearch(95)); System.out.println("Search result of 38 is: " + tempDataArray.hashSearch(38)); System.out.println("Search result of 57 is: " + tempDataArray.hashSearch(57)); System.out.println("Search result of 4 is: " + tempDataArray.hashSearch(4)); }// Of hashSearchTest /** ********************* * The entrance of the program. * * @param args Not used now. ********************* */ public static void main(String args[]) { System.out.println("\r\n-------sequentialSearchTest-------"); sequentialSearchTest(); System.out.println("\r\n-------binarySearchTest-------"); binarySearchTest(); System.out.println("\r\n-------hashSearchTest-------"); hashSearchTest(); }// Of main