数据结构是哈希表（hashTable）（二）

public class HashTableDouble {  
    private DataItem[] hashArray;  
    private int arraySize;  
    private int itemNum;  
    private DataItem nonItem;  
 
    public HashTableDouble() {  
 arraySize = 13;  
 hashArray = new DataItem[arraySize];  
 nonItem = new DataItem(-1);  
    }  
 
    public void displayTable() {  
        System.out.print("Table:");  
        for (int i = 0; i < arraySize; i++) {  
            if (hashArray[i] != null) {  
                System.out.print(hashArray[i].getKey() + " ");  
            } else {  
                System.out.print("** ");  
            }  
        }  
        System.out.println("");  
    }  
 
    public int hashFunction1(int key) { // first hash function  
        return key % arraySize;  
    }  
 
    public int hashFunction2(int key) { // second hash function  
        return 5 - key % 5;  
    }  
 
    public boolean isFull() {  
        return (itemNum == arraySize);  
    }  
 
    public boolean isEmpty() {  
        return (itemNum == 0);  
    }  
 
    public void insert(DataItem item) {  
        if (isFull()) {  
            System.out.println("哈希表已满，重新哈希化..");  
            extendHashTable();  
        }  
        int key = item.getKey();  
        int hashVal = hashFunction1(key);  
        int stepSize = hashFunction2(key); // 用hashFunction2计算探测步数  
        while (hashArray[hashVal] != null && hashArray[hashVal].getKey() != -1) {  
            hashVal += stepSize;  
            hashVal %= arraySize; // 以指定的步数向后探测  
        }  
        hashArray[hashVal] = item;  
        itemNum++;  
    }  
 
    public void extendHashTable() {  
        int num = arraySize;  
 itemNum = 0; // 重新记数，因为下面要把原来的数据转移到新的扩张的数组中  
        arraySize *= 2; // 数组大小翻倍  
        DataItem[] oldHashArray = hashArray;  
 hashArray = new DataItem[arraySize];  
        for (int i = 0; i < num; i++) {  
            insert(oldHashArray[i]);  
        }  
    }  
 
    public DataItem delete(int key) {  
        if (isEmpty()) {  
            System.out.println("Hash table is empty!");  
            return null;  
        }  
        int hashVal = hashFunction1(key);  
        int stepSize = hashFunction2(key);  
        while (hashArray[hashVal] != null) {  
            if (hashArray[hashVal].getKey() == key) {  
                DataItem temp = hashArray[hashVal];  
                hashArray[hashVal] = nonItem;  
                itemNum--;  
                return temp;  
            }  
            hashVal += stepSize;  
            hashVal %= arraySize;  
        }  
        return null;  
    }  
 
    public DataItem find(int key) {  
        int hashVal = hashFunction1(key);  
        int stepSize = hashFunction2(key);  
        while (hashArray[hashVal] != null) {  
            if (hashArray[hashVal].getKey() == key) {  
                return hashArray[hashVal];  
            }  
            hashVal += stepSize;  
            hashVal %= arraySize;  
        }  
        return null;  
    }  
}  
 
class DataItem {  
    private int iData;  
 
    public DataItem(int data) {  
 iData = data;  
    }  
 
    public int getKey() {  
        return iData;  
    }  
}  

public class HashTableDouble {  
    private SortedList[] hashArray; // 数组中存放链表  
    private int arraySize;  
 
    public HashTableDouble(int size) {  
 arraySize = size;  
 hashArray = new SortedList[arraySize];  
        // new出每个空链表初始化数组  
        for (int i = 0; i < arraySize; i++) {  
            hashArray[i] = new SortedList();  
        }  
    }  
 
    public void displayTable() {  
        for (int i = 0; i < arraySize; i++) {  
            System.out.print(i + ": ");  
            hashArray[i].displayList();  
        }  
    }  
 
    public int hashFunction(int key) {  
        return key % arraySize;  
    }  
 
    public void insert(LinkNode node) {  
        int key = node.getKey();  
        int hashVal = hashFunction(key);  
        hashArray[hashVal].insert(node); // 直接往链表中添加即可  
    }  
 
    public LinkNode delete(int key) {  
        int hashVal = hashFunction(key);  
        LinkNode temp = find(key);  
        hashArray[hashVal].delete(key);// 从链表中找到要删除的数据项，直接删除  
        return temp;  
    }  
 
    public LinkNode find(int key) {  
        int hashVal = hashFunction(key);  
        LinkNode node = hashArray[hashVal].find(key);  
        return node;  
    }  
}  

public class SortedList {  
    private LinkNode first;    
    public SortedList() {    
 first = null;    
    }    
    public boolean isEmpty() {    
        return (first == null);    
    }    
    public void insert(LinkNode node) {    
        int key = node.getKey();    
        LinkNode previous = null;    
        LinkNode current = first;    
        while(current != null && current.getKey() < key) {    
 previous = current;    
 current = current.next;    
        }    
        if(previous == null) {    
 first = node;    
        }    
        else {    
 node.next = current;    
 previous.next = node;    
        }    
    }    
    public void delete(int key) {    
        LinkNode previous = null;    
        LinkNode current = first;    
        if(isEmpty()) {    
            System.out.println("chain is empty!");    
            return;    
        }    
        while(current != null && current.getKey() != key) {    
 previous = current;    
 current = current.next;    
        }    
        if(previous == null) {    
 first = first.next;    
        }    
        else {    
 previous.next = current.next;    
        }    
    }    
    public LinkNode find(int key) {    
        LinkNode 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):");    
        LinkNode current = first;    
        while(current != null) {    
            current.displayLink();    
 current = current.next;    
        }    
        System.out.println("");    
    }    
}    
class LinkNode {    
    private int iData;    
    public LinkNode next;    
    public LinkNode(int data) {    
 iData = data;    
    }    
    public int getKey() {    
        return iData;    
    }    
    public void displayLink() {    
        System.out.print(iData + " ");    
    }    
}  
在没有冲突的情况下，哈希表中执行插入和删除操作可以达到O(1)的时间级。