挂链式---hash表的实现

 一、什么是hash表，它的作用？

简而言之：hash表就是将数据依特定算法直接指定到一个地址上。hashCode方法实际上返回的就是对象存储的物理地址。那你就会想到为什么不用数组和链表来存储这些数据呢？

先来看一下数组和链表他们的优势：

数组：对数据的查询的比较方便

链表：对数据进行插入和删除比较方便

而往往我们对数据同时要进行插入、删除、查找，这时候你就应该想到hash表的作用了，因为他的实现形式-----数组+链表。

二、实现hash表需要注意的地方

1、Hash冲突
2、衡量一个HASH
3、冲突因子
4、重新增加hash,重新散列
5、弱引用的回收

三、自己实现链式hash表的步骤：

1认识链式hash表的形式

 

如图：

    数组            链表

2、获得hash值

由于自己写出不同数据类型的hash值算法比较难，我们就调用JDK提供的hashCode()来计算hash值

3、添加新的元素

当集合要添加新的元素时，先调用这个元素的hashCode方法，就一下子能定位到它应该放置的物理位置上。如果这个位置上没有元素，它就可以直接存储在这个位置上，不用再进行任何比较了；如果这个位置上已经有元素了，就调用它的equals方法与新元素进行比较，相同的话就不存了，不相同就散列其它的地址（挂链法）。

4、删除一个元素

首先，判断元素的位置，分为在首位置、挂链上面。如果，在首位置就直接删除，而在挂链上的话，则需要遍历找到这个值再将其删除。

5、rehash

当元素的个数+5>hash长度的时候，就rehash

6、打印所有元素

7、性能测试

我的是与list比较同时插入1000000个数的速度快慢和查询一个元素的速度

写道

package cn.netjava.hash;
//节点类
public class Node {
private Object value;//节点的值
private Node next;//链表中指向下一结点的引用

public Node(Object value){this.value=value;}
//得到值
public Object getValue(){return value;}
//得到下一个节点
public Node getNext(){return next;}
//设置下一个节点
public void setNext(Node next){this.next=next;}
}

package cn.netjava.hash;

public class HashCode {
private Node[] HashList;//哈希链表
private int size=0; //数组的长度
private int Have=0; //元素个数

//构造方法的创建
public HashCode(int size){
HashList=new Node[size];
this.size=size;
}

//获得大小
public int getSize(){
return size;
}
//获得哈希编码
public int getHashCode(Object data){
return data.hashCode()*1024%size;
}
//增加元素
public void add(Object data){
int index=getHashCode(data);//得到hash码相应的下标
//创建新的节点
Node newN=new Node(data);
if(HashList[index]==null){
HashList[index]=newN;
}else{
//否则就加入到其下拉链表中
Node Next=HashList[index];
if(Next.getValue().equals(data)){
//重复则不添加
return;
}
while(Next.getNext()!=null){
//递归到最后为空的链表
if(Next.getValue().equals(data)){
//重复则不添加
return;
}
Next=Next.getNext();
}
Next.setNext(newN);//设置为其下拉链表
}
Have++;//统计元素个数
if(Have+5>size){
reHash();
}
}
//取得其中的一个数
public void find(Object data){
int index=getHashCode(data);
Node node=HashList[index];
while(node.getNext()!=null){
if(node!=null&&node.getValue().equals(data)){
System.out.println("查找成功！！！");
return;
}
}
}
//删除一个
public void remove(Object node){
int index=getHashCode(node);
//当在首节点的时候
if(HashList[index].getValue()==node){
if(HashList[index].getNext()==null){
HashList[index]=null;//没有挂链就直接移除
}else{
//有挂链
HashList[index]=HashList[index].getNext();
}
return;
}
//要删除的数在挂链中
Node temp=HashList[index];
Node last=null;
while(!temp.getValue().equals(node)&&temp!=null){
last=temp;
temp=temp.getNext();
}

if(temp!=null&&temp.getValue().equals(node)&&last!=null){
last.setNext(temp.getNext());
}
}
//再一次hash
public void reHash(){
Node[] TempList=HashList;
size=size*2;
HashList=new Node[size];
Have=0;
//在hash放入原来hashlist中去
for(int i=0;i<size/2;i++){
if(TempList[i]!=null){
add(TempList[i].getValue());
//加入挂链中的内容
while(TempList[i].getNext()!=null){
TempList[i]=TempList[i].getNext();
add(TempList[i].getValue());
}
}
}
}
//打印全部的出来
public void printAll(){
for(int i=0;i<size;i++){
Node temp=HashList[i];
while(temp!=null){
System.out.println(temp.getValue()+"-----"+temp.hashCode());
temp=temp.getNext();
}
}
}
}

package cn.netjava.hash;

import java.util.List;
import java.util.LinkedList;

public class Test {

public static void main(String[] args) {
HashCode code=new HashCode(100000);
Long startTime=System.currentTimeMillis();
for(int i=1;i<=100000;i++){
code.add(i*4);
}
Long endTime=System.currentTimeMillis();
System.out.println("hash insert time--->"+(endTime-startTime));
code.remove(12);
Long startTime2=System.currentTimeMillis();
code.find(24);
Long endTime2=System.currentTimeMillis();
System.out.println("hash find time--->"+(endTime2-startTime2));
//code.printAll();
System.out.println("-------华丽的分割线-------");
List<Integer> list = new LinkedList<Integer>();

Long startTime1=System.currentTimeMillis();
for(int i=1;i<=100000;i++){
list.add(i);
}
Long endTime1=System.currentTimeMillis();
System.out.println("list insert time--->"+(endTime1-startTime1));

Long startTime4=System.currentTimeMillis();
list.get(24);
Long endTime4=System.currentTimeMillis();
System.out.println("list get time--->"+(endTime4-startTime4));
}
}

 

       对hash的原理和运用还有深入！！！