实现简单的Hash数据结构

          一：对以往所学的简单数据结构回顾
  学习程序语言时数组是我们首先接触到的数据结构。众所周知，数组在访问数据时通过下标可以及其快速的访问数据,但是在删除和插入时数组就表现的并不优越。
  链表在数据的删除和插入时会很方便，但是不能达到对数据的快速访问。
  那么有没有一种对两者进行综合的数据结构呢？
  答案是肯定的。比如Hash数据结构就可以即拥有数组的优点又可以实现链表的优点。
  那么我们就简单的介绍一下什么是Hash，并实现一个简单的Hash结构
          二：Hash的简单介绍
  Hash：Hash就是将任意长度的输入通过散列算法得到固定长度的输出，该输出即为散列值。
其中得到散列值的方法极为散列函数。散列函数可以得到存储元素的存储位置。
    例如：向数组中存入数据 200，如果直接将200作为数组的元素值存储(比如array[i]=200)，则在查找的时候需要遍历数组并判断某一位置是否是200。

这样的存储方法在查找在数据比较多的时候会比较浪费时间。
    那么我们可以通过某一函数，获得该元素所在位置的索引，那么在查找的时候只需获得该索引位置的数据即可。
    比如：
            int index = H(存入的元素);
    其中index 即为获得的索引。而该函数即为散列函数。
    常用的构造散列函数的方法如下：
     1：直接寻址法
     2：数字分析法
     3：平方取中法
     4：折叠法
     5：随机法
     6：除留取余法：取关键字被某个不大于散列表长度的数P除后所得的余数为散列地址。例如关键字200,取P=30；余数20即为关键字200的散列地址。
          三：用除留取余法实现一个简单的Hash结构

  聪明的你肯定会想到在做除留取余时可能会出现具有相同散列地址的情况。
  为了处理这一问题我们就需要将数组和链表联合使用了。
  其中数组存储链表，而链表存储元素。
  依然用除留取余法获得元素的索引，若有相同的散列地址则将该数据添加到该位置处链表中

  那么我们首先定义一个节点类

  package hashV3;

public class DataNode {
	public int member;
	public DataNode next;
}

 定义一个链表并实现数据的添加和删除

package hashV3;

public class MyHash {
	private DataNode[] array = new DataNode[100];
	
	private int getHash(DataNode node){
		int index = node.member%10;
		return index;
	}
	
	/**
	 * 添加元素
	 * @param node
	 */
	public void add(DataNode node){
		int index = this.getHash(node);
		if(array[index] == null){
			array[index] = node;
		}else{
			node.next = array[index];
			array[index] = node;
			System.out.println("====--->>>>"+node.member);
		}
		
	}
	
	public boolean remove(DataNode node){
		int index = this.getHash(node);
		if(node == null || array[index]==null){ //如果删除的数据为空
			return false;
		}
		
		DataNode temp = array[index];
		if(temp.member==node.member){//如果删除的是第一个数据
			array[index] = temp.next;
		}
		
		while(temp.next.member != node.member && temp.next!=null){
			temp = temp.next;
		}
		temp.next = temp.next.next;
		return true;
	}
	
	/**
	 * 打印数据
	 */
	public void print(){
		for(int i=0; i<array.length; i++){
			if(array[i]!= null){
				DataNode node = array[i];
				while(node != null){
					System.out.println("        "+node.member);
					node = node.next;
				}
			}
		}
	}
}

  则在主函数中实现数据的添加和删除

package hashV3;

import java.util.Random;
	
public class HashMain {
	public static void main(String[] args){
		HashMain h = new HashMain();
		h.add();
	    h.remove();
	}
	
	/**
	 * 添加方法
	 */
	private void add(){
		MyHash hash = new MyHash();
		Random rand = new Random();
		for(int i=0; i<10; i++){
			int a = rand.nextInt(4);
			DataNode node = new DataNode();
			node.member = a;
			hash.add(node);
		}
		hash.print();
	}
	
	/**
	 * 删除方法
	 */
	private void remove(){
		MyHash hash = new MyHash();
		DataNode n = new DataNode();
		n.member = 2;
		hash.remove(n);
		System.out.println("************************************************");
		hash.print();
	}
}