15.链地址法

同样是为了解决哈希表中索引重复问题的算法，基本思路为将哈希表中维护的数组改成存储链表的数组，将数据存在链表中。也可以用数组但是数组的插入和删除的效率较低，故采用链表。

实现：

链表的实现：

1/*
2 * 链结点，相当于是车厢
3 */
4public class Node {
5	//数据域
6	public Info info;
7	//指针域
8	public Node next;
9	
10	public Node(Info info) {
11		this.info = info;
12	}
13	
14}
15
16/*
17 * 链表，相当于火车
18 */
19public class LinkList {
20	//头结点
21	private Node first;
22	
23	public LinkList() {
24		first = null;
25	}
26	
27	/**
28	 * 插入一个结点，在头结点后进行插入
29	 */
30	public void insertFirst(Info info) {
31		Node node = new Node(info);
32		node.next = first;
33		first = node;
34	}
35	
36	/**
37	 * 删除一个结点，在头结点后进行删除
38	 */
39	public Node deleteFirst() {
40		Node tmp = first;
41		first = tmp.next;
42		return tmp;
43	}
44	
45	
46	/**
47	 * 查找方法
48	 */
49	public Node find(String key) {
50		Node current = first;
51		while(!key.equals(current.info.getKey())) {
52			if(current.next == null) {
53				return null;
54			}
55			current = current.next;
56		}
57		return current;
58	}
59	
60	/**
61	 * 删除方法，根据数据域来进行删除
62	 */
63	public Node delete(String key) {
64		Node current = first;
65		Node previous = first;
66		while(!key.equals(current.info.getKey())) {
67			if(current.next == null) {
68				return null;
69			}
70			previous = current;
71			current = current.next;
72		}
73		
74		if(current == first) {
75			first = first.next;
76		} else {
77			previous.next = current.next;
78		}
79		return current;
80		
81	}
82}

哈希表的实现：

1public class HashTable {
2	private LinkList[] arr;
3	
4	/**
5	 * 默认的构造方法
6	 */
7	public HashTable() {
8		arr = new LinkList[100];
9	}
10	
11	/**
12	 * 指定数组初始化大小
13	 */
14	public HashTable(int maxSize) {
15		arr = new LinkList[maxSize];
16	}
17	
18	/**
19	 * 插入数据
20	 */
21	public void insert(Info info) {
22		//获得关键字
23		String key = info.getKey();
24		//关键字所自定的哈希数
25		int hashVal = hashCode(key);
26		if(arr[hashVal] == null) {
27			arr[hashVal] = new LinkList();
28		}
29		arr[hashVal].insertFirst(info);
30	}
31	
32	/**
33	 * 查找数据
34	 */
35	public Info find(String key) {
36		int hashVal = hashCode(key);
37		return arr[hashVal].find(key).info;
38	}
39	
40	/**
41	 * 删除数据
42	 * @param key
43	 * @return
44	 */
45	public Info delete(String key) {
46		int hashVal = hashCode(key);
47		return arr[hashVal].delete(key).info;
48	}
49	
50	public int hashCode(String key) {
51		BigInteger hashVal = new BigInteger("0");
52		BigInteger pow27 = new BigInteger("1");
53		for(int i = key.length() - 1; i >= 0; i--) {
54			int letter = key.charAt(i) - 96;
55			BigInteger letterB = new BigInteger(String.valueOf(letter));
56			hashVal = hashVal.add(letterB.multiply(pow27));
57			pow27 = pow27.multiply(new BigInteger(String.valueOf(27)));
58		}
59		return hashVal.mod(new BigInteger(String.valueOf(arr.length))).intValue();
60	}
61}

所存储的实体类：

1/**
2 * 员工信息类
3 * @author Administrator
4 *
5 */
6public class Info {
7	private String key;
8	private String name;
9	
10	public Info(String key, String name) {
11		this.key = key;
12		this.name = name;
13	}
14
15	public String getKey() {
16		return key;
17	}
18
19	public void setKey(String key) {
20		this.key = key;
21	}
22
23	public String getName() {
24		return name;
25	}
26
27	public void setName(String name) {
28		this.name = name;
29	}
30}