链地址法比开放地址法要好。
哈希化的效率：
1，线性探测：成功查找P=(1+1/(1-L))/2；不成功查找为P=(1+1/(1-L)^2)/2；其中P为探测序列，L为装填因子
2，二次探测和再哈希法：成功查找P=-log2(1-L)/L；不成功查找P=1/(1-L)
3，链地址法：成功查找和插入P=1+L/2；不成功查找P=1+L
比如装填因子L=1/2时，线性探测成功查找和不成功查找平均需要1.5次和2.5次；二次探测为2次和2次；而对于链地址法，这是一个线性函数，查找很快。随着装填因子变大，链地址法性能下降的最慢。
import java.util.Random; //链地址法 class Link { int data; Link next; public Link(int data) { this.data = data; } } // 有序链表对成功查找没啥影响，但可以减少查找不到的时间 class SortedLink { private Link first; public SortedLink() { first = null; } public void insert(int key) { Link current = first; Link previous = null; Link link = new Link(key); while (current != null && key > current.data) { previous = current; current = current.next; } if (previous == null)// first为null或一开始key最小 first = link; else previous.next = link; link.next = current; } public boolean delete(int key) { Link current = first; Link previous = null; while (current != null && key >= current.data) { if (current.data == key) { if (previous == null)// 如果删除的为第一个 first = first.next; else previous.next = current.next; return true; } previous = current; current = current.next; } return false; } public Link find(int key) { Link current = first; while (current != null && key >= current.data) { if (key == current.data) return current; current = current.next; } return null; } public void displayLink() { Link current = first; while (current != null) { System.out.print(current.data + "/"); current = current.next; } System.out.print(" "); } } public class HashChain { private SortedLink[] linkArray; private int size; public HashChain(int size) { this.size = size; linkArray = new SortedLink[size]; for (int i = 0; i < size; i++) linkArray[i] = new SortedLink(); } public void insert(int key) { int hashval = hashfunc(key); linkArray[hashval].insert(key); } public void find(int key) { int hashval = hashfunc(key); Link link = linkArray[hashval].find(key); if (link != null) System.out.println(link.data); } public void delete(int key) { int hashval = hashfunc(key); boolean bool = linkArray[hashval].delete(key); System.out.println(bool); } private int hashfunc(int key) { return key % size; } public void display() { for (int i = 0; i < size; i++) linkArray[i].displayLink(); System.out.println(); } public static void main(String[] args) { HashChain hash = new HashChain(23); Random rand = new Random(); int[] array = new int[10]; for (int i = 0; i < 10; i++) array[i] = rand.nextInt(1000); for (int n : array) hash.insert(n); hash.display(); int temp = array[3]; hash.find(temp); hash.delete(temp); hash.delete(temp); hash.display(); hash.find(temp); hash.insert(200); hash.display(); } }我们也可以使用平衡树来代替链表，进一步提高查找的效率。import java.util.Random;import RBTree.RBTree;//使用平衡二叉树（红黑树）代替链表建立哈希表@SuppressWarnings({ "unchecked", "rawtypes" })public class HashTree { private RBTree[] itemArray;//参考红黑树实现 private int maxSize; public HashTree(int size) { maxSize = size; itemArray = new RBTree[size]; for (int i = 0; i < size; i++) itemArray[i] = new RBTree(); } public void insert(int key) { int hashval = hashfunc(key); itemArray[hashval].insert(key); } public boolean find(int key) { int hashval = hashfunc(key); return itemArray[hashval].find(key); } public int hashfunc(int key) { return key % maxSize; } public void display() { for (int i = 0; i < maxSize; i++) { if (itemArray[i].root == null) System.out.print("[] "); else { itemArray[i].display(itemArray[i].root); System.out.print(" "); } } System.out.println(); } public static void main(String[] args) { HashTree hash = new HashTree(31); Random rand = new Random(); int[] array = new int[20]; for (int i = 0; i < 20; i++) array[i] = rand.nextInt(100); for (int a : array) hash.insert(a); hash.display(); System.out.println(hash.find(array[5])); }}
