Java数据结构温习之哈希表-链地址法

哈希表分为两大类，一是开放地址法，二是链地址法。
1）、开放地址法中，通过在哈希表中再找一个空位解决冲突问题。
2）、链地址法中，某个数据项的关键字值还是像通常一样映射到哈希表的单元，而数据项本身插入到这个单元的链表中，其他同样映射到该位置的数据项只需要加入到链表中。

链地址法Java简缩代码：

/**
* 节点类
*/
class Link{
private int data;
public Link next;

public Link(int data){
this.data = data;
this.next = null;
}

public int getKey(){
return this.data;
}

public void display(){
System.out.println(this.data);
}
}

/**
* 优先级链表
*/
class SortedList{
private Link first;

public SortedList(){
this.first = null;
}

public void insert(Link theLink){
int key = theLink.getKey();
Link current = this.first;
Link previous = null;

while (current != null && key > current.getKey()){
previous = current;
current = current.next;
}

if (previous != null){
previous.next = theLink;
}else{
this.first = theLink;
}

theLink.next = current;
}

public Link find(int key){
Link current = this.first;
while (current != null && key != current.getKey()){
current = current.next;
}

return current;
}

public void display(){
Link current = this.first;
while (current != null){
current.display();
current = current.next;
}
}
}

/**
* 链地址哈希表
*/
class HashTableLink{
private SortedList[] hashArray;
private int arraySize;

public HashTableLink(int size){
this.arraySize = size;
this.hashArray = new SortedList[this.arraySize];
for (int i = 0; i < this.arraySize; i++){
this.hashArray[i] = new SortedList();
}
}

public int keyFunc(int key){
return key % this.arraySize;
}

public void insert(Link theLink){
int key = keyFunc(theLink.getKey());
this.hashArray[key].insert(theLink);
}

public Link find(int key){
key = keyFunc(key);
return this.hashArray[key].find(key);
}

public void display(){
for (int i = 0; i < this.arraySize; i++){
System.out.println("i: " + i);
this.hashArray[i].display();
}
}

}

public class HashTableTest {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
HashTableLink htl = new HashTableLink(3);
for (int i = 1; i < 12; i ++){
Link link = new Link(i);
htl.insert(link);
}

htl.display();

}

}