哈希表分为两大类，一是开放地址法，二是链地址法。
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();
}
}
|
收藏
淘帖
踩
